Предприятие планирует выпуск двух видов продукции I и II

Обозначим через Х=(х1,х2) – план производства, показывающий какие виды продукции и в каких количествах необходимо производить, где х1 – количество продукции I, х2 – количество продукции 2-го вида. Общий объем прибыли – это целевая функция, которую необходимо максимизировать:
(1)
Составим систему ограничений на сырье и необходимый минимальный объем выпуска продукции:
Чтобы искомый план был реален, наряду с ограничениями на сырье нужно наложить условие неотрицательности на объемы xj выпуска продукции:
(3)
Таким образом (1)-(3) – математическая модель исходной задачи.
2) Запишем ЭММ в каноническом виде, для чего введем дополнительные переменные х3, х4, х5, х6:
Расширенная матрица системы ограничений-равенств данной задачи:
3 2 1 0 0 0 21
1 1 0 1 0 0 8
2 3 0 0 1 0 21
1 1 0 0 0 -1 3
Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x3.
2. В качестве базовой переменной можно выбрать x4.
3 . В качестве базовой переменной можно выбрать x5.
4. В качестве базовой переменной можно выбрать x6.
Получаем новую матрицу:
3 2 1 0 0 0 21
1 1 0 1 0 0 8
2 3 0 0 1 0 21
-1 -1 0 0 0 1 -3
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (3,4,5,6).
Выразим базисные переменные через остальные:
x3 = -3x1-2x2+21x4 = -x1-x2+8x5 = -2x1-3x2+21x6 = x1+x2-3
Подставим их в целевую функцию:F(X) = 4x1+4x2
Среди свободных членов bi имеются отрицательные значения, следовательно, полученный базисный план не является опорным.
Вместо переменной x6 следует ввести переменную x2.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
Базис B x1 x2 x3 x4 x5 x6
x3 15 1 0 1 0 0 2
x4 5 0 0 0 1 0 1
x5 12 -1 0 0 0 1 3
x2 3 1 1 0 0 0 -1
F(X0) -12 0 0 0 0 0 4
Выразим базисные переменные через остальные:x3 = -x1-2x6+15x4 = -x6+5x5 = x1-3x6+12x2 = -x1+x6+3Подставим их в целевую функцию:F(X) = 4x1+4(-x1+x6+3)илиF(X) = 4x6+12x1+x3+2x6=15x4+x6=5-x1+x5+3x6=12x1+x2-x6=3
При вычислениях значение Fc = 12 временно не учитываем.
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
A = 1 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,3,15,5,12,0)
Базис B x1 x2 x3 x4 x5 x6
x3 15 1 0 1 0 0 2
x4 5 0 0 0 1 0 1
x5 12 -1 0 0 0 1 3
x2 3 1 1 0 0 0 -1
F(X0) 0 0 0 0 0 0 -4
Переходим к симплекс-преобразованиям.
Ключевой столбец выбираем по наименьшему отрицательному элементу индексной строки.
Ключевую строку выбираем по наименьшему отношению частного от деления: bi / aij.
Ключевой элемент находится на пересечении ключевого столбца и ключевой строки.
Все вычисления сводим в симплекс-таблицы.
Переход от одной симплекс-таблицы к другой проводим по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, расположенные в вершинах прямоугольника и всегда включающие ключевой элемент КЭ.
НЭ = СтЭ - (А∙В)/КЭ
СтЭ – элемент старого плана,
КЭ – ключевой элемент,
А и В – элементы старого плана, образующие прямоугольник с элементами СтЭ и КЭ.
Базис B x1 x2 x3 x4 x5 x6 min
x3 15 1 0 1 0 0 2 15/2
x4 5 0 0 0 1 0 1 5
x5 12 -1 0 0 0 1 3 4
x2 3 1 1 0 0 0 -1 -
F(X1) 0 0 0 0 0 0 -4 0
Базис B x1 x2 x3 x4 x5 x6 min
x3 7 5/3 0 1 0 -2/3 0 21/5
x4 1 1/3 0 0 1 -1/3 0 3
x6 4 -1/3 0 0 0 1/3 1 -
x2 7 2/3 1 0 0 1/3 0 21/2
F(X2) 16 -4/3 0 0 0 4/3 0 0
Базис B x1 x2 x3 x4 x5 x6
x3 2 0 0 1 -5 1 0
x1 3 1 0 0 3 -1 0
x6 5 0 0 0 1 0 1
x2 5 0 1 0 -2 1 0
F(X2) 20 0 0 0 4 0 0
Среди значений индексной строки нет отрицательных