Задачи динамического программирования

Нижегородский институт менеджмента и бизнеса. Богомолова Е. С.

Содержание

Задание 1

Постановка  задачи 

Предприятие выпускает  два вида продукции, используя три  вида ресурсов. Принятые обозначения: А – матрица норм затрат ресурсов, В – запасы ресурсов в планируемый  период, С – прибыль на единицу продукции.

А = ; В = ; С =

С помощью данных, приведенных  в таблице, требуется:

1) Составить экономико-математическую  модель задачи;

2) Определить план  выпуска изделий, обеспечивающий получение максимальной прибыли;

3) Составить двойственную  задачу, найти оптимальное решение  и оптимум двойственной задачи  с помощью теорем двойственности; указать дефицитные для предприятия  ресурсы;

4) провести решение  графическим методом и рассмотреть, к чему приведет изменение запасов ресурсов;

5) провести решение симплекс-методом и рассмотреть экономическую интерпретацию последней симплекс-таблицы.

Решение

Экономико-математическая модель задачи линейного программирования имеет следующий вид:

= 4x₁ + x₂ → max;

где х₁ – план выпуска первого изделия, х₂ – план выпуска второго изделия.

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

Каждое неравенство определяет некоторую полуплоскость. Соответствующие области для каждого ограничения отмечены штрихами. Пересечение D данных полуплоскостей (т. е. множество точек, которые одновременно принадлежат каждой их них) является областью допустимых планов задачи. Поведение целевой функции f(x) = 4х₁+ х₂ в рамках двумерной иллюстрации может быть охарактеризовано с помощью линий уровня.

Линией уровня функции называется множество точек из ее области определения, в которых функция принимает одно и то же фиксированное значение. Градиентом функции f(x) называется вектор указывающий направление наиболее быстрого возрастания функции, и, стало быть, ориентированный перпендикулярно линиям уровня.

Если линия уровня определяется уравнением f (x) = c_lx_l+c₂x₂= const , то этот вектор имеет вид

и указывает направление  возрастания функции. Таким образом, с геометрической точки зрения задача максимизации сводится к определению такой точки области D, через которую проходит линия уровня, соответствующая наибольшему из возможных значений. Последнее означает, что для нахождения точки экстремума в задаче линейного программирования мы должны сначала построить линию уровня для некоторого произвольного значения целевой функции. Затем необходимо осуществлять ее параллельное передвижение (так, чтобы она оставалась перпендикулярной вектору с) до тех пор, пока не достигнем такой точки области допустимых планов D, из которой смещение в направлении вектора с было бы невозможно. Такой точкой будет являться точка пересечения прямых 8x₁ + 2x₂ = 80 и х₂ = 0. Найдем координаты этой точки.

x₂ = 0

x₁ = 80/8 = 10

Таким образом, оптимальным планом выпуска изделий будет являться план: X^*(10;0), а максимальная прибыль будет равна = 40 = max

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

С точки зрения обеспечения рациональности и наглядности вычислительного процесса выполнение алгоритма симплекс-метода удобно оформлять в виде последовательности таблиц.

Шаг 1. Приведем задачу к  канонической форме. Для реализации шага в ограничения задачи вводятся дополнительные переменные.

= 4x₁ + x₂ + 0·x₃ + 0·x₄ +  0·x₅ → max;

Шаг 2. Исходная симплекс-таблица  соответствует первоначальному  допустимому базисному решению. В качестве такового проще всего взять базисное решение, в котором основными являются дополнительные переменные x₃, x₄, x_5.

В левом столбце записываются основные (базисные) переменные, в первой строке таблицы перечисляются все  переменные задачи. Крайний правый столбец содержит свободные члены системы ограничений b₁, b₂, ..., b_m. В последней строке таблицы (она называется оценочной) записываются коэффициенты целевой функции, а также значение целевой функции (с обратным знаком) при текущем базисном решении ( ). В рабочую область таблицы (начиная со второго столбца и второй строки) занесены коэффициенты a_ij при переменных системы ограничений.

Таблица 1 - Исходная симплекс-таблица

Таким образом, в данном базисном решении неосновные переменные x₁ и x₂ равны нулю. Базисные переменные отличны от нуля: x₃ = 80, x₄ = 60, x₅ = 40. Данное базисное решение является допустимым. Естественно, что значение целевой функции в этом случае равно нулю, так как в формировании целевой функции участвуют переменные, которые для данного базисного решения являются неосновными.

Шаг 3.  Проверка условия: все c_j ≤ 0. Если НЕТ - осуществляется переход к шагу 4, если ДА - задача решена. Таким образом, на данном шаге проверяется наличие положительных элементов в последней строке симплексной таблицы. Если такие элементы имеются, необходимо продолжать решение.

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

Шаг 4. Выбор разрешающего столбца (переменной, вводимой в базис). Разрешающий столбец выбирается в соответствии со следующим условием:

где r - номер разрешающего столбца.

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

В нашей задаче в качестве разрешающего выберем первый столбец (соответствующий переменной x₁), поскольку в последней строке для этого столбца содержится 4.

Шаг 5. Проверка условия: все a_ir ≤ 0. Если ДА - целевая функция неограниченна и решения нет, если НЕТ - переход к шагу 6.

Таким образом, необходимо проверить элементы разрешающего столбца. Если среди них нет положительных, то задача неразрешима.

В нашем примере все  элементы разрешающего столбца положительны (8, 3 и 1), следовательно, необходимо перейти к шагу 6.

Шаг 6. Выбор разрешающей строки (переменной, выводимой из базиса) по условию:

где s - номер разрешающей строки.

Таким образом, для тех  строк, где элементы разрешающего столбца  положительны, необходимо найти частное  от деления элемента b_i (последний столбец таблицы) на элемент, находящийся в разрешающем столбце. В качестве разрешающей выбирается строка, для которой результат такого деления будет наименьшим.

Для первой строки: D₁ = 80 / 8 = 10.

Для второй строки: D₂ = 60 / 3 = 20.

Для третьей строки: D₃ = 40 / 1 = 40.

Наименьший результат  деления - в первой строке, значит именно эту строку мы выбираем в качестве разрешающей, т.е. исключать из базисного решения будем переменную x₃. Элемент, стоящий на пересечении разрешающей строки и разрешающего столбца, называется разрешающим элементом. В нашем случае таковым является 8 (элемент, стоящий на пересечении первой строки и первого столбца).

Шаг 7. Пересчет элементов симплекс-таблицы (переход к новому базисному решению). Порядок пересчета различных элементов таблицы несколько отличается.

Для элементов  разрешающей строки используются следующие формулы:

где s - номер разрешающей  строки,

r - номер разрешающего столбца, 

, - новые значения пересчитываемых элементов,

a_sj, b_s - старые значения пересчитываемых элементов,

a_sr - старое значение разрешающего элемента.

Таким образом, при пересчете  элементов разрешающей строки каждый ее элемент делится на разрешающий  элемент.

Еще проще пересчитать элементы разрешающего столбца. Все они (кроме разрешающего элемента) становятся равными нулю:

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

где , , , - новые значения пересчитываемых элементов,

a_ij, b_i, c_j, L - старые значения пересчитываемых элементов.

Применение правила прямоугольника проиллюстрируем, используя таблицу 2. Пересчитаем элемент a₃₂ (в исходной симплекс-таблице его значение равно 4). В таблице 2 можно видеть прямоугольник (прочерчен пунктиром), соединяющий четыре элемента, участвующих в пересчете:

Аналогичным образом  пересчитываются остальные элементы.

Таблица 2 - Исходная симплекс-таблица  с выделенными разрешающей строкой  и столбцом, а также с иллюстрацией к применению правила прямоугольника

По окончании пересчета  осуществляется возврат к шагу 3.

Полностью результат  пересчета для нашего примера  можно видеть в таблице 3.

Таблица 3 - Симплекс-таблица (второе базисное решение)

Рассмотрим последнюю  строку таблицы 3. В ней нет положительных элементов. значит, полученное решение является оптимальным. Оно, что естественно, совпадает с решением, полученным для этой же задачи при помощи графического метода.

Базисное решение содержит х₁ = 10, х₂ = 0. Максимальное значение функции прибыли равно 40 ден. ед..

Экономический смысл  последней симплекс-таблицы заключается в следующем: Оптимальный план выпуска составляет выпуск 10 изделий х₁. Изделие х₂ целесообразнее не выпускать. При этом сырье первого вида используется полностью, остатки сырья второго и третьего вида  - по 30 единиц каждого. Увеличение запасов сырья второго и третьего вида не повлияет на значение целевой функции, лишь увеличит остаток каждого вида сырья, увеличение запасов сырья первого вида на 1 увеличит значение целевой функции на 1/8.

Задача линейного программирования, двойственная задаче исходной задаче, будет иметь вид:

Оптимальное решение  этой задачи имеет вид: = 1/2, = 0, = 0,

= 40 = min.

Двойственные оценки отражают сравнительную  дефицитность факторов производства. Чем выше величина оценки , тем выше дефицитность i-го ресурса. Факторы, получившие нулевые оценки, не являются дефицитными и не ограничивают производство. Дефицитным является ресурс первого типа, ресурсы второго и третьего типов дефицитными не являются.

Задание 2

Постановка  задачи

Составить модель транспортной задачи и с помощью распределительного метода найти оптимальный план перевозок  от трех поставщиков с различными мощностями к трем потребителям с разным спросом.

Мощности поставщиков: (30 40 20)

Спрос потребителей: (40 40 30)

Матрица норм затрат А =

Решение

Сформулируем ЗЛП:

Распределительный метод  является одним из вариантов базового симплексного метода. Поэтому идея распределительного метода (как и  симплексного) содержит такие же три существенных момента.

Прежде всего отыскивается какое-то решение задачи — исходный опорный план. Затем посредством  специальных показателей опорный  план проверяется на оптимальность. Если план оказывается не оптимальным, переходят к другому плану. При  этом второй и последующие планы должны быть лучше предыдущего. Так за несколько последовательных переходов от не оптимального плана приходят к оптимальному.

Проверим необходимое  и достаточное условие разрешимости задачи.  
 ∑a  = 30 + 40 + 20 = 90

∑b = 40 + 40 + 20 = 110

Условие баланса не соблюдается. Запасы не равны потребностям. Следовательно, модель транспортной задачи является открытой. Для приведения задачи к закрытому виду введем фиктивного поставщика №4 с мощностью, равной 20. Все издержки по доставке продукции от данного поставщика любому потребителю принимаем равными нулю.

Маршруты доставки продукции  от фиктивного поставщика A₄ к потребителям мы будем рассматривать в последнюю очередь. Скорее всего, это позволит получить более рентабельное начальное решение.

Согласно условию задачи составим таблицу. (тарифы c_ij располагаются в нижнем правом углу ячейки)

Начальный опорный план получим с помощью метода минимальной  стоимости. Минимальный элемент матрицы тарифов находится в ячейке A₃B₃ и равен 3, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A₃ к потребителю B₃ наиболее рентабельный.

Запасы поставщика A₃ составляют 20 единиц продукции. Потребность потребителя B3₁ составляет 30 единиц продукции.

От поставщика A₃ к потребителю B₃ будем доставлять min = { 20 , 30 } = 20 единиц продукции.

Разместим в ячейку A₃B₃ значение равное 20.

Мы полностью исчерпали мощности потребителя А₃ Вычеркиваем строку 3 таблицы, т.е исключаем его из дальнейшего рассмотрения.

Элемент, равный 4, встречается  в четырех строках таблицы, Возьмем  в качестве минимального элемент, стоящий  в ячейке A₂B₂. Запасы поставщика A₂ составляют 40 единиц продукции, потребности потребителя B₂ – тоже 40 единиц продукции, таким образом, мы полностью удовлетворим потребность потребителя B₂ и исчерпаем мощность потребителя A_2. Вычеркиваем вторую строку и второй столбец из дальнейшего рассмотрения.

Минимальный элемент  матрицы тарифов находится в  ячейке A₁B₃ и равен 4, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A₁ к потребителю B₃ наиболее рентабельный.

Запасы поставщика A₁ составляют 30 единиц продукции. Потребность потребителя B₃ составляет 30 из которых 20 единиц уже удовлетворена.

От поставщика A₁ к потребителю B₃ будем доставлять min = { 30 , 10 } = 10 единиц продукции.

Разместим в ячейку A₁B₃ значение равное 10

Мы полностью удовлетворили  потребность потребителя B₃. Вычеркиваем столбец 3 таблицы, т.е исключаем его из дальнейшего рассмотрения.

В таблице остался  один потребитель, у которого не удовлетворены потребности.

Разместим в ячейку А₁В₁ значение равное 20 и чтобы полностью удовлетворить потребность потребителя В₁ – в ячейку А₄В₁ – значение 20.

Заполненные ячейки будем  называть базисными, остальные - свободными.

Проверим полученный опорный план на невырожденность. Количество заполненных клеток N должно удовлетворять условию N=n+m-1 . В нашем случае N=5, n+m=4+3=7 , план является вырожденным. Прежде чем двигаться дальше выберем одну незаполненную клетку и запишем в нее число ноль, осуществим так называемую нуль-загрузку. Выбирать следует такие клетки, которые не образуют циклов с другими заполненными клетками, иначе опорного плана не получится.

Вычислим общие затраты  на перевозку всей продукции.

P_нач = 5·20 + 4·10 + 4·40 + 3·20 + 0·20 + 6·0 = 100 + 40 +160+60 = 360

Для каждой свободной клетки таблицы задачи можно построить единственный цикл, который содержит эту клетку и часть клеток, занятых опорным решением. Обозначив этот цикл и осуществив сдвиг (перераспределение груза) по циклу на величину  можно получить новое опорное решение Х₂. Определим, как изменится целевая функция при переходе к новому опорному решению. При сдвиге на единицу груза по циклу, соответствующему клетке (l, m), приращение целевой функции Δ_lmравно разности двух сумм:

где - сумма стоимостей перевозок единиц груза в нечетных клетках цикла, отмеченных знаком “+” ; - сумма стоимостей перевозок единиц груза в четных клетках цикла, отмеченных знаком “-”. В клетках, отмеченных знаком “+”, величины груза прибавляются, что приводит к увеличению значения целевой функции F(X), а в клетках, отмеченных знаком “-”, величины груза уменьшаются, что приводит к уменьшению значения целевой функции. Если разность сумм для свободной клетки ( l, m ) меньше нуля, т.е. Δ _lm< 0, то перераспределение величины θ по соответствующему циклу приведет к уменьшению значения F(X) на величину θ•Δ_lm, т.е. опорное решение можно улучшить. Если же величины Δ_lm, называемые оценками, для всех свободных клеток таблицы транспортной задачи неотрицательны, то значение целевой функции нельзя уменьшить и опорное решение оптимально. Следовательно, признаком оптимальности распределительного метода является условие

Для каждого нового опорного решения вычисление оценок начинается с первой свободной клетки таблицы. Очередность проверяемых свободных  клеток целесообразно устанавливать  в порядке возрастания стоимости  перевозок c_ij ,так как решается задача на нахождение минимума.