Решение задач линейного программирования симплекс-методом

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

Определим максимальное значение целевой функции F (X) = 5x₁ + 5x₂ + 11x₃+9 при следующих условиях — ограничений.

При вычислениях значение Fc = 9 временно не учитываем. x₁ + x₂ + x₃ + x₄?0 7x₁ + 5x₂ + 3x₃ + 2x₄?0 3x₁ + 5x₂ + 10x₃ + 15x₄?0.

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (?) вводим базисную переменную x₅. В 2-м неравенстве смысла (?) вводим базисную переменную x₆. В 3-м неравенстве смысла (?) вводим базисную переменную x₇.

1x₁ + 1x₂ + 1x₃ + 1x₄ + 1x₅ + 0x₆ + 0x₇ = 0 7x₁ + 5x₂ + 3x₃ + 2x₄ + 0x₅ + 1x₆ + 0x₇ = 0 3x₁ + 5x₂ + 10x₃ + 15x₄ + 0x₅ + 0x₆ + 1x₇ = 0 Матрица коэффициентов A = a (ij) этой системы уравнений имеет вид:

Таблица 1.

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

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

Решим систему уравнений относительно базисных переменных: x₅, x₆, x₇

Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,0,0,0,0).

Базисное решение называется допустимым, если оно неотрицательно.

Таблица 2.

Переходим к основному алгоритму симплекс-метода.

Итерация № 0. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

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

Вычислим значения D_i по строкам как частное от деления: b_i / a_i3 и из них выберем наименьшее: min (0: 1, 0: 3, 0: 10) = 0.

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

Таблица 3.

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы. Вместо переменной x₅ в план 1 войдет переменная x₃. Строка, соответствующая переменной x₃ в плане 1, получена в результате деления всех элементов строки x₅ плана 0 на разрешающий элемент РЭ=1 На месте разрешающего элемента в плане 1 получаем 1. В остальных клетках столбца x₃ плана 1 записываем нули. Таким образом, в новом плане 1 заполнены строка x₃ и столбец x₃. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ. НЭ = СЭ — (А*В)/РЭ СТЭ — элемент старого плана, РЭ — разрешающий элемент (1), А и В — элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ. Представим расчет каждого элемента в виде таблицы:

Таблица 4.

Получаем новую симплекс-таблицу:

Таблица 5.

1. Проверка критерия оптимальности. Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи. Окончательный вариант симплекс-таблицы:

Таблица 6.

Оптимальный план можно записать так: x₃ = 0 F (X) = 11*0 + 9 = 9.