yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->5.1. Отыскания максимума линейной функции

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

5.1. Отыскания максимума линейной функции

Рассмотрим симплексный метод на примере задачи, которая была решена графическим путём в примере 4.4.

Пример 5.1

Найти max функции цели  при ограничениях:

1. Представляем систему ограничений и функцию цели в симплексной форме

 

                                                                                      (5.1)

 

2. Выбираем базисные переменные и исходное допустимое базисное решение (опорный план).

            Для определения первоначального базисного решения разобьем переменные на две группы – базисные (основные) и неосновные. В рассматриваемой задаче в качестве базисных переменных можно взять переменные х3, х4, х5, т.к. определитель, составленный из коэффициентов при этих неизвестных не равен нулю. Действительно

 

 

При выборе базисных переменных на первом шаге не обязательно составлять определитель из их коэффициентов и определять его значение. Достаточно воспользоваться следующим правилом:

В качестве базисных переменных на первом шаге следует выбирать такие m переменных, каждая из которых входит только в одно уравнение системы ограничений, при этом нет таких уравнений, в которые не входит ни одна из этих переменных. При этом, если знаки этих переменных такие же, как и знаки соответствующих свободных членов уравнений, то полученное таким образом базисное решение будет допустимым.

Дополнительные переменные х3, х4, х5 удовлетворяют этому правилу.

Т.к. переменные х1 и х2 являются неосновными, то положив х1 = 0 и х2 = 0, получаем из системы уравнений (5.1) первоначальное базисное решение х1 (0; 0; 6; 4; 6).

Это решение является допустимым. Оно соответствует угловой точке многоугольника (рис.4.8.), находящейся в начале координат.

Т.к. решения допустимые, нельзя отбросить возможность того, что оно оптимально. При решении х1 значение целевой функции равно . Из выражения для функции цели  видно, что ее можно увеличить за счет увеличения переменной х2, которая входит в выражение для функции цели с положительным коэффициентом. Увеличить переменную х2 – это значит перейти к другому базисному решению, в которой переменная х2 будет основной, т.е. будет принимать не нулевые, а положительные значения. Если функция цели содержит несколько неосновных переменных с разными по величине и знаку коэффициентами, то для перевода в основные следует выбирать ту переменную, при которой коэффициент имеет наибольшее положительное значение.

Таким образом ставится задача о «переразрешении» системы уравнений-ограничений относительно новых базисных переменных. Эту операцию удобно осуществлять в табличной форме, в которой удобно представить систему правил по «переразрешению» системы уравнений.

 

 

 

 

 

 

Табличный алгоритм замены базисных переменных

1. Представляем исходную систему уравнений-ограничений (5.1) в табличной форме (таблица 5.1)

 

Таблица 5.1

      перем.

 

базисн.

перем.

х1

х2

х3

х4

х5

bi

х3

-2

3

1

0

0

6

х4

1

-2

0

1

0

4

х5

1

2

0

0

1

6

 

-2

2

0

0

0

F

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

            Отметим характерную особенность таблицы. Эта особенность присуща всем нижеследующим таблицам. Она заключается в том, что каждый столбец, обозначенный основной переменной (в таблице 5.1 это переменные х3, х4, х5) включает в себя одну единицу и остальные нули. При этом единица находится на пересечении столбца и строки, обозначенными одной и той же переменной.

            2. Оцениваем по последней строке таблицы функцию цели при первом базисном решении:   .   Т.к. в функции цели  имеется положительный коэффициент при переменной х2, ее можно увеличить, увеличив переменную х2, т.е. переводя ее из неосновных в основные.

Этот коэффициент определяет так называемый разрешающий столбец, который выделен в таблице 5.1.

            3. С помощью разрешающего столбца определяется разрешающая строка и разрешающий элемент. Для определения разрешающей строки свободные члены делятся на положительные элементы разрешающего столбца (отрицательные элементы и нуль не рассматриваются). В рассматриваемом примере  и . Из полученных отношений выбирается то, которое имеет наименьшее частное, т.е. min (;) = 2. Эту строку назовем разрешающей и выделим ее. На пересечении разрешающей строки с разрешающим столбцом определяется разрешающий элемент. В этом примере он равен 3.

            4. Осуществляем преобразования в разрешающем столбце, в результате которых он содержал бы одну единицу и остальные нули.

            С этой целью делим разрешающую строку в таблице 5.1 на разрешающий элемент, получаем первую строку таблицы 5.2, которую обозначаем переменной х2. С помощью полученной единицы «обнулим» в разрешающем столбце остальные элементы. Например, чтобы «обнулить» во второй строке разрешающего столбца элемент «–2», нужно полученную первую строку таблицы 5.2 умножить на 2 и сложить со второй строкой таблицы 5.1. В результате получим вторую строку таблицы 5.2.

            Проводим аналогичные преобразования с третьей и четвертой строками таблицы 5.1. В результате этих преобразований переменная х2 из неосновных переходит в основные, а переменная х3 – из основных в неосновные. Результаты преобразований сведены в таблицу 5.2.

 

Таблица 5.2

 

 

Базисн.

 перем

х1

х2

х3

х4

х5

bi

х2

1

0

0

2

х4

0

1

0

8

х5

0

0

1

2

 

0

0

0

F-4

 

 

            5. После каждого очередного преобразования проверяем функцию цели на оптимальность. В рассматриваемом случае (последняя строка в таблице 5.2) функция цели имеет вид

           

Т.к. , то  и .

Этот результат был получен при графическом решении задачи (пример 4.4).

            Отметим, что этому решению соответствует вершина А(0;2) в четырехугольнике решений (рис. 4.8), а в пространстве пяти измерений – точка х2(0;2;0;8;2).

 

 

Критерий оптимальности  при отыскании максимума линейной функции.

Если в выражении линейной функции через неосновные переменные отсутствуют положительные коэффициенты при не основных переменных, то решение оптимально.

 

 

 

13