На первой фазе, минимизируя z, из числа базисных переменных выводятся все искусственные переменные, а на второй фазе минимизируется целевая функция y и определяется оптимальное решение исходной задачи.
На первой фазе решения могут встретиться следующие случаи:
1. Если в результате решения задачи (2.31) окажется, что zmin > 0, то это свидетельствует о том, что система ограничений несовместна.
2. Если zmin = 0 и слева то симплексной таблицы нет ни одной искусственной переменной, то можно приступать ко второй фазе метода.
3. Если zmin = 0, но слева от таблицы имеются искусственные переменные, то используя элементарные преобразования, эти переменные следует вывести из числа базисных, а вместо них ввести исходные переменные. В этом случае базисное решение вырожденное (имеет нулевые базисные компоненты). Если искусственную переменную хn+r невозможно вывестииз базиса из-за того, что аrj = 0 для всех j = 1, 2,…,n, то это значит, что r – тое уравнение системы (2.31) лишнее и его нужно вычеркнуть из таблицы.
Пример 1. (Двухфазный симплекс – метод)
y = х1 - x2+ 1 → min
2х1 + х2 + 3х3 = 1
- х1 + 3х2 –х3 = 3
х1 + 11 х2 +3х3 = 11
х1, х2, х1j ≥ 0
Составим задачу для первой фазы, введя искусственные переменные:
z - х4 - х5 - х6 = 0
y - х1 + x2 = 1
2х1 + х2 + 3х3 + х4 = 1
- х1 + 3х2 –х3 + х5 = 3
х1 + 11 х2 +3х3 + х6 = 11
х1, х2, х1j ≥ 0
Исключаем искусственные переменные из первого уравнения:
z + 2х1 + 15х2 + 5х3 = 15
y - х1 + x2 = 1
2х1 + х2 + 3х3 + х4 = 1
- х1 + 3х2 –х3 + х5 = 3
х1 + 11 х2 +3х3 + х6 = 11
х1, х2, х1j ≥ 0
Составим симплекс – таблицу (Табл. 2.5), соответствующую этой системе
Таблица 2.5
|
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
||
|
z |
15 |
2 |
15 |
5 |
0 |
0 |
0 |
|
y |
1 |
-1 |
1 |
0 |
0 |
0 |
0 |
|
х4 |
1 |
2 |
1* |
3 |
1 |
0 |
0 |
|
х5 |
3 |
-1 |
3 |
-1 |
0 |
1 |
0 |
|
х6 |
11 |
1 |
11 |
3 |
0 |
0 |
1 |
В качестве ведущего выбираем второй столбец. Сравнивая отношения 1/1, 3/3, 11/11, вывод, что ведущей может любая из трех последних строк. Выбираем в качестве ведущей строку с наименьшим номером, а ведущим элементом – а42. Соответственно, базисную переменную х4 следуетзаменить на х2. Для этого ведущую строку (строку, соответствующую переменной х4 умножаем последовательно на -15, -1, -3, -11 и складываем соответственно с первой, второй, четвертой и пятой строками. В результате соответствующих преобразований приходим к таблице (Табл.2.6):
Таблица 2.6
|
х1 |
х2 |
х3 |
х5 |
х6 |
||
|
z |
0 |
-28 |
0 |
-40 |
0 |
0 |
|
y |
0 |
-3 |
0 |
-3 |
0 |
0 |
|
х2 |
1 |
2 |
1 |
3 |
0 |
0 |
|
х5 |
0 |
-7 |
0 |
-10 |
1 |
0 |
|
х6 |
0 |
-21 |
0 |
-30 |
0 |
1 |
Четвертый столбец, соответствующий выведенной из базиса искусственной переменной х4 исключаем из рассмотрения. Из табл. 2.6 следует, что минимальное значение z достигнуто и равно нулю, но искусственные переменные х5 их6 еще не выведены из базиса. Выведем переменную х5 . Элементы предпоследней строки, соответствующие переменным х1 и х3 отрицательны, поэтому предварительно умножим эту строку на -1 (что допустимо, так как в нулевом столбце этой строки стоит элемент, равный нулю). Введем вместо х5 переменную х1. Для этого элементы ведущей строки разделим на 7 и с помощью элементарных преобразований добьемся появления нулевых элементов в ведущем столбце, а именно предпоследнюю (ведущую) строку умножим последовательно на 4, 3/7, -3/7, 3 и сложим, соответственно, с нулевой, первой, второй и четвертой строками табл. 2.6. В результате получим таблицу 2.7:
Таблица 2.7
|
х1 |
х2 |
х3 |
х6 |
||
|
z |
0 |
0 |
0 |
0 |
0 |
|
y |
0 |
0 |
0 |
9/7 |
0 |
|
х2 |
1 |
0 |
1 |
1/7 |
0 |
|
х1 |
0 |
1 |
0 |
10/7 |
0 |
|
х6 |
0 |
0 |
0 |
0 |
1 |
Переменную х6 из числа базисных вывести нельзя, так как все соответствующие элементы равны нулю. Значит, третье из уравнений было «лишним». Исключив верхнюю и нижнюю строки, а также последний столбец можно перейти ко второй фазе (Табл. 2.8).
Вторая фаза
Таблица 2.8
|
х1 |
х2 |
х3 |
||
|
y |
0 |
0 |
0 |
9/7 |
|
х2 |
1 |
0 |
1 |
1/7 |
|
х1 |
0 |
1 |
0 |
10/7 |
Ведущий столбец третий. Ведущая строка – вторая. Ведущий элемент а13. Переменную х1 нужно вывести из базиса и ввести переменную х3. Для этого последнюю строку умножаем последовательно на -9/10 и на -1/10 и складываем соответственно с нулевой и первой строками. Получаем оптимальную табл. 2.9:
Таблица 2.9
|
х1 |
х2 |
х3 |
||
|
y |
0 |
-9/10 |
0 |
0 |
|
х2 |
1 |
-1/10 |
1 |
0 |
|
х1 |
0 |
7/10 |
0 |
1 |
Таким образом, минимальное значение у = 0, а оптимальный план
х2 =1, х3 = 0, х1 = 0, ymin = 0.
Вопросы для самопроверки
1. Определите понятия «глобальный экстремум», «локальный экстремум».
2. В чем заключаются условия существования «стационарных точек»?
3. Охарактеризуйте необходимые условия существования экстремума.
4. В чем заключаются достаточные условия существования экстремума?
5. Запишите условия существования экстремума функций двух переменных.
6. Какие задачи приводятся к задачам линейного программирования?
7. Сформулируйте общую задачу линейного программирования и ее частные случаи.
8. Какое решение называется допустимым?
9. Какое решение является оптимальным?
10. К какой задаче линейного программирования применяется однофазный симплекс метод и в чем он заключается?
11. Какое решение называется базисным?
12. К какой задаче линейного программирования применяется многофазный симплекс метод и в чем он заключается?
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.