Симплекс-метод для отыскания опорного и оптимального решений. Примеры, страница 2

            Можно доказать, что за конечное число таких возвращений либо выяснится, что условие задачи противоречиво, либо будет найдено опорное решение. Если по ходу преобразований Рабочей таблицы 2 возникнет таблица, полностью совпадающая с какой-то таблицей на предыдущих этапах, то возникает ситуация «зацикливания». Доказывают, что если при таких обстоятельствах в моменты вы-бора минимума брать другой минимум, а в моменты выбора отрицательного элемента - брать другой отрицательный элемент, то ситуация преодолеется.

            2.Пример отыскания опорного решения.

            Рассмотрим численный пример.

            Речь пойдет о поиске опорного решения. Какой при этом является целевая функция, - не важно. Итак, требуется найти опорное в условиях:

,            Таким образом, здесь три переменных,  семь условий,

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

,              переменные, а свободных переменных - всего одна,

,            это - переменная . Нужно найти такую точку, которая

,             удовлетворяет всем неравенствам, или (что то же са-      

.                мое) делает неотрицательными следующие выражения:

                                   ,

                                   ,

                                   ,

                                   ,

                                   ,

.

Строим Рабочую таблицу:

-x1

-x2

-x3

1

y1=

1

-2

5

3

y2=

-1

-1

-1

-1

y3=

2

1

-1

1

y4=

0

-3

-3

2

y5=

2

-1

2

6

            Учитывая, что свободные переменные - это только x1, надо произвести единственное модифицированное жорданово исключение с разрешающим элементом a11=1 (он выделен серым фоном). Получим  следующую основную таблицу:

-y1

-x2

-x3

1

x1=

1

-2

5

3

y2=

1

-3

4

2

y3=

-2

5

-11

-5

y4=

0

-3

-3

2

y5=

-2

3

-8

0

Далее мы исключаем строки со свободными переменными и получаем Рабочую

таблицу 1:

-y1

-x2

-x3

1

y2=

1

-3

4

2

y3=

-2

5

-11

-5

y4=

0

-3

-3

2

y5=

-2

3

-8

0

Поскольку здесь с самого начала нет строки, соответствующей целевой функ-ции, Рабочая таблица 1 совпадает с Рабочей таблицей 2 и мы приступаем к трем алгоритмическим шагам для поиска опорного решения.

            Просматриваем правый столбец. Отыскиваем отрицательный элемент. В данном случае - это число -5. Фиксируем строку этого элемента и отыскиваем в ней первый отрицательный элемент. В данном случае - это число -2. Столбец этого элемента будет разрешающим. Просматриваем неотрицательные дроби:  2/1,-5/(-2),0/(-2). Нулевые дроби с отрицательными знаменателями - исключаем из рассмотрения. Из оставшихся дробей, т.е. из дробей 2/1, -5/(-2), - выбираем минимальную. В данном случае - это дробь 2/1. Она соответствует строке, кото-рая принимается за разрешающую. Таким образом, надо произвести модифици-

рованное жорданово исключение с разрешающим элементом, который выделен в нижеследующей таблице серым фоном:

-y1

-x2

-x3

1

y2=

1

-3

4

2

y3=

-2

5

-11

-5

y4=

0

-3

-3

2

y5=

-2

3

-8

0

Вот результат этого действия:

-y2

-x2

-x3

1

y1=

1

-3

4

2

y3=

2

-1

-3

-1

y4=

0

-3

-3

2

y5=

2

-3

0

4