- •Программа дисциплины
- •Тема 1 общая характеристика и классификация математических методов и моделей, применяемых в экономических исследованиях Предмет математического программирования
- •Общая схема формирования экономико-математической модели
- •Классификация методов математического программирования
- •Тема 2 линейное программирование Задача линейного программирования (злп)
- •Формы записи задач линейного программирования
- •Приемы, позволяющие переходить от одной формы записи условий задач к другой
- •Графический метод решения злп
- •Симплекс-метод решения злп
- •Алгоритм симплекс-метода
- •Геометрическая интерпретация в случае двух переменных
- •Отыскание начального опорного плана (1-ый пункт алгоритма)
- •Отыскание начального опорного плана методом искусственного базиса
- •Отыскание начального опорного плана путем преобразования таблицы Жордана
- •Шаг Жордановых исключений осуществляется по следующим правилам:
- •Исследование на оптимальность опорного плана при минимизации целевой функции (второй пункт алгоритма)
- •Переход к новому, нехудшему опорному плану (третий пункт алгоритма)
- •Тема 3 транспортная задача линейного программирования Постановка транспортной задачи по критерию стоимости в матричной форме
- •Закрытая и открытая модели транспортной задачи
- •Алгоритм решения сбалансированной транспортной задачи
- •Построение исходного опорного плана (первый пункт алгоритма)
- •Проверка на оптимальность невырожденного опорного плана методом потенциалов (второй пункт алгоритма)
- •Переход к нехудшему опорному плану (третий пункт алгоритма)
- •Цикл пересчета
- •Тема 4 динамическое программирование
- •I этап. Условная оптимизация
- •II этап. Безусловная оптимизация
- •Задача об оптимальной стратегии замены оборудования
- •I этап. Условная оптимизация
- •II этап. Безусловная оптимизация
- •Литература
- •Тема 1 общая характеристика и классификация математических методов и моделей, применяемых в экономических исследованиях 3
- •Тема 2 линейное программирование 6
- •Тема 3 транспортная задача линейного программирования 33
- •Тема 4 динамическое программирование 50
Тема 3 транспортная задача линейного программирования Постановка транспортной задачи по критерию стоимости в матричной форме
В m пунктах отправления сосредоточен однородный груз в количестве соответственно единиц. Имеющийся груз необходимо доставить потребителям , спрос которых выражается величинами единиц. Известна стоимость перевозки единицы груза из -го ( ) пункта отправления в -й ( ) пункт назначения.
Требуется составить план перевозок, который полностью удовлетворяет спрос потребителей в грузе, и при этом суммарные транспортные издержки минимизируются.
Для наглядности условие транспортной задачи (ТЗ) можно представить таблицей, которую будем называть распределительной. Распределительную таблицу называют иногда табличной или матричной моделью ТЗ (см. таблицу 14).
Таблица 14
Поставщик |
Потребитель |
Запас груза, |
|||
|
|
|
... |
|
|
|
|
|
... |
|
|
|
|
|
... |
|
|
... |
... |
... |
... |
... |
|
|
|
|
... |
|
|
Потребность в грузе |
|
|
... |
|
|
Для построения экономико-математической модели ТЗ введем переменные – количество груза, которое необходимо доставить из -го пункта отправления в -й пункт назначения.
Матрицу будем называть матрицей перевозок.
Цель ТЗ – минимизировать общие затраты на реализацию плана перевозок. Следовательно, целевая функция будет иметь вид
(3.1)
Составим систему ограничений, которая будет определять ОДР данной задачи в случае, когда .
Первые m уравнений системы (3.2) – это ограничения на запас груза у поставщиков, следующие n уравнений системы (3.2) – это ограничения на потребности потребителей в грузе, неравенства системы – это ограничения на смысл переменных (количество груза не может быть отрицательным).
(3.2)
Будем называть план перевозок
допустимым, если он удовлетворяет системе ограничений (3.2).
Допустимый план перевозок, доставляющий минимум целевой функции, называется оптимальным.
Закрытая и открытая модели транспортной задачи
Модель ТЗ называют закрытой (сбалансированной), если суммарный объем груза, имеющегося у поставщиков, равен суммарному спросу потребителей, т.е. выполняется равенство:
.
Если для транспортной задачи выполняется одно из условий:
, (3.3)
, (3.4)
то модель задачи называют открытой (несбалансированной).
Для разрешимости ТЗ с открытой моделью необходимо преобразовать ее в закрытую модель.
Так, при выполнении условия (3.3) необходимо ввести фиктивный (n+1)-й пункт назначения , т.е. в матрице задачи добавляется столбец. Спрос фиктивного потребителя полагают равным небалансу, т.е. , а стоимость перевозок равной нулю, т.е. . Переменные – это количество груза, которое останется в i-ом пункте отправления. Аналогично при выполнении условия (3.4) вводится фиктивный поставщик , т.е. в матрице задачи добавляется строка. Запас груза фиктивного поставщика равен , а тарифы (стоимости перевозок) равны нулю, т.е. . Переменные – это количество груза, недостающее j-му пункту назначения.
При преобразовании открытой модели задачи в закрытую модель целевая функция не изменяется, так как все слагаемые, соответствующие дополнительным перевозкам, равны нулю.
Целевая функция (3.1) и система ограничений (3.2) являются экономико-математической моделью сбалансированной ТЗ.