Оптимальное решение двойственной задачи

Задание 1

Данные исходной задачи запишем в виде таблицы (таблица 1).

Таблица 1

Предположим, что будет использовано х₁ сырья S₁ для изготовления продукции А₁, х₂ сырья для продукции вида А₂. Тогда общий доход от реализации составит 4х₁ + 8х₂.

Так как общее количество сырья S₁ не может превышать 10, то должно выполняться следующее неравенство: х₁+х₂? 10

Аналогичные рассуждения относительно возможного использования остального количества сырья приведут к следующим неравенствам:

х₁ + 4х₂? 28;

3х₁+х₂? 24.

При этом, так как количество продукции не может быть отрицательным, то: х₁? 0, х₂? 0

Пусть F — прибыль предприятия, так как по условию необходимо составить план производства двух видов продукции, обеспечивающий максимальную прибыль, следовательно, функция F, при условии, что изготовлено х₁ единиц продукции вида А₁ и х₂ единиц продукции вида А₂ будет максимизироваться:

издержка теневой цена прибыль

F = 4х₁ + 8х₂ > max.

Таким образом, мы приходим к следующей математической задаче:

Дана система:

(1)

трех линейных неравенств с двумя неизвестными х_i (i=1,2). И линейная функция относительно этих же переменных:

F = 4х₁ + 8х₂ (2)

требуется среди всех неотрицательных решений системы неравенств (2), найти такое, при котором функция (3) примет максимальное значение.

Найдем решение сформулированной задачи, используя ее геометрическую интерпретацию. Сначала определим многоугольник решений. Для этого в неравенствах системы ограничений и условиях не отрицательности переменных знаки неравенств заменим на знаки точных равенств и найдем соответствующие прямые.

Прямые S1 — S3, изображены на рисунке 1.

Каждая из построенных прямых делит плоскость на две полуплоскости. Координаты точек одной полуплоскости удовлетворяют исходному неравенству, а другой — нет. Определим искомую полуплоскость через точку О (0;0).

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

Рисунок 1 — Многоугольник решений Как видно из рисунка 1, многоугольником решений является пятиугольник ОАВСD.

Таким образом, среди точек пятиугольника ОАВСD нам нужно найти такие, в которых функция F = 4х₁ + 8х₂ принимает максимальное значение. Для нахождения этих точек построим нулевую линию уровня (F₀) 4х₁ + 8х₂ = 0 и вектор N = (4;8).

Передвигая данную прямую параллельно самой себе в направлении вектора N, видим, что ее последней точкой с многоугольником решений задачи является точка В. Следовательно, в этой точке функция F принимает максимальное значение. Так как В — точка пересечения прямых S1 и S2, то ее координаты удовлетворяют уравнениям этих прямых:

Решив эту систему уравнений мы получили: х₁ = 4 и х₂ = 6.

Таким образом, максимальное значение функции F_max = 4*4+8*6 = 16 + 48 = 64.

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

х₁, х₂? 0

F = 4х₁ + 8х₂

Запишем эту задачу в форме основной задачи ЛП:

Для этого перейдем от ограничений неравенств — к ограничениям равенствам.

Введем 3 дополнительные переменные, в результате чего ограничения запишутся в виде систем ограничений:

Преобразованную систему ограничений запишем в векторной форме:

Поскольку среди векторов Р₁-Р₅ имеются 3 единичных вектора, для данной задачи можно непосредственно записать опорный план.

Таковым является план Х = (0;0;0;10;28;24), определяемый системой трехмерных единичных векторов Р₃, Р₄, Р₅, которые образуют базис трехмерного векторного пространства.

Составим симплексную таблицу для I итерации (таблица 2), подсчитав значения F₀, z_i — c_i и проверяем исходный план на оптимальность.

F₀ = (c, P₀); z₁ = (c, P₁) = 0; z₂ = (c, P₂) = 0; z₃ = (c, P₃) = 0;

z₄ = (c, P₄) = 0; z₅ = (c, P₅) = 0;

z₁ — c₁ = 0 — 4 = -4; z₂ — c₂ = 0 — 8 = -8.

Для векторов базиса z_i — c_i = 0.

Таблица 2

Таким образом, по 4 строке таблицы 2 видно, что план не оптимален, т.к. значения z_i — c_i — отрицательны.

Далее определяем вектор, подлежащий исключению из базиса. Для этого находим Q_0min (b_i/a_i1) для a_i1>0 и Q_0min (b_i/a_i2) для a_i2>0.

Таким образом, Q_0min (b_i/a_i1) = min (10/1;28/1;24/4) = 24/4, а Q_0min (b_i/a_i2)= min (10/1;28/4;24/1) = 28/4.

Min (24/4;28/4) = 28/4.

Таким образом, мы нашли разрешающий элемент, находящийся на пересечении 2-ой строки и столбца вектора Р₂.

Следовательно, вектор Р₄ подлежит исключению из базиса.

Столбец вектора Р₂ и вторая строка являются направляющими.

Далее, составляем таблицу для итерации II (таблица 3).

Сначала заполняем строку вектора вновь введенного в базис. Элементы этой строки таблицы 3 получаются из соответствующих элементов таблицы 2 делением на разрешающий элемент.

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

Данный цикл продолжается до тех пор, пока все значения z_i — c_i — не станут положительными.

Таким образом, в таблице 3 мы запишем все итерации вычислительного процесса.

Таблица 3

Итак, среди значений z_i — c_i нет отрицательных, следовательно, опорный план оптимален и F_max = 64.

Прямая задача имеет вид:

х₁, х₂? 0

F = 4х₁ + 8х₂

Хопт. = (4; 6).

Max F = 64.

Составим двойственную модель и с помощью теорем двойственности найдем оптимальное решение двойственной модели:

Двойственная модель:

Z = 10y₁ + 28y₂ + 24y₃> min

Так как мы уже нашли решение исходной задачи (таблица 3), следовательно, мы нашли и решение двойственной задачи:

y₁ = 2,67; y₂ = 1,33; y₃ = 0. (итерация III в симплекс-таблице 3).

Таким образом оптимальное решение двойственной задачи = y_опт(2,67;1,33;0).

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

Z = 10*2,67+28*1,33+24*0 = 26,7+37,3+0 = 64

Итак, Z = F = 64.

Задание 2

Запишем и преобразуем матрицу коэффициентов системы.

>>

Таким образом, мы получили систему ограничений с единичным базисом (х₃, х₄, х₅):

Отбрасывая базисные переменные, получим стандартную задачу ЛП:

Выразим функцию цели через свободные неизвестные х₁ и х₂. Имеем:

Тогда:

Таким образом, ц_min вспомогательной задачи не равно 0, следовательно, исходная задача не обладает опорным решением (несовместна).

Задание 3

Таблица 4 Исходные данные задачи

Спрос = 20+20+20+13+27 = 100

Предложение = 53+17+30 = 100

Таким образом, данная ТЗ — закрытая.

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

Таблица 5

n+m -1 =3+5−1 = 7 — не соответствует числу заполненных клеток Общие транспортные издержки равны:

Z₁ = 20*13+20*4+17*6+3*10+13*3+20*18+7*29 = 260+80+102+30+39+360+203 = 1074

Проверим составленный план на оптимальность методом потенциалов.

Рассчитаем потенциалы, исходя из того, что потенциал строки А1 = 0 (таблица 6).

Таблица 6

Далее, рассчитаем теневые цены (таблица 7 — теневые цены серым цветом).

Таблица 7

Наличие теневых цен означает не оптимальность имеющегося плана, следовательно, для улучшения плана намечаем маршрут с наименьшей отрицательной теневой ценой и для этого маршрута определяем цикл перераспределения. Объем перевозимого груза численно равен минимальному значению из тех объемов груза, которые указаны в клетках со знаком минус. Таким образом,? (А2, В5) = min (17;7) = 7.

Итак, составляем новый план (таблица 8).

Данный цикл длится до тех пор, пока все теневые цены не станут положительными.

Таблица 8

Общие транспортные издержки равны:

Z₂ = 20*13+20*4+10*6+10*10+13*3+20*18+7*9 = 260+80+60+100+39+360+63 = 962

В таблице 8 все теневые цены положительны, следовательно, план оптимален.