Для изготовления трех видов изделий А, В и С используется токарное, фрезерное, сварочное и шлифовальное оборудование. Затраты времени на обработку одного изделия для каждого из типов оборудования приведены в таблице.
Тип оборудования Затраты времени на обработку одного изделия, час. Общий фонд рабочего времени оборудования
А В С
Токарное 2 4 5 120
Фрезерное 1 8 6 280
Сварочное 7 4 5 240
Шлифовальное 4 6 7 360
Прибыль 10 14 12
Требуется определить, сколько изделий и какого вида следует изготовить предприятию, чтобы прибыль от их реализации была максимальной.
Решение
Пусть изделий А необходимо выпускать х1, изделий В – х2, изделий С – х3, тогда ограничения
по токарному оборудованию:2x1+4x2+5x3≤120,
по фрезерному оборудованию:x1+8x2+6x3≤280,
по сварочному оборудованию:7x1+4x2+5x3≤240,
по шлифовальному оборудованию:4x1+6x2+7x3≤360,
по неотрицательности переменных:
х1>0,
х2>0,
х3>0,
х4>0.
Прибыль определяется как функции F(X)=10x1+14x2+12x3, которую необходимо максимизировать.
Математическая модель задачи имеет вид:
F(X)=10x1+14x2+12x3 → max
2x1+4x2+5x3≤120,
x1+8x2+6x3≤280,
7x1+4x2+5x3≤240,
4x1+6x2+7x3≤360,
х1>0,
х2>0,
х3>0,
х4>0.
Решим прямую задачу линейного программирования симплексным методом с использованием симплексной таблицы.
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x4. В 2-м неравенстве смысла (≤) вводим базисную переменную x5. В 3-м неравенстве смысла (≤) вводим базисную переменную x6. В 4-м неравенстве смысла (≤) вводим базисную переменную x7.
2x1+4x2+5x3+x4 = 120x1+8x2+6x3+x5 = 2807x1+4x2+5x3+x6 = 2404x1+6x2+7x3+x7 = 360
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
2 4 5 1 0 0 0
1 8 6 0 1 0 0
7 4 5 0 0 1 0
4 6 7 0 0 0 1
Базисные переменные – это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x4, x5, x6, x7
Полагая, что свободные переменные равны 0, получим первый опорный план:
X0 = (0,0,0,120,280,240,360)
Базисное решение называется допустимым, если оно неотрицательно.
Базис B x1 x2 x3 x4 x5 x6 x7
x4 120 2 4 5 1 0 0 0
x5 280 1 8 6 0 1 0 0
x6 240 7 4 5 0 0 1 0
x7 360 4 6 7 0 0 0 1
F(X0) 0 -10 -14 -12 0 0 0 0
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1
. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai2и из них выберем наименьшее:
min (120 : 4 , 280 : 8 , 240 : 4 , 360 : 6 ) = 30
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (4) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 x6 x7 min
x4 120 2 4 5 1 0 0 0 30
x5 280 1 8 6 0 1 0 0 35
x6 240 7 4 5 0 0 1 0 60
x7 360 4 6 7 0 0 0 1 60
F(X1) 0 -10 -14 -12 0 0 0 0
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x4 в план 1 войдет переменная x2.
Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x4 плана 0 на разрешающий элемент РЭ=4
Задать вопрос
на новый заказ в Автор24.
