Леспромхоз имеет древесину трех видов в количествах: 1 – 1000 м3, 2 – 500 м3, 3 – 700 м3, для изготовления изделий А, В, С и D. Нормы расхода древесины в м3 на изготовление единицы каждого изделия и прибыль от реализации единицы изделия даны в таблице.
Построить модель проблемной ситуации. Определить оптимальный план по показателю общая прибыль от реализации изделий. Дать рекомендации по дополнительной эффективности.
Решение
Пусть необходимо изготовить изделий А – х1, изделий В – х2, изделий С – х3, изделий D – х4, тогда ограничения
по сырью 1:0.1x1+0.15x2+0.2x3+0.25x4≤1000,по сырью 2:0.2x1+0.4x2+0.3x3+0.1x4≤500,по сырью 3:0.4x1+0.5x2+0.1x3+0.2x4≤700,
по неотрицательности переменных:
х1>0,
х2>0,
х3>0,
х4>0.
Удельная прибыль определяется как F(X)=10x1+20x2+30x3+10x4, которую необходимо максимизировать.
Математическая модель задачи имеет вид:
F(X) = 10x1+20x2+30x3+10x4 → max
0.1x1+0.15x2+0.2x3+0.25x4≤1000,0.2x1+0.4x2+0.3x3+0.1x4≤500,0.4x1+0.5x2+0.1x3+0.2x4≤700,
х1>0,
х2>0,
х3>0,
х4>0.
Решим задачу линейного программирования симплексным методом с использованием симплексной таблицы.
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x5. В 2-м неравенстве смысла (≤) вводим базисную переменную x6. В 3-м неравенстве смысла (≤) вводим базисную переменную x7.
0.1x1+0.15x2+0.2x3+0.25x4+x5 = 10000.2x1+0.4x2+0.3x3+0.1x4+x6 = 5000.4x1+0.5x2+0.1x3+0.2x4+x7 = 700Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
0.1 0.15 0.2 0.25 1 0 0
0.2 0.4 0.3 0.1 0 1 0
0.4 0.5 0.1 0.2 0 0 1
Базисные переменные – это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x5, x6, x7
Полагая, что свободные переменные равны 0, получим первый опорный план: X0 = (0,0,0,0,1000,500,700)
Базисное решение называется допустимым, если оно неотрицательно.
Базис B x1 x2 x3 x4 x5 x6 x7
x5 1000 0.1 0.15 0.2 0.25 1 0 0
x6 500 0.2 0.4 0.3 0.1 0 1 0
x7 700 0.4 0.5 0.1 0.2 0 0 1
F(X0) 0 -10 -20 -30 -10 0 0 0
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1
. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai3и из них выберем наименьшее:
min (1000 : 0.2 , 500 : 0.3 , 700 : 0.1 ) = 1666.667
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (0.3) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 x6 x7 min
x5 1000 0.1 0.15 0.2 0.25 1 0 0 5000
x6 500 0.2 0.4 0.3 0.1 0 1 0 1666.67
x7 700 0.4 0.5 0.1 0.2 0 0 1 7000
F(X1) 0 -10 -20 -30 -10 0 0 0
4
Задать вопрос
на новый заказ в Автор24.
