yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->5.3. Определение первоначального допустимого базисного решения.

Исследование операций

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, y2ym, которая имеет тот же знак, что и свободный член в правой части уравнения. В первую симплекс-таблицу заносятся искусственные переменные. Вводится  вспомогательная целевая функция 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. Задача целочисленного программирования.

 

 

15