далее в разделах 3.4, 4.3 и 7.4.2.) Далее задается точность, с которой будут отображаться выходные результаты, остается щелкнуть на кнопке Go То Output Screen (Перейти к экрану вывода).

На рис. 3.8 представлено окно, в котором показаны результаты расчетов для каждой итерации для модели Reddy Mikks (файл ch3ToraReddyMikks.txt). Чтобы перейти к следующей итерации, щелкните на кнопке Next Iteration (Следующая итерация, это режим пошагового выполнения). Чтобы сразу получить окончательный ответ, щелкните на кнопке All Iterations (Все итерации). Если вы выполняете вычисления в пошаговом режиме, то на каждой итерации можно указать вводимую и исключаемую переменные, щелкнув на соответствующих столбце и строке. Если ваш выбор корректен, то столбец закрасится зеленым цветом, а строка - красным. В противном случае получите сообщение об ошибке. Такой тип вычислений должен помочь вам понять основные базовые концепции симплекс-метода без громоздких вычислений по методу Гаусса-Жордана.

TORA D:\Work\ToraFilesV:h3ToraRedclyMild<s.txl

LINEAR PROGRAMMING

SIMPI FX 1ЛН1 I AI) (Starting All Slack Method)

Title: Reddy Mikks model, Example 7.2A (Maximize)

Step* for uenerrtirte NEXT tableau tram CURWrNT one:

1. ENTERING variable: Click a NONBASIC variable (rf correct, column turn* green)

?. LEAVING variable: Click а BASIC variable (it correct, row lurna red) 3. Click command button NEXT ITERATION (or Alt ITERATIONS) Thta atep maybe executed without Stcpa 1 inciter 2.

Рис. 3.8. Модель Reddy Mikks в программе TORA

УПРАЖНЕНИЯ 3.3.3

1. Дана следующая задача ЛП.

Максимизировать z = хг + х2 + Зх3 + 2xt при ограничениях

х1 + 2х2 - Зх, + 5х4 < 4, 5хг - 2х2 + 6х4 < 8,

2xl + 3x2-2x3 + 3xi<3, -х1 + х3 + 2х4 < О,

1 2 *3 4 -

a) С помощью программы TORA найдите оптимальное решение данной задачи.

b) Имея оптимальное решение, выберите любую небазисную переменную и попробуйте ввести ее в базис, щелкнув на кнопке Next Iteration. Сравните полученное значение целевой функции с оптимальным. (Идея этого упражнения заключается в том, чтобы показать, что в оптимальном решении любая небазисная переменная, введенная в базис, не может улучшить значения целевой функции.)

3.4. ИСКУССТВЕННОЕ НАЧАЛЬНОЕ РЕШЕНИЕ

В примере 3.3.1 при начальном допустимом базисном решении гарантировалось, что все последующие базисные решения, получаемые при выполнении симплекс-метода, также будут допустимыми. В задачах линейного программирования, где все ограничения являются неравенствами типа < (с неотрицательной правой частью), дополнительные (остаточные) переменные позволяют сформировать начальное допустимое базисное решение. Естественно, возникает вопрос: как найти начальное допустимое базисное решение в задачах ЛП, где есть ограничения в виде равенств или неравенств типа > ?

Наиболее общим способом построения начального допустимого базисного решения задачи ЛП является использование искусственных переменных. Эти переменные в первой итерации играют роль дополнительных остаточных переменных, но на последующих итерациях от них освобождаются. Разработано два тесно связанных между собой метода нахождения начального решения, которые используют искусственные переменные: М-метод5 и двухэтапный метод.

3.4.1. М-метод

Пусть задача ЛП записана в стандартной форме (см. раздел 3.1). Для любого равенства i, в котором не содержится дополнительная остаточная переменная, введем искусственную переменную Д, которая далее войдет в начальное базисное решение. Но, поскольку эта переменная искусственна (другими словами, не имеет никакого физического смысла в данной задаче), необходимо сделать так, чтобы на последующих итерациях она обратилась в нуль. Для этого в выражение целевой функции вводят штраф.

Переменная i?, с помощью достаточно большого положительного числа М штрафуется путем ввода в целевую функцию выражения -MRt в случае максимизации целевой функции и выражения +MRt - в случае минимизации. Вследствие этого штрафа естественно предположить, что процесс оптимизации симплекс-метода приведет к нулевому значению переменной Rt. Следующий пример проясняет детали этого метода.

5 М-метод также называют методом больших штрафов. - Прим. ред.

Пример 3.4.1

Минимизировать z = 4х, + х,

при выполнении условий

Зх, -¥ х2 = 3, 4а-, + Зл-2 > 6, х, + 2х2 < 4, х х2>0.

Стандартная форма этой задачи получается в результате добавления дополнительной (избыточной) переменной х3 во второе неравенство и дополнительной (остаточной) переменной xt в третье неравенство. Эта задача в стандартной форме будет записана следующим образом.

Минимизировать z = 4х, + х2

при выполнении условий

Зх, + х2 = 3, 4л-, + Зх2 - х3 = 6, х, + 2х2 + xt = 4, л х2, х3, х4 0.

В полученной задаче первое и второе уравнения не имеют дополнительных (остаточных) переменных, которые можно ввести в базисное решение. Поэтому введем в эти уравнения искусственные переменные Л, и R2, а в целевую функцию добавим штраф MRX + MR2. В результате получим следующую задачу ЛП.

Минимизировать z = 4х, + х2 + МЛ, + MR2

при выполнении условий

Зх, + х2 + Л, = 3,

4а-, + Зх2 -х3 + Л2 = 6,

х, + 2х2 + х4 = 4,

-К Л, Kg, -

В этой модифицированной задаче переменные Л Л2 и х4 можно использовать в качестве начального допустимого базисного решения. В результате получим следующую симплекс-таблицу.

Прежде чем применять симплекс-метод, надо согласовать значения в z-строке с остальной частью таблицы. В частности, значение функции z, соответствующее начальному базисному решению Л, = 3, Л2 = 6 и х4 = 4, должно равняться ЗМ+ 6М + 0 = 9М, а не 0, как показано в таблице. Это противоречие связано с тем,