Метод динамического программирования управление запросами. Динамическое программирование, основные принципы. I этап. Условная оптимизация

На начальном этапе решения транспортной задачи необходимо получить первоначальный опорный план. Как это сделать, подробно описано в статье Как решить транспортную задачу . После получения опорного плана необходимо проверить его на невырожденность.

Правило: количество базисных (заполненных) клеток в первоначальном плане ВСЕГДА должно быть равно m + n - 1, где m - количество поставщиков, n - количество потребителей транспортной задачи.

Что же делать, если количество заполненных ячеек опорного плана меньше необходимого?

На некотором шаге получения первоначального плана может сложиться ситуация, когда одновременно удовлетворяются потребности магазина и опустошается склад. В этом случае происходит "потеря" базисной клетки. Это приводит к тому, что система определения потенциалов имеет не единственное решение.

Чтобы обойти эту ситуацию, добавим к базисным ячейкам недостающее количество ячеек с нулевыми значениями. Нулевое значение поставим в клетку, стоящую рядом с базисной клеткой, которая обусловила "пропажу" базисного значения.

Вырожденность опорного решения транспортной задачи - пример 1:

Построить первоначальный план для следующей ситуации:

Количество поставщиков (складов) = 3, количество потребителей (магазинов) = 4

60 + 30 + 40 = 40 + 50 + 10 + 30 - спрос равен предложению - задача закрытая.

Методом северо - западного угла получим опорный план.

Начинаем с самой верхней левой ячейки.

Потребности первого магазина выполнены полностью, но на складе еще остался груз. Заполняем дальше.

Остатки груза с первого склада 60 - 40 = 20 перевозим в магазин второй. При этом, первый склад опустел, но потребности магазина не выполнены полностью.

Переходим ко второму складу. Все 30 единиц груза переносим в магазин второй, потребности которого совпали с предложением склада 50 - 20 = 30.

При данном распределении склад опустошается и потребности второго магазина выполняются полностью. Происходит потеря базисной клетки!

В данном случае необходимо к базисным клеткам добавить клетку с нулевым значением, расположенную рядом с только что заполненной, которая обусловила потерю.

Продолжим.

С третьего склада направим 10 единиц груза в магазин 4 для полного выполнения его потребностей. На 3-м складе остается 40 - 10 = 30 единиц груза, которые перенесем в последний магазин.

Опорный план составлен.

Количество базисных ячеек равно 6 = 3 + 4 - 1. Условие невырожденности выполнено!

Вырожденность опорного решения транспортной задачи - пример 2:

Три торговых склада поставляют продукцию в четыре магазина. Наличие продукции на складах и потребности магазинов приведены в следующей таблице. Построим первоначальный план транспортной задачи:

Задача закрытая:

12 + 10 + 14 = 36

4 + 18 + 8 + 6 = 36

Первоначальный план получим методом северо - угла.

Начнем с заполнения ячейки (1;1).

Запасы первого склада распределили по первому и второму магазину, при этом запасы склада исчерпаны, а потребность второго магазина не удовлетворена. Переходим ко второму складу.

Все 10 единиц груза направляем во второй магазин, потребности которого на данный момент равны 18 - 8 = 10. Заметим, что на данном шаге одновременно удовлетворяются потребности второго магазина и закончились запасы второго склада. Произошла потеря одного базисного значения.

Ничего страшного, если вы упустите этот момент при получении опорного плана. Главное не забыть проверить условие невырожденности перед проверкой плана на оптимальность. Проанализировав уже полученное распределение груза, нетрудно найти момент, когда была "потеряна" базисная клетка.

Чтобы компенсировать потерю, мы должны ввести нулевую ячейку, рядом с заполненной. Можем поместить ее правее, левее или ниже значения 10.

Закончим заполнение таблицы:

Получили первоначальный план методом северо - западного угла. Количество базисных ячеек равно 4 + 3 - 1 = 6.

Можно приступать к решению задачи методом потенциалов!

Предположим, что каноническая задача ЛП имеет не совсем специальный вид, а к примеру, правые части уравнений системы ограничений могут быть отрицательны.
Этот случай возникает при решении задачи о рационе . Канонический вид задачи выглядит так:

F = 20х 1 + 20х 2 + 10х 3 → min.

Запишем задачу в симплекс-таблицу (табл. 1).

Таблица 1

Базисное решение, соответствующее базису {x 4 , x 5 , x 6 } и равное (0; 0; 0; -33; 23; -12), не является допустимым ввиду отрицательности х 4 < 0, x 5 < 0, x 6 < 0.

Сформулируем правило нахождения допустимого опорного плана .
Если в столбце свободных членов есть отрицательные элементы, выберите из них наибольший по модулю, а в его строке - любой отрицательный. Взяв этот элемент в качестве разрешающего пересчитайте таблицу по прежним правилам 2-5 .
Если в полученной таблице все элементы столбца свободных членов стали положительны либо 0, то данное базисное решение можно взять в качестве первоначального опорного плана. . Если в столбце свободных членов не все элементы неотрицательны, то еще раз воспользоваться этим правилом.
Проведем этот шаг для задачи о рационе. В качестве разрешающей строки табл. 1 нужно выбрать первую. А разрешающим элементом выберем, к примеру, элемент -4.

Таблица 2

базисные				свободные

Заметим, что переменная х 1 вошла в базис вместо х 4 , все вычисления осуществлялись по правилу 2-5. В правом столбце еще остался отрицательный элемент, воспользуемся правилом еще раз. Строка переменной х 6 - разрешающая, а в качестве разрешающего элемента возьмем, к примеру, 3 / 2 , здесь есть некоторая возможность выбора.

Таблица 2

базисные				свободные

Полученный базисный план х * = (х 1 , х 2 , х 3, х 4 , х 5 , х 6) = (7, 0, 5/2, 0, 1/2, 0) является допустимым и, к тому же, оказывается оптимальным, т.к. в индексной строке нет отрицательных элементов. Оптимальное значение целевой функции равно F* = 165. Действительно,
F = 20х 1 + 20х 2 + 10х 3 = 20 · 7 + 0 + 10· = 140 + 25 = 165.

В этой задаче не пришлось улучшать найденный первоначальный опорный план, т.к. он оказался оптимальным. Иначе, мы должны были вернуться к III этапу.

Решение задачи о плане симплекс-методом

Задача. Предприятие располагает тремя видами сырья и намеревается выпускать четыре вида продукции. Коэффициенты в таблице 3.12 указывают затраты соответствующего вида сырья на единицу определенного вида продукции, а также прибыль от реализации единицы продукции и общие запасы ресурсов. Задача: найти оптимальный план производства продукции, при котором будет обеспечена максимальная прибыль.

Таблица 3

Составим математическую модель. Пусть х 1 , х 2 , х 3 , х 4 - количество продукции I, II, III, IV вида соответственно в плане. Тогда количество используемого сырья и его запасы выразятся в неравенствах:

F = 3x 1 + 5x 2 + 4x 3 + 5x 4 → max.

Целевая функция выражает собой общую суммарную прибыль, полученную от реализации всей плановой продукции, а каждое из неравенств выражает затраты определенного вида продукции. Понятно, что затраты не должны превышать запасов сырья.

Приведем задачу к канонической форме и к специальному виду, введя дополнительные переменные х 5 , х 6 , х 7 в каждое из неравенств.
Очевидно, что, если первого ресурса необходимо для производства плановой продукции 5х 1 + 0,4х 2 + 2х 3 + 0,5х 4 , то х 5 обозначает просто излишки первого ресурса как разность между имеющимся запасом и требуемым для производства. Аналогично х 6 и х 7 . Итак, дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.

Запишем задачу в таблицу 4, предварительно выписав ее каноническую форму:

I этап . Это задача специального вида, базис составляют переменные { х 5 , х 6 , х 7 }, правые части уравнений неотрицательны, план х = (0, 0, 0, 0, 400, 300, 100) - опорный. Он соответствует симплекс-таблице.

Таблица 4

базисные					свободные

II этап . Проверим план на оптимальность. Так как в индексной F -строке есть отрицательные элементы, то план неоптимален, переходим к III этапу.

III этап . Улучшение опорного плана. Выберем в качестве разрешающего столбца четвертый, но могли бы выбрать и второй, т.к. в обоих (-5). Остановившись на четвертом, выберем в качестве разрешающего элемента 1, т.к. именно на нем достигается минимум соотношений . С разрешающим элементом 1 проводим преобразование таблицы по правилам 2-5 (табл. 5).

Таблица 5

Полученный план опять неоптимален, т.к. в F -строке есть отрицательный элемент -5 . этот столбец разрешающий.

В качестве разрешающего элемента выбираем 5, т.к. .

Пересчитываем еще раз таблицу. Заметим, что пересчет удобно начинать с индексной строки, т.к. если в ней все элементы неотрицательны, то план оптимален, и чтобы его выписать, достаточно пересчитать столбец свободных членов, нет необходимости вычислять "внутренность" таблицы (табл. 6).

Таблица 6

базисные					свободные

План оптимален, т.к. в индексной строке нет отрицательных элементов, выписываем его.

IV этап . Базисные переменные {x 5 , x 2 , x 4 } принимают значения из столбца свободных членов, а свободные переменные равны 0. Итак, оптимальный план х * = (0, 40, 0, 100, 334, 0, 0) и F * = 700. Действительно, F = 3х 1 + 4х 3 + 5х 2 + 5х 4 = 5 · 40 + 5 · 100 = 700. Т. е. для получения максимальной прибыли в 700 руб. предприятие должно выпускать изделия II вида в количестве 40 штук, IV - вида в количестве 100 штук, изделия I и III вида производить невыгодно. При этом сырье второго и третьего вида будет израсходовано полностью, а сырья первого вида останется 334 единицы (х 5 = 334, х 6 = 0, х 7 = 0).