- •Программа дисциплины
- •Тема 1 общая характеристика и классификация математических методов и моделей, применяемых в экономических исследованиях Предмет математического программирования
- •Общая схема формирования экономико-математической модели
- •Классификация методов математического программирования
- •Тема 2 линейное программирование Задача линейного программирования (злп)
- •Формы записи задач линейного программирования
- •Приемы, позволяющие переходить от одной формы записи условий задач к другой
- •Графический метод решения злп
- •Симплекс-метод решения злп
- •Алгоритм симплекс-метода
- •Геометрическая интерпретация в случае двух переменных
- •Отыскание начального опорного плана (1-ый пункт алгоритма)
- •Отыскание начального опорного плана методом искусственного базиса
- •Отыскание начального опорного плана путем преобразования таблицы Жордана
- •Шаг Жордановых исключений осуществляется по следующим правилам:
- •Исследование на оптимальность опорного плана при минимизации целевой функции (второй пункт алгоритма)
- •Переход к новому, нехудшему опорному плану (третий пункт алгоритма)
- •Тема 3 транспортная задача линейного программирования Постановка транспортной задачи по критерию стоимости в матричной форме
- •Закрытая и открытая модели транспортной задачи
- •Алгоритм решения сбалансированной транспортной задачи
- •Построение исходного опорного плана (первый пункт алгоритма)
- •Проверка на оптимальность невырожденного опорного плана методом потенциалов (второй пункт алгоритма)
- •Переход к нехудшему опорному плану (третий пункт алгоритма)
- •Цикл пересчета
- •Тема 4 динамическое программирование
- •I этап. Условная оптимизация
- •II этап. Безусловная оптимизация
- •Задача об оптимальной стратегии замены оборудования
- •I этап. Условная оптимизация
- •II этап. Безусловная оптимизация
- •Литература
- •Тема 1 общая характеристика и классификация математических методов и моделей, применяемых в экономических исследованиях 3
- •Тема 2 линейное программирование 6
- •Тема 3 транспортная задача линейного программирования 33
- •Тема 4 динамическое программирование 50
Проверка на оптимальность невырожденного опорного плана методом потенциалов (второй пункт алгоритма)
1 Каждому поставщику поставим в соответствие потенциал , а каждому потребителю потенциал .
Тогда каждой занятой клетке будет соответствовать уравнение
.
Так как всех занятых клеток должно быть m + n – 1, т.е. на единицу меньше числа потенциалов, то для нахождения необходимо решить систему из m + n – 1 уравнений с m + n неизвестными. Система является линейно-зависимой и, чтобы найти частное решение, одному из потенциалов нужно придать произвольное числовое значение, тогда остальные потенциалы определяются однозначно. Например, потенциалы строк и столбцов для начального опорного плана, найденного в последнем примере методом минимального элемента определим из решения системы
Система является линейно-зависимой, для нахождения одного из частных решений придадим одному из потенциалов числовое значение, например , тогда
Для исследования плана на оптимальность для каждой свободной клетки считаем оценки по формуле
;
а) если все оценки положительны, то найденный опорный план оптимален и единственен ;
б) если наряду с положительными оценками встречаются и нулевые оценки , то найденный опорный план оптимален, но не единственен;
в) если оценка хотя бы одной свободной клетки отрицательна , то опорный план не является оптимальным, его можно улучшить за счет загрузки этой клетки. Если таких клеток несколько, то наиболее перспективной для загрузки является клетка с наименьшей оценкой. Например, для клеток имеем оценки . Здесь наиболее потенциальной (перспективной для загрузки) является клетка .
Переход к нехудшему опорному плану (третий пункт алгоритма)
Улучшим план перевозок за счет загрузки свободной клетки с отрицательной оценкой, для этого для наиболее перспективной свободной клетки строится замкнутый цикл с вершинами в загруженных клетках. Вершинам этого цикла условно присваиваются знаки: свободной клетке – плюс, следующей, по часовой или против часовой стрелке, занятой клетке – минус, следующей – снова плюс и т.д. Из поставок в клетках цикла с «отрицательными» вершинами выбирается наименьшее количество груза, которое и перемещается по клеткам этого цикла: прибавляется к поставкам в «положительных» вершинах и вычитается из поставок в «отрицательных» вершинах, в результате чего баланс цикла не нарушится.
Цикл пересчета
В общем случае цикл пересчета представляет собой замкнутую ломаную линию, состоящую из звеньев, пересекающихся под прямым углом. Каждое звено соединяет две клетки строки (столбца). Цикл включает одну свободную клетку, остальные клетки цикла заняты. В цикле всегда четное число клеток. Для свободной клетки всегда можно построить единственный цикл.
Если из занятых клеток образуется цикл, то план перевозок не является опорным. Цикл строится лишь для свободной клетки.
Например, найдем оценки свободных клеток начального опорного плана, построенного в последнем примере методом минимального элемента. Используя найденные выше потенциалы строк и столбцов , рассчитаем оценки свободных клеток:
Так как оценка , то найденный план не оптимален. Его можно улучшить путем загрузки этой клетки.
Составим цикл пересчета относительно клетки ( ) (см. таблицу 19).
Таблица 19
Хранилища |
Потребители |
Запас топлива, т |
|
|||||
|
В1 |
В2 |
В3 |
В4 |
В5 |
|
|
|
А1 |
|
|
|
|
|
70 |
|
|
А2 |
|
|
|
|
|
90 |
|
|
А3 |
|
|
|
|
|
50 |
|
|
Потребность в топливе, т |
50 |
70 |
40 |
40 |
10 |
210 |
|
|
|
|
|
|
|
|
|
|
Из клеток, помеченных знаком «–», выбираем наименьшее количество груза . Прибавляем значение к поставкам в клетках, помеченных знаком «+», и вычитаем из поставок в клетках, помеченных знаком «–». Получим следующий план перевозок (см. таблицу 20).
Таблица 20
Хранилища |
Потребители |
Запас топлива, т |
|
|||||
|
В1 |
В2 |
В3 |
В4 |
В5 |
|
|
|
А1 |
|
|
|
|
|
70 |
|
|
А2 |
|
|
|
|
|
90 |
|
|
А3 |
|
|
|
|
|
50 |
|
|
Потребность в топливе, т |
50 |
70 |
40 |
40 |
10 |
210 |
|
|
|
|
|
|
|
|
|
|
Полученный опорный план является вырожденным, так как число заполненных клеток равно 6 < m + n – 1 = 7. Для преодоления вырожденности плана поставим ноль в любую пустую клетку, не образующую цикла с уже заполненными клетками, например в клетку ( ) (см. таблицу 20).
Проверим найденный план на оптимальность, для этого найдем потенциалы строк и столбцов из решения системы:
Присвоив ,найдем
Запишем потенциалы в последнюю таблицу.
Определим оценки свободных клеток:
Так как все оценки неотрицательны, то найденный опорный план является оптимальным, а так как имеется нулевая оценка ( ), то этот план не единственен.
Итак, получили оптимальный план
.
Транспортные издержки для этого плана:
(усл ден. ед.).
Итак, по оптимальному плану необходимо из хранилища А1 потребителю B2 доставить 20 т топлива, потребителю B3 – 40 т топлива; из хранилища А2 потребителю В2 доставить 50 т топлива, а потребителю В4 –40 т топлива; из хранилища А3 доставить 50 т топлива потребителю В1.
При этом затраты на транспортировку будут минимальными и составят 490 усл. ден. ед. Нераспределенное топливо в размере 10 т останется в хранилище А1.