Исследование операций
5.3. Определение первоначального допустимого базисного решения.
Симплексный метод применяется только в случае, когда первоначальное базисное решение является допустимым. В случае, когда на первом шаге получается недопустимое базисное решение, его следует исключить и найти допустимое решение.
Существует два метода определения допустимых опорных планов – метод итераций и метод искусственного базиса.
Метод итераций.
В методе итераций используется тот же симплексный метод. Сначала выбирают разрешающую строку, в которой свободный член является отрицательным. Затем по минимуму отношения свободного члена в разрешающей строке к отрицательным коэффициентам при свободных переменных определяется разрешающий столбец. Если таких строк с отрицательными свободными членами несколько, для каждой из них следует проводить один шаг симплекс – метода.
Замечание. Если в задаче окажется строка с отрицательным свободным членом, а все коэффициенты при свободных переменных положительны, то такая задача решения не имеет.
Рассмотрим метод итераций на примере.
Пример 5.3
Найти
минимальное значение целевой функции 
при ограничениях
Преобразуем систему ограничений – неравенств в систему ограничений – равенств
Представим эту систему ограничений и функцию цели в симплексной форме
Базисными являются переменные х3; х4; х5, переменные х1, х2 – свободные.
Первое базисное решение Х1(0;0;6;12;-1) является отрицательным.
Заполним симплекс-таблицу 5.6
Третью строку выбираем в качестве разрешающей, т.к. она содержит отрицательный свободный член. За разрешающий столбец можно выбрать любой х1 или х2, т.к. коэффициенты при них отрицательные. Выбираем столбец х1.
Таблица 5.6
|
|
х1 |
х2 |
х3 |
х4 |
х5 |
b |
|
х3 |
-1 |
2 |
1 |
0 |
0 |
6 |
|
х4 |
4 |
3 |
0 |
1 |
0 |
12 |
|
х5 |
-1 |
-1 |
0 |
0 |
1 |
-1 |
|
|
-4 |
1 |
0 |
0 |
0 |
F |
Функцию цели при недопустимом решении не рассматриваем.
Выполним симплекс – преобразования. Переведём переменную х1 в основные, а х5 в не основные (таблица 5.7).
Таблица 5.7
|
|
х1 |
х2 |
х3 |
х4 |
х5 |
b |
|
х3 |
0 |
3 |
1 |
0 |
-1 |
7 |
|
х4 |
0 |
-1 |
0 |
1 |
-4 |
8 |
|
х1 |
1 |
1 |
0 |
0 |
-1 |
1 |
|
|
0 |
5 |
0 |
0 |
-4 |
F+4 |
Как видно из таблицы 5.7, полученный опорный план является допустимым. х2(1;0;7;8;0). Получив допустимое решение, проверяем, не является ли оно оптимальным. Функция цели при этом решении не оптимальна, т.к. коэффициент при не основной переменной х5 является отрицательным (-4). Этот коэффициент определяет разрешающий столбец. Разрешающая сторона – вторая.
Переводим в основные переменную х5 и в неосновные переменную х4 (таблица 5.8)
Таблица 5.8
|
|
х1 |
х2 |
х3 |
х4 |
х5 |
b |
|
х3 |
0 |
|
1 |
|
0 |
9 |
|
х5 |
0 |
|
0 |
|
1 |
2 |
|
х1 |
1 |
|
0 |
|
0 |
3 |
|
|
0 |
4 |
0 |
2 |
0 |
F+4+8 |
Полученное решение х3(3;0;9;0;2) является оптимальным,
т.к. коэффициенты при неосновных переменных х2 и х4
являются положительными, что является критерием оптимальности целевой функции
при поиски ее минимума. Целевая функция 
при х2
= х4 = 0 равна 
Метод искусственного базиса
Состоит в следующем. В каждое уравнение, дающее отрицательную компоненту в базисном решении, вводится искусственная неотрицательная переменная y1, y2…ym, которая имеет тот же знак, что и свободный член в правой части уравнения. В первую симплекс-таблицу заносятся искусственные переменные. Вводится вспомогательная целевая функция f = 0 при условии, когда y1 = y2 = … ym = 0. Путём перевода искусственных переменных из основных в неосновные достигается допустимое решение. После этого производится оптимизация обычным методом.
Пример 5.4.
Решим задачу, рассмотренную в примере 5.3
Определим допустимое решение методом искусственного базиса.
Найти
при ограничениях
В последнее уравнение, определяющее недопустимое значение базисной переменной х5 = –1 вводим искусственную переменную y1 с тем же знаком, что и свободный член. Получаем систему ограничений
или 
в которой все базисные переменные х3; х4; y1 имеют допустимые значения.
Вспомогательная функция цели F = – y1.
Составим первую симплекс-таблицу
Таблица 5.9
|
|
x1 |
x2 |
x3 |
x4 |
x5 |
y1 |
b |
|
x3 |
-1 |
2 |
1 |
0 |
0 |
0 |
6 |
|
x4 |
4 |
3 |
0 |
1 |
0 |
0 |
12 |
|
y1 |
1 |
1 |
0 |
0 |
-1 |
1 |
1 |
|
|
|
|
|
|
|
-1 |
F |
Переводим искусственную переменную y1 из основных в не основные. Разрешающая строка – y1, за разрешающий столбец можно взять любой x1 или x2. Возьмем столбец x2.
Выполнив симплекс-преобразование, получаем таблицу 5.10
Таблица 5.10
|
|
x1 |
x2 |
x3 |
x4 |
x5 |
b |
|
x3 |
-3 |
0 |
1 |
0 |
2 |
4 |
|
x4 |
1 |
0 |
0 |
1 |
3 |
9 |
|
x2 |
1 |
1 |
0 |
0 |
-1 |
1 |
|
|
-4 |
1 |
|
|
|
F |
Столбец с y1 исключаем, т.к. при переводе этой переменной в неосновные она стала равной нулю.
В результате симплекс преобразования получено допустимое базисное решение Х1(0;1;4;9;0), которое используется для минимизации функции цели. Функция не оптимальна, т.к. при неосновной переменной x1 находится отрицательный коэффициент.
Разрешающим
столбцом является столбец x1.
Разрешающей строкой является строка х2, в которой имеет место
минимум отношения свободного члена к коэффициенту при х2. 
.
Очередное симплексное преобразование приводит к Таблице 5.11
Таблица 5.11
|
|
х1 |
х2 |
х3 |
х4 |
х5 |
b |
|
х3 |
0 |
3 |
1 |
0 |
-1 |
7 |
|
х4 |
0 |
-1 |
0 |
1 |
4 |
8 |
|
х1 |
1 |
1 |
0 |
0 |
-1 |
1 |
|
|
0 |
5 |
0 |
0 |
-4 |
F+4 |
Функция цели не минимальна, т.к. имеется коэффициент –4 при неосновной переменной х5. Снова проводим симплекс-преобразование. Разрешающим столбцом является столбец х5, разрешающей строкой – х4. Результаты преобразования представлены в таблице 5.12.
Таблица 5.12
|
|
х1 |
х2 |
х3 |
х4 |
х5 |
b |
|
х3 |
0 |
|
1 |
|
0 |
9 |
|
x5 |
0 |
|
0 |
|
1 |
2 |
|
x1 |
1 |
|
0 |
|
0 |
3 |
|
|
0 |
4 |
0 |
1 |
0 |
F+12 |
Функция цели оптимальна, т.к. при неосновных переменных отсутствуют коэффициенты со знаком минус. Оптимальному решению соответствует точка Х*(3;0;9;0;2).
6. Задача целочисленного программирования.