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

Предположим, что будет использовано х₁ сырья 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