Найти решение ЗЛП, используя симплекс-метод.
Для изготовления четырех видов продукции используется три вида сырья. Запасы, нормы его расхода и цена каждого продукта приведены в таблице. Требуется определить план производства продукции, обеспечивающий максимальную прибыль.
Решение
Пусть необходимо выпускать продукции А – х1, продукции Б – х2, продукции В – х3, тогда ограничения
по сырью I:x1+2x2+x3≤144,
по сырью II:3x1+2x2+3x3≤180,по сырью III:4x1+x2+5x3≤200,
по неотрицательности переменных:
х1>0,
х2>0,
х3>0.
Прибыль определяется как F(X)=5x1+4x2+6x3, которую необходимо максимизировать.
Математическая модель задачи имеет вид:
F(X) = 5x1+4x2+6x3 → max
x1+2x2+x3≤144,3x1+2x2+3x3≤180,4x1+x2+5x3≤200,
х1>0,
х2>0,
х3>0.
Решим прямую задачу линейного программирования симплексным методом с использованием симплексной таблицы.
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x4. В 2-м неравенстве смысла (≤) вводим базисную переменную x5. В 3-м неравенстве смысла (≤) вводим базисную переменную x6.
x1+2x2+x3+x4 = 144
3x1+2x2+3x3+x5 = 180
4x1+x2+5x3+x6 = 200
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
A = 1 2 1 1 0 0
3 2 3 0 1 0
4 1 5 0 0 1
Базисные переменные – это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x4, x5, x6
Полагая, что свободные переменные равны 0, получим первый опорный план:
X0 = (0,0,0,144,180,200)
Базисное решение называется допустимым, если оно неотрицательно.
Базис B x1 x2 x3 x4 x5 x6
x4 144 1 2 1 1 0 0
x5 180 3 2 3 0 1 0
x6 200 4 1 5 0 0 1
F(X0) 0 -5 -4 -6 0 0 0
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1
. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai3и из них выберем наименьшее:
min (144 : 1 , 180 : 3 , 200 : 5 ) = 40
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (5) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 x6 min
x4 144 1 2 1 1 0 0 144
x5 180 3 2 3 0 1 0 60
x6 200 4 1 5 0 0 1 40
F(X1) 0 -5 -4 -6 0 0 0
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x6 в план 1 войдет переменная x3.
Строка, соответствующая переменной x3 в плане 1, получена в результате деления всех элементов строки x6 плана 0 на разрешающий элемент РЭ=5. На месте разрешающего элемента получаем 1
Задать вопрос
на новый заказ в Автор24.
