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

1. В последней строке симплекс-таблицы находят наименьший среди отрицательных приведенных коэффициентов . Переменную для перевода в базисную выбирают из условия:

для <0. (3.29)

Свободная переменная переводится в базисную. Столбец, соответствующий этому элементу, считается разрешающим ().

2. Вычисляются отношение свободных членов к положительным элементам разрешающего столбца. Находят наименьшее из этих отношений, оно соответствует разрешающей строке (i = r):

. (3.30)

Элемент ark называется разрешающим. Базисная переменная становится свободной переменной.

3. После нахождения разрешающего элемента и определения новой базисной переменной, переходят к следующей симплекс-таблице. Свободные члены вычисляются по формулам:

а коэффициенты при переменных – по формулам:

После вычисления согласно формулам (3.31) и (3.32) их значения заносят в табл. 3.4. Элементы (m + 1)-й строки этой таблицы вычисляются либо по формулам:

, (3.33)

, (3.34)

либо на основании их определения (3.28) - (3.29).

4. Как только получится симплекс-таблица, в которой в последней строке все приведенные коэффициенты положительные, то оптимальный план получен и максимум целевой функции определен.

На рис. 3.1. приведена блок-схема алгоритма решения задачи линейного программирования, приведенной к канонической форме при выбранном допустимом базисном решении. В блок-схеме приняты следующие обозначения: N = n + m - количество свободных и базисных переменных, M – число уравнений ограничений (число базисных переменных), A – массив коэффициентов при неизвестных и свободных членах системы уравнений (3.22),
B – массив свободных членов системы уравнений (3.22), NB – массив номеров базисных переменных, C – массив коэффициентов целевой функции (3.21).

Рис. 3.1. Блок-схема симплекс-метода

Пример 3.1. Предприятие должно выпускать два вида продукции, используя при этом последовательно различные группы производственного оборудования. Выпуск одного комплекта продукции A обеспечивает предприятию прибыль 2 млн. руб., продукции B - 3 млн. руб. Фонд времени работы (в днях) каждой группы оборудования и трудоемкость (в днях) изготовления комплектов продукции обоих видов представлены в табл. 3.5.

При этих условиях необходимо разработать такой план производства, который обеспечивает наибольшую прибыль для предприятия.

Решение. Составим математическую модель задачи. Пусть и - количество комплектов, соответственно вида A и вида B, которое необходимо

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

Таблица 3.5

Группа производственного оборудования	Норма времени на выпуск одного комплекта, дни	Фонд времени, дни
A	B

Для изготовления x 1 и x 2 комплектов потребуется дней работы на оборудовании 1-ой группы. Всего на оборудовании 1-ой группы можно работать 15 дней. Следовательно, переменные и должны удовлетворять следующему неравенству: .

Выпуск продукции ограничен фондом времени работы каждой из четырех групп оборудования. Условия ограничения для остальных групп оборудования записываются следующим образом:

.

От выпуска комплектов вида А и комплектов вида В предприятие получит прибыль:

. (3.35)

По своему экономическому содержанию переменные не могут быть отрицательными, т.е. .

Необходимо составить такой план производства, который обеспечит наибольшую прибыль: , при соблюдении ограничений:

(3.36)

Для решения симплекс-методом запишем задачу в канонической форме. Для этого перейдем от ограничений-неравенств к ограничениям-равенствам, вводя 4 положительные дополнительные переменные , условия ограничения запишутся в виде системы уравнений:

. (3.37)

Для нашей задачи переменные являются базисными, а - свободные переменные. Составляем первый опорный план, приравняв нулю свободные переменные.

Заполняем первую симплекс – таблицу (таб. 3.6).

Таблица 3.6

i	Базис		bi
m + 1			F 0 = 0	-2	-3

После заполнения таблицы исходный опорный план проверяют на оптимальность, анализируя значения . Первоначальный опорный план не оптимальный, так как в (m + 1)-ой строке есть два отрицательных (). Наименьший отрицательный элемент равен -3, т.е. второй столбец коэффициентов будет разрешающим (j = k = 2). Следовательно, переменная переходит в базисную. Затем определяем отношения свободных членов к положительным элементам разрешающего столбца . Для нашей задачи это будут следующие отношения:

Минимальное из полученных отношений равно 3 при . Соответствующая этой строке (отмечено стрелкой) базисная переменная переходит в свободную переменную, т.е. выводится из базиса. Разрешающий элемент находится на пересечении строки переменной и столбца . Переходим ко второй симплекс-таблице (табл. 3.7), определяя по формулам (3.32) и (3.33), свободные члены и коэффициенты .

Таблица 3.7

i	Базис
m + 1			F 0 = 12	-1

Полученный опорный план не оптимален, так как в
(m + 1)-ой строке есть одно отрицательное ( = -1). Следовательно, первый столбец коэффициентов будет разрешающим () и переменная переходит в базисную. Минимальное отношение свободных членов к положительным элементам разрешающего столбца :

равно 3 при , следовательно, базисная переменная переходит в свободную переменную.

После вычисления и согласно соответствующим формулам, их значения заносим в табл. 3.8.

В последней (m + 1)-ой строке все положительные, следовательно, оптимальное решение найдено.

План производства, приносящий максимальную прибыль: , .

Таблица 3.8

i	Базис
						-
						-2
						-
m + 1

Предприятие должно выпустить три комплекта изделия вида А и два комплекта изделия вида В. Останется неиспользованным четыре дня работы на оборудовании третьей группы и один день на оборудовании четвертой группы. При таком плане производства предприятие получит максимальную прибыль 12 тысяч рублей и останется неиспользованным четыре дня работы на оборудовании третьей группы и один день на оборудовании четвертой группы.