Задание 1. Прямая линия на плоскости . . Задание 1. Прямая линия на плоскости (стр. 4 )

Пусть предприятие выпустит x1 единиц – продукции I, х2 единиц – продукции II, х3 единиц – продукции III.

Расход сырья А на все виды продукции – . По условию задачи расход сырья А  не должен превышать запаса , т. е. ≤ Аналогично составляем ограничения расхода сырья В и С. Получим систему неравенств:

Прибыль от реализации выпущенной продукции будет равна

.

Запишем модель задачи:

  (12)

.  13) 

(13)  называют целевой функцией.

Пусть (7,2,5), d2(0,3,1), d3(5,2,1), Q(220,140,100), Р(2,1,1)

  (14)

 

  .  (15)

Введем балансовые переменные , , в каждое неравенство для приведения модели к каноническому виду

  (16)

, (j=1,2,…6)

.  (17)

Алгоритм симплексного метода

1. Записываем данную задачу в исходную симплексную таблицу.

2. Если все элементы оценочной строки симплексной таблицы неотрицательны, то соответствующий план является оптимальным.

3. Если в оценочной строке  содержится отрицательный элемент, а в столбце над ним нет ни одного положительного элемента, то целевая функция не ограничена сверху на множестве допустимых планов и задача не имеет решения.

4. Если  в каждом столбце соответствующем отрицательной оценке содержится хотя бы один положительный элемент, то можно перейти к “лучшему ” плану следующим образом:

а)  выбираем разрешающий столбец по наименьшей отрицательной оценке;

б)  выбираем разрешающую строку по минимальному значению  ;

  равно отношению свободных членов к соответствующим положительным  элементам разрешающего столбца;

в) на пересечении разрешающего столбца и разрешающей строки лежит разрешающий элемент;

г) элементы разрешающей строки делим на разрешающий элемент и записываем в новой таблице сохраняя порядок строки, оставшиеся элементы разрешающего столбца заполняем нулями;

д) элементы остальных строк, в том числе и оценочной строки,  вычисляем по формулам прямоугольников (см. метод Жордана –Гаусса).

Составим симплексную таблицу.

Таблица заполняется следующим образом:

В столбце “ai0” записываются свободные члены уравнений (16), в столбцах  “ x1”, “x2”, …, “x6” − коэффициенты  при соответствующих неизвестных этой системы.

В столбце “базис” выписываются базисные переменные, содержащиеся в соответствующих уравнениях системы (16).

Верхняя строчка и крайний левый столбец содержат коэффициенты при соответствующих неизвестных  целевой функции Z выражения (17).

Последняя строка таблицы называется оценочной строкой, а её элементы a0j  оценками.  Первый элемент  a00  оценочной строки равен значению целевой функции Z для начального опорного плана

  .

Это значение может быть получено как результат скалярного умножения вектора – столбца “сj “ на вектор – столбец свободных членов “ai0” :

  Z(0) = a00  = 0∙220 + 0∙140 + 0∙100 = 0.

Остальные значения a0к оценочной строки получаются в результате скалярного умножения вектора – столбца “сj “ на вектор – столбец  коэффициентов при переменной хк с последующим вычитанием соответствующего элемента ск верхней строки:

a01 = 0∙7 + 0∙2 +0∙5 – 2 = -2;

a02 = 0∙0 + 0∙3 +0∙1 – 1 = -1;

a03 = 0∙5 + 0∙2 +0∙1 – 1 = -1.

Оценки для базисных переменных всегда равны 0.

cj	Базис xj	ai0	2	1	1	0	0	0
x1	x2	x3	x4	x5	x6
0 0 0	x4 x5 x6	220 140 100	7 2 5	0 3 1	5 2 1	1 0 0	0 1 0	0 0 1	220/7 140/2 100/5 min
Z	0	-2	-1	-1	0	0	0
0 0 2	x4 x5 x1	80 100 20	0 0 1	-7/5 13/5 1/5	18/5 8/5 1/5	1 0 0	0 1 0	-7/5 -2/5 1/5	min
Z	40	0	-3/5	-3/5	0	0	2/5
0 1 2	x4 x2 x1	1740/13 500/13 160/13	0 0 1	0 1 0	58/13 8/13 1/13	1 0 0	7/13 5/13 -1/13	-21/13 -2/13   3/13	500/8 160
Z	820/13	0	0	-3/13	0	3/13	4/13
1 1 2	x3 x2 x1	30 20 10	0 0 1	0 1 0	1 0 0	13/58 -8/58 -1/58	7/58 18/58 -5/58	-21/58 4/58 15/58
Z	70	0	0	0	3/58	15/58	13/58

  y1  y2  y3

Исходное опорное решение , не является оптимальным, в оценочной строке три отрицательные оценки  (-2), (-1), (-1), ситуация соответствует пункту 4 алгоритма симплексного метода.  Перейдём к новому опорному плану:

а) разрешающий столбец соответствует переменной  , т. к.  оценка (-2) ─ наименьшая отрицательная оценка оценочной строки;

б) третья строка является  разрешающей, т. к. для неё  ;

в) на пересечении разрешающих столбца и строки лежит разрешающий элемент 5, при этом в базис войдёт переменная  , а переменная выйдет из базиса.

Далее заполнение новой таблицы осуществляется по методу Жордана – Гаусса.

В результате  первой итерации получим новое опорное решение  , .

Вторая итерация приводит к решению:

, .

После третьей итерации получаем оптимальное решение: ,  . Дальнейшее увеличение Z невозможно, т. к. все оценки оценочной строки  стали неотрицательными.