Составьте модель задачи и решите ее симплексным методом
Предприятие выпускает три вида продукции, уровень выпуска ее лимитируется ограниченностью имеющихся в распоряжении предприятия ресурсов (сырья, материалов, оборудования).
Предприятие заинтересовано в определении такого уровня выпуска продукции по видам, при котором достигает максимума ее общая стоимость. Норма затрат ресурсов и стоимость единицы продукции каждого вида указаны в таблице 1:
Решение
Пусть необходимо производить продукции I – х1, продукции II – х2, продукции III – х3, тогда ограничения
по сырью:5x1+7x2+4x3≤860,по материалам:5x1+2x2+x3≤300,по оборудованию:2x1+x2+x3≤200,
по неотрицательности переменных:
х1>0,
х2>0,
х3>0.
Стоимость определяется как F(X)=18x1+12x2+8x3, которую необходимо максимизировать.
Математическая модель имеет вид:
F(X) = 18x1+12x2+8x3 → max
5x1+7x2+4x3≤860,5x1+2x2+x3≤300,2x1+x2+x3≤200,
х1>0,
х2>0,
х3>0.
Решим задачу линейного программирования симплексным методом с использованием симплексной таблицы.
Определим максимальное значение целевой функции Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x4
. В 2-м неравенстве смысла (≤) вводим базисную переменную x5. В 3-м неравенстве смысла (≤) вводим базисную переменную x6.
5x1+7x2+4x3+x4 = 8605x1+2x2+x3+x5 = 3002x1+x2+x3+x6 = 200Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
A = 5 7 4 1 0 0
5 2 1 0 1 0
2 1 1 0 0 1
Базисные переменные – это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x4, x5, x6
Полагая, что свободные переменные равны 0, получим первый опорный план: X0 = (0,0,0,860,300,200)
Базисное решение называется допустимым, если оно неотрицательно.
БП B x1 x2 x3 x4 x5 x6
x4 860 5 7 4 1 0 0
x5 300 5 2 1 0 1 0
x6 200 2 1 1 0 0 1
∆ 0 -18 -12 -8 0 0 0
Переходим к симплекс-преобразованиям.
Ключевой столбец выбираем по наименьшему отрицательному элементу индексной строки.
Ключевую строку выбираем по наименьшему отношению частного от деления: bi / aij.
Ключевой элемент находится на пересечении ключевого столбца и ключевой строки.
Все вычисления сводим в симплекс-таблицы.
Переход от одной симплекс-таблицы к другой проводим по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, расположенные в вершинах прямоугольника и всегда включающие ключевой элемент КЭ.
НЭ = СтЭ - (А∙В)/КЭ
СтЭ – элемент старого плана,
КЭ – ключевой элемент,
А и В – элементы старого плана, образующие прямоугольник с элементами СтЭ и КЭ.
БП B x1↓ x2 x3 x4 x5 x6 min
x4 860 5 7 4 1 0 0 172
←x5 300 5 2 1 0 1 0 60
x6 200 2 1 1 0 0 1 100
∆ 0 -18 -12 -8 0 0 0
БП B x1 x2↓ x3 x4 x5 x6 min
←x4 560 0 5 3 1 -1 0 112
x1 60 1 2/5 1/5 0 1/5 0 150
x6 80 0 1/5 3/5 0 -2/5 1 400
∆ 1080 0 -24/5 -22/5 0 18/5 0
БП B x1 x2 x3↓ x4 x5 x6 min
x2 112 0 1 3/5 1/5 -1/5 0 560/3
x1 76/5 1 0 -1/25 -2/25 7/25 0 -
←x6 288/5 0 0 12/25 -1/25 -9/25 1 120
∆ 8088/5 0 0 -38/25 24/25 66/25 0
БП B x1 x2 x3 x4 x5 x6
x2 40 0 1 0 1/4 1/4 -5/4
x1 20 1 0 0 -1/12 1/4 1/12
x3 120 0 0 1 -1/12 -3/4 25/12
∆ 1800 0 0 0 5/6 3/2 19/6
Т.к
Задать вопрос
на новый заказ в Автор24.
