Симплекс-метод для отыскания опорного решения. Примеры. Симплекс-метод для отыскания оптимального решения. Примеры, страница 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

            Учитывая, что свободные переменные - это только x₁, надо произвести единственное модифицированное жорданово исключение с разрешающим элементом a₁₁=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