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

Таким образом, текущий вид задачи состоит в следующем:

максимизировать

Z = 0,03 Wa + 0,07 Wb

0,lWe + 0,3W4 + j, = 0,2 (9.21)

Wa+Wb + s2= 1.

При Wa = 0, Wb = 0, s\ = 0,2 и s2 = 1 решение равно Z = 0. Это первоначальное возможное решение. Далее метод продвигается через последовательность улучшающихся возможных решений до тех пор, пока не будет найдено лучшее. Для облегчения поиска лучшего решения представим исходную ситуацию в табличной форме

+-индикаторы-►

Нижняя строка представляет собой целевую функцию Мы установили цель в форме Z - 0,03 -0,07 Wb + 0s\ + 0- - 0. Первая и вторая строки показывают два ограничения, связанных с этой задачей. ПС представляет правую сторону неравенств.

Теперь мы должны дать определение базисных и небазисных переменных. Базисные переменные - это те, в столбцах которых содержатся только нули кроме одной единицы. Значит, в данном предварительном решении s\ и s2 являются базовыми переменными. Текущая величина этих переменных может быть найдена, -если посмотреть на правый столбец напротив элемента один в соответствующих столбцах. Отсюда текущая величина s\ составляет 0,2, а текущее значение 52-1.

Остальные переменные известны как небазисные переменные. В этом процессе небазисные переменные имеют текущее значение ноль.

При каждой итерации (шаге) процесса поиска одна базисная переменная преобразуется в небазисную переменную. В то же время какая-либо небазисная переменная преобразуется в базисную переменную (что называется вхождением в решение).

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

Улучшение решения

Первым шагом в этом процессе служит определение одного элемента в целевой строке, который имеет знак минус. Мы выберем -0,03 (возможен выбор между -0,03 и -0,07). Столбец чисел, где находится -0,03, известен как основной.

Вспомним, что в первоначальной форме целевая функция имеет вид Z = 0,03 Wa + 0,07 Wb. В таблице Z выражена через текущие небазисные переменные, т.е. в таблице это соотносится с Z-0,03 Жд-0,07 Wb = 0. Так как в предварительном решении эти небазисные переменные имели нулевые значения и их коэффициенты в таблице отрицательны, мы видим, что Z возрастет, если увеличится Wa или Wb, т.е. если мы сделаем какую-то из них базисной. Имея возможность выбора, мы решили выбрать увеличение Wa.

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

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

Следующий шаг - преобразование всех остальных элементов основного столбца в нули с помощью прибавления или

вычитания соответствующих кратных количеств основной строки (заметьте: мы используем новые значения основной строки, т.е. после того как основа была приведена к единице). Таким образом, для преобразования 0,1 вверху основного столбца в ноль мы отнимаем 0,1 раза основную строку от каждого соответствующего элемента верхней строки. Чтобы трансформировать -0,03 в ноль, прибавим 0,03 раза основную строку к каждому элементу нижней строки. Получилась такая таблица:

-индикаторы-►

Для толкования этого решения заметьте, что переменные, являющиеся базисными, будут иметь значения, которые даны соответствующими элементами с правой стороны. Все значения других переменных будут равны нулю. Следовательно, целевая функция (Z) имеет величину 0,03 (без учета постоянной 0,08), Wa равна единице, s\ равна 0,1, в то время как Щ и s2 имеют нулевые значения.

На то, что поиск оптимального решения еще не завершен, указывают индикаторы, а именно - один индикатор со знаком минус .

Поэтому повторим процесс. Во второй таблице мы видим, что основным является столбец, в котором нижний элемент равен -0,04. Проверяя соотношения, мы находим основу, равную 0,2 в верхней строке ограничений, которая отсюда становится основной строкой. Для преобразования основы в единицу мы делим все элементы основной строки на 0,2. Затем трансформируем все остальные элементы основного столбца в нули, вычитаем заново преобразованную основную строку из нижнего ограничения и прибавляем 0,04 раза новую основную строку к целевой функции. Получившаяся таблица имеет вид:

-индикаторы-*