--PAGE_BREAK--
Рассмотрим алгоритм перехода к следующим симплекс-таблицам:
1. Выбираем ключевой столбец. Это столбец соответствующий минимально отрицательному (максимально положительному) элементу последней (индексной) строке:
Если отрицательных элементов в индексной строке нет, то план оптимальный.
2. В ключевом столбце выбираются положительные коэффициенты, если таких нет, то задача не имеет решений;
3. Выбираем ключевую строку:
Среди выбранных коэффициентов столбца, для которых абсолютная величина отношения соответствующего свободного члена к этому элементу минимальна.
Ключевой элемент – это элемент, стоящий на пересечении ключевого столбца и ключевой строки;
4. Базисная переменная из ключевой строки переводится в разряд свободных, а свободная переменная в ключевом столбце переводится в разряд базисных. Строится новая таблица;
5. В новой таблице:
5.1 Все элементы ключевой строки делятся на ключевой элемент.
5.2 Все элементы ключевого столба равны нулю, за исключением ключевого элемента.
5.3 Столбец, у которого в ключевой строке имеется ноль, в новой таблице будет таким же.
5.4 Строка, у которой в ключевом столбце имеется ноль, в новой таблице будет такой же.
5.5 В остальные клетки записывается результат преобразования элементов старой таблицы.
6. Переход к шагу 1.
Через конечное число итераций либо будет получено решение задачи линейного программирования, либо будет установлено, что решение неограниченно.
2. Постановка задачи
Для изготовления изделий двух видов склад может отпустить металла не более 150 кг, причем на изделие первого вида расходуется пять килограмм, а на изделие второго вида три килограмма. Требуется спланировать производство так, чтобы была обеспечена наибольшая прибыль, если изделий первого вида требуется изготовить не более 20 штук, а изделий второго вида не более 25 штук, причем одно изделие первого вида стоит 7 руб., а изделие второго вида стоит 8 руб.
3. Решение поставленной задачи
x1– количество изделий первого вида.
x2– количество изделий второго вида.
F(x) – целевая функция.
5x1 + 3x2 =150
x1 £20
x2 £25
x1, x2≥0
F(x) = 7x1 +8x2 ®max
Приведем заданную модель к каноническому виду, введя свободные переменные x3, x4, x5, превращающие неравенства в равенства. Переменные x3, x4, x5 входят в уравнение с коэффициентом единица и только один раз:
5x1 + 3x2+x3 =150
x1+x4=20
x2+x5 =25
x1, x2, x3, x4, x5≥0
F(x)= 7x1 +8x2 +x3 +x4 +x5
x3,x4,x5 – базисные переменные; x1,x2 – свободные переменные.
Составим симплекс – таблицу, соответствующую каноническому виду:
Таблица2 – Итерация 1
Базис
Свободные чл.
X1
X2
X3
X4
X 5
X 3
150
5
3
1
X 4
20
1
1
X 5
25
1
1
F(x)
-7
-8
продолжение
--PAGE_BREAK--