Решить задачу оптимального планирования выпуска продукции симплексным методом при следующих условиях.
Для изготовления двух видов продукции используются три вида сырья. При производстве единицы продукции первого вида затрачивается 5 кг сырья первого вида, 3 кг сырья второго вида и 2 кг сырья третьего вида. При производстве единицы продукции второго вида затрачивается 2 кг сырья первого вида, 3 кг сырья второго вида и 3 кг сырья третьего вида. Запасы сырья первого вида составляют 505 кг, второго - 393 кг, третьего - 348 кг. Прибыль от реализации единицы продукции первого вида составляет 7 руб., от реализации единицы продукции второго вида - 4 руб.
Решение
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 7x1+4x2 при следующих условиях-ограничений.
5x1+2x2≤505
3x1+3x2≤393
2x1+3x2≤348
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x3. В 2-м неравенстве смысла (≤) вводим базисную переменную x4. В 3-м неравенстве смысла (≤) вводим базисную переменную x5.
5x1+2x2+x3 = 505
3x1+3x2+x4 = 393
2x1+3x2+x5 = 348
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
EQ A = \b(\a \al \co5 \hs3 (5;2;1;0;0;3;3;0;1;0;2;3;0;0;1))
Решим систему уравнений относительно базисных переменных: x3, x4, x5
Полагая, что свободные переменные равны 0, получим первый опорный план:
X0 = (0,0,505,393,348)
Базисное решение называется допустимым, если оно неотрицательно.
Базис B x1 x2 x3 x4 x5
x3 505 5 2 1 0 0
x4 393 3 3 0 1 0
x5 348 2 3 0 0 1
F(X0) 0 -7 -4 0 0 0
Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю
.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
min (505 : 5 , 393 : 3 , 348 : 2 ) = 101
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (5) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 min
x3 505 5 2 1 0 0 101
x4 393 3 3 0 1 0 131
x5 348 2 3 0 0 1 174
F(X1) 0 -7 -4 0 0 0
Формируем следующую часть симплексной таблицы. Вместо переменной x3 в план 1 войдет переменная x1.
Строка, соответствующая переменной x1 в плане, получена в результате деления всех элементов строки x3 плана 0 на разрешающий элемент РЭ=5. На месте разрешающего элемента получаем 1. В остальных клетках столбца x1 записываем нули.
Таким образом, в новом плане заполнены строка x1 и столбец x1. Все остальные элементы нового плана, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (5), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ
Задать вопрос
на новый заказ в Автор24.
