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