Решить задачу оптимального планирования выпуска продукции симплексным методом (при оформлении контрольного задания должны быть выполнены все шаги алгоритма симплексного метода без пропусков промежуточных расчетов).
Для изготовления двух видов продукции используются три вида сырья. При производстве единицы продукции первого вида затрачивается 5 кг сырья первого вида, 5 кг сырья второго вида и 9 кг сырья третьего вида. При производстве единицы продукции второго вида затрачивается 7 кг сырья первого вида, 1 кг сырья второго вида и 5 кг сырья третьего вида. Запасы сырья первого вида составляют 446 кг, второго – 503 кг, третьего – 333 кг. Прибыль от реализации единицы продукции первого вида составляет 10 руб., от реализации единицы продукции второго вида — 12 руб.
Ответ
продукцию первого вида нужно произвести в размере 2,658 единиц, а продукцию второго вида нужно произвести в размере 768,368 единиц
Решение
Имеем задачу линейного программирования
2705102743201
001
10 * x1 + 12 * x2 → max
5 * x1 + 7 * x2 ≤ 446
5 * x1 + 1 * x2 ≤ 503
9 * x1 + 5 * x2 ≤ 333
Решим данную задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (то есть осуществим переход к канонической форме).
В первом неравенстве вводим базисную переменную x3. Во втором неравенстве вводим базисную переменную x4. В третьем неравенстве вводим базисную переменную x5.
5x1+7x2+x3 = 446
5x1+x2+x4 = 503
9x1+5x2+x5 = 333
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
A = 5 7 1 0 0
5 1 0 1 0
9 5 0 0 1
Решим систему уравнений относительно базисных переменных: x3, x4, x5Полагая, что свободные переменные равны 0, получим первый опорный план:
X0 = (0, 0 , 446, 503, 333)
Базис B x1 x2 x3 x4 x5
x3 446 5 7 1 0 0
x4 503 5 1 0 1 0
x5 333 9 5 0 0 1
F(X0) 0 -10 -12 0 0 0
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi / ai2 и из них выберем наименьшее:
min (446/7 ; 503/1 ; 333/5 ) = 446/7 = 63,714
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (7) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 min
x3 446 5 7 1 0 0 63,714
x4 503 5 1 0 1 0 503
x5 333 9 5 0 0 1 66,6
F(X1) 0 -10 -12 0 0 0
Формируем следующую часть симплексной таблицы
. Вместо переменной x3 в план 1 войдет переменная x2.
Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x3 плана 0 на разрешающий элемент РЭ = 7. На месте разрешающего элемента получаем 1. В остальных клетках столбца x2 записываем нули.
Таким образом, в новом плане 1 заполнены строка x2 и столбец x2. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ – (А * В) / РЭ
СТЭ – элемент старого плана,
РЭ – разрешающий элемент (7),
А и В – элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
B x1 x2 x3 x4 x5
446 : 7 5 : 7 7 : 7 1 : 7 0 : 7 0 : 7
503 - (446 • 1):7 5 - (5 • 1):7 1 - (7 • 1):7 0 - (1 • 1):7 1 - (0 • 1):7 0 - (0 • 1):7
333 - (446 • 5):7 9 - (5 • 5):7 5 - (7 • 5):7 0 - (1 • 5):7 0 - (0 • 5):7 1 - (0 • 5):7
0 - (446 • -12):7 -10 - (5 • -12):7 -12 - (7 • -12):7 0 - (1 • -12):7 0 - (0 • -12):7 0 - (0 • -12):7
Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4 x5
x2 63,714 0,714 1 0,143 0 0
x4 439,286 4,286 0 -0,143 1 0
x5 14,429 5,429 0 -0,714 0 1
F(X1) 764,571 -1,429 0 1,714 0 0
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее:
min (63,714 : 0,714 ; 439,286 : 4,286 ; 14,429 : 5,429) = 2,658
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (5,429) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 min
x2 63,714 0,714 1 0,143 0 0 89,2
x4 439,286 4,286 0 -0,143 1 0 102,5
x5 14,429 5,429 0 -0,714 0 1 2,658
F(X2) 764,571 -1,429 0 1,714 0 0
Формируем следующую часть симплексной таблицы
Задать вопрос
на новый заказ в Автор24.
