Решить задачу линейного программирования симплекс-методом.
Предприятие располагает несколькими группами невзаимозаменяемого оборудования, на котором может быть изготовлено три наименования изделий. Составить план производства изделий, обеспечивающий максимальную прибыль реализуемой продукции.
Трудоемкость изделий, фонд полезного времени каждой группы оборудования и прибыль (руб.) от реализации единицы готового изделия каждого вида приведены в следующих таблицах.
Решение
Пусть необходимо выпускать изделий 1 – х1, изделий 2 – х2, изделий 3 – х3, тогда ограничения
по оборудованию А:6x1+x2≤60,по оборудованию Б:x1+5x2+x3≤80,по оборудованию В:3x2+4x3≤80,по оборудованию Г:2x1+3x2+2x3≤50,по оборудованию Д:3x1+4x3≤56,
по неотрицательности переменных:
х1>0,
х2>0,
х3>0.
Прибыль определяется как F(X)=6x1+5x2+7x3, которую необходимо максимизировать.
Математическая модель имеет вид:
F(X) = 6x1+5x2+7x3 → max
6x1+x2≤60,x1+5x2+x3≤80,3x2+4x3≤80,2x1+3x2+2x3≤50,3x1+4x3≤56,
х1>0,
х2>0,
х3>0.
Решим прямую задачу линейного программирования симплексным методом с использованием симплексной таблицы.
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x4. В 2-м неравенстве смысла (≤) вводим базисную переменную x5. В 3-м неравенстве смысла (≤) вводим базисную переменную x6. В 4-м неравенстве смысла (≤) вводим базисную переменную x7. В 5-м неравенстве смысла (≤) вводим базисную переменную x8.
6x1+x2+x4 = 60x1+5x2+x3+x5 = 803x2+4x3+x6 = 802x1+3x2+2x3+x7 = 503x1+4x3+x8 = 56
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
6 1 0 1 0 0 0 0
1 5 1 0 1 0 0 0
0 3 4 0 0 1 0 0
2 3 2 0 0 0 1 0
3 0 4 0 0 0 0 1
Базисные переменные – это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x4, x5, x6, x7, x8
Полагая, что свободные переменные равны 0, получим первый опорный план:
X0 = (0,0,0,60,80,80,50,56)
Базисное решение называется допустимым, если оно неотрицательно.
Базис B x1 x2 x3 x4 x5 x6 x7 x8
x4 60 6 1 0 1 0 0 0 0
x5 80 1 5 1 0 1 0 0 0
x6 80 0 3 4 0 0 1 0 0
x7 50 2 3 2 0 0 0 1 0
x8 56 3 0 4 0 0 0 0 1
F(X0) 0 -6 -5 -7 0 0 0 0 0
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1
. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai3и из них выберем наименьшее:
min (- , 80 : 1 , 80 : 4 , 50 : 2 , 56 : 4 ) = 14
Следовательно, 5-ая строка является ведущей.
Разрешающий элемент равен (4) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 x6 x7 x8 min
x4 60 6 1 0 1 0 0 0 0 -
x5 80 1 5 1 0 1 0 0 0 80
x6 80 0 3 4 0 0 1 0 0 20
x7 50 2 3 2 0 0 0 1 0 25
x8 56 3 0 4 0 0 0 0 1 14
F(X1) 0 -6 -5 -7 0 0 0 0 0
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x8 в план 1 войдет переменная x3.
Строка, соответствующая переменной x3 в плане 1, получена в результате деления всех элементов строки x8 плана 0 на разрешающий элемент РЭ=4
Задать вопрос
на новый заказ в Автор24.
