Предприятие планирует выпуск двух видов продукции I и II, на производство которых расходуется три вида сырья А, В и С. Потребность aij на каждую единицу j-го вида продукции i-го вида сырья, запас bi соответствующего вида сырья и прибыль cj от реализации единицы j-го вида продукции заданы таблицей:
Виды
сырья Виды продукции Запасы
сырья
I II
А 2 2 14
В 1 1 7
С 2 3 18
Прибыль 4 3
Cоставить ЭММ, то есть целевую функцию прибыли Z и соответствующую систему ограничений по запасам сырья, предполагая, что требуется изготовить в сумме не менее 2 единиц обоих видов продукции.
Записать ЭММ в канонической форме.
Составить двойственную задачу.
Решить задачу графоаналитическим методом.
Решить задачу симплекс-методом.
Дать экономическую интерпретацию результатов.
Решение
Обозначим через Х=(х1,х2) – план производства, показывающий какие виды продукции и в каких количествах необходимо производить, где х1 – количество продукции I, х2 – количество продукции 2-го вида. Общий объем прибыли – это целевая функция, которую необходимо максимизировать:
(1)
Составим систему ограничений на сырье и необходимый минимальный объем выпуска продукции:
Чтобы искомый план был реален, наряду с ограничениями на сырье нужно наложить условие неотрицательности на объемы xj выпуска продукции:
(3)
Таким образом (1)-(3) – математическая модель исходной задачи.
2) Запишем ЭММ в каноническом виде, для чего введем дополнительные переменные х3, х4, х5, х6:
Расширенная матрица системы ограничений-равенств данной задачи:
2 2 1 0 0 0 14
1 1 0 1 0 0 7
2 3 0 0 1 0 18
1 1 0 0 0 -1 2
Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x3.
2. В качестве базовой переменной можно выбрать x4.
3. В качестве базовой переменной можно выбрать x5.
4
. В качестве базовой переменной можно выбрать x6.
Получаем новую матрицу:
2 2 1 0 0 0 14
1 1 0 1 0 0 7
2 3 0 0 1 0 18
-1 -1 0 0 0 1 -2
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (3,4,5,6).
Выразим базисные переменные через остальные:
x3 = -2x1-2x2+14x4 = -x1-x2+7x5 = -2x1-3x2+18x6 = x1+x2-2Подставим их в целевую функцию:F(X) = 4x1+3x2
Среди свободных членов bi имеются отрицательные значения, следовательно, полученный базисный план не является опорным.
Вместо переменной x6 следует ввести переменную x2.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
Базис B x1 x2 x3 x4 x5 x6
x3 10 0 0 1 0 0 2
x4 5 0 0 0 1 0 1
x5 12 -1 0 0 0 1 3
x2 2 1 1 0 0 0 -1
F(X0) -6 1 0 0 0 0 3
Выразим базисные переменные через остальные:x3 = -2x6+10x4 = -x6+5x5 = x1-3x6+12x2 = -x1+x6+2Подставим их в целевую функцию:F(X) = 4x1+3(-x1+x6+2)илиF(X) = x1+3x6+6x3+2x6=10x4+x6=5-x1+x5+3x6=12x1+x2-x6=2
При вычислениях значение Fc = 6 временно не учитываем.
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
A = 0 0 1 0 0 2
0 0 0 1 0 1
-1 0 0 0 1 3
1 1 0 0 0 -1
Решим систему уравнений относительно базисных переменных: x3, x4, x5, x2
Полагая, что свободные переменные равны 0, получим первый опорный план: X0 = (0,2,10,5,12,0)
Базис B x1 x2 x3 x4 x5 x6
x3 10 0 0 1 0 0 2
x4 5 0 0 0 1 0 1
x5 12 -1 0 0 0 1 3
x2 2 1 1 0 0 0 -1
F(X0) 0 -1 0 0 0 0 -3
Переходим к симплекс-преобразованиям.
Ключевой столбец выбираем по наименьшему отрицательному элементу индексной строки.
Ключевую строку выбираем по наименьшему отношению частного от деления: bi / aij.
Ключевой элемент находится на пересечении ключевого столбца и ключевой строки.
Все вычисления сводим в симплекс-таблицы.
Переход от одной симплекс-таблицы к другой проводим по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, расположенные в вершинах прямоугольника и всегда включающие ключевой элемент КЭ.
НЭ = СтЭ - (А∙В)/КЭ
СтЭ – элемент старого плана,
КЭ – ключевой элемент,
А и В – элементы старого плана, образующие прямоугольник с элементами СтЭ и КЭ.
Базис B x1 x2 x3 x4 x5 x6 min
x3 10 0 0 1 0 0 2 5
x4 5 0 0 0 1 0 1 5
x5 12 -1 0 0 0 1 3 4
x2 2 1 1 0 0 0 -1 -
F(X1) 0 -1 0 0 0 0 -3 0
Базис B x1 x2 x3 x4 x5 x6 min
x3 2 2/3 0 1 0 -2/3 0 3
x4 1 1/3 0 0 1 -1/3 0 3
x6 4 -1/3 0 0 0 1/3 1 -
x2 6 2/3 1 0 0 1/3 0 9
F(X2) 12 -2 0 0 0 1 0 0
Базис B x1 x2 x3 x4 x5 x6 min
x1 3 1 0 3/2 0 -1 0 -
x4 0 0 0 -1/2 1 0 0 -
x6 5 0 0 1/2 0 0 1 -
x2 4 0 1 -1 0 1 0 4
F(X3) 18 0 0 3 0 -1 0 0
Базис B x1 x2 x3 x4 x5 x6
x1 7 1 1 1/2 0 0 0
x4 0 0 0 -1/2 1 0 0
x6 5 0 0 1/2 0 0 1
x5 4 0 1 -1 0 1 0
F(X3) 22 0 1 2 0 0 0
Среди значений индексной строки нет отрицательных
Задать вопрос
на новый заказ в Автор24.
