Линейное программирование

3. ЧИСЛЕННЫЕ   МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ЛП

3.4. Специальная задача ЛП.

                Специальной задачей ЛП (СЦЛП) называется задача ЛП, удовлетворяющая условиям :

                1. Это каноническая задача ЛП.

                2. Система линейных ограничений есть система с базисом.

                3. Целевая функция выражается только через небазисные переменные.

                СЗЛП имеет таким образом следующий вид

                              

                Замечание о начальном базисном решении

                Если в СЗЛП   i=1,..., m, то вектор

                                        

является допустимым базисным решением СЗЛП.

                Доказательство

                1. х- допустим, так как х удовлетворяет всем линейным ограничениям и (так как все    по условию)

                2. х- базисное решение, так как система векторов столбцов

               

                                                                              Замечание доказано.

 

                Допустимой СЗЛП называется СЗЛП, в которой   i=1,..., m.

 

                Каждой СЗЛП соответствует симплексная таблица                                                                              

                Строка L называется индексной строкой.

                Симплексная таблица называется допустимой, если все элементы b1,...,bm неотрицательны.Допустимой симплексной таблице соответствует допустимое базисное решение

                                                

Значение целевой функции

                                                              

                Две симплексные таблицы называются эквивалентными, если соответствующие им специальные задачи ЛП эквивалентны.

 

 3.5 Правила преобразования симплексных таблиц

                Для решения СЗЛП применяется симплекс-метод Данцига (1974 г.).

                Поскольку каждой допустимой СЗЛП соответствует допустимое базисное решение, то переходу от одного допустимого базиса к другому соответствует переход от одной СЗЛП к другой СЗЛП, или переход от одной симплекс-таблице к эквивалентной ей симплекс-таблице. Такой переход осуществляется до тех пор, пока не будет найдена СЗЛП с оптимальным базисным решением.

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

                                                                               

вводится в базис вместо некоторой базисной переменной

                                                                              .

Столбец q и строка p называются ведущими и выбираются по следующим правилам.

                Правило выбора ведущего столбца q

                В базис вводится переменная

                Правило выбора ведущей строки р.

                Из базиса выводится переменная

                                                              

для которой выполняется ключевое отношение :

                                                              

                Преобразование симплексной таблицы осуществляется по следующим правилам.

                Формулы пересчета симплекс-таблицы

2) Ведущая строка p делится на ведущий элемент

                                                                    

                              

3) Ведущий столбец q делится на ведущий элемент с противоположным знаком        

                              

4) Оставшиеся строки преобразуются по правилу : из строки   вычитается  поделенная на

                                                                

строка р (или новая ведущая строка   , j=m+1,...,n), умноженная на коэффициент     

                              

5) Индексная строка пересчитывается по тому же правилу :

               

                Схему преобразования элементов симплекс-таблицы (кроме ведущей строки и ведущего столбца) называют схемой ”прямоугольника”.

               

Преобразуемый элемент

                                                                

и соответствующие ему три сомножителя как раз и являются вершинами ”прямоугольника”.

 

3.6 Пример

                Убедимся на примере, что преобразования симплексной таблицы 1) -5) действительно соответствуют гаусовским преобразованиям системы уравнений.

                Рассмотрим задачу ЛП

               

                Этой задаче соответствует симплекс-таблица

                              

Пусть переменная выводится из базиса, а переменная  вводится в базис. Тогда строка  ведущая, столбец  ведущий, а элемент  - ведущий элемент.

После преобразований 1)- 5) получим новую симплекс-таблицу     

                Гауссовские преобразования соответствующей системы уравнений состоят в следующем.

                Из строки            

                                              

выражается переменная , в результате получаем значение соответствующей ведущие строке симплексной таблицы :

                              

                Затем полученные значения подставляем во все ограничения и в целевую функцию для исключения из них переменной . К примеру, после подстановки выражения  в первое уравнение

                              

                получим выражение

что соответствует строке для x1в новой симплекс-таблице. Не составляет особого труда проверка остальных строк симплекс-таблицы.

                Таким образом, преобразования симплекс-таблицы соответствуют гауссовским преобразованиям соответствующей системы линейных уравнений.

 

3.7 Теоретические основы симплекс-метода

Критерий оптимальности

Если в индексной строке допустимой симплексной таблицы                                                                 то соответствующее допустимое базисное решение   является оптимальным решением.

Доказательство.

На базисном решении

                              

целевая функция имеет значение

                              

                Рассмотрим любое допустимое решение

                              

Тогда

               

поскольку

                           

                Для любого допустимого решения х' получили неравенство                                             

что означает оптимальность решения х.

Критерий доказан

 

3.8 Критерий неограниченности целевой функции.

Пусть существует  для которого столбец

Тогда целевая функция L неограничена сниузу на допустимом множестве.

Доказательство.

Рассмотрим для t>0 вектор

 

, где  

Для любого t>0 вектор  допустим, так как

                                              

и выполняются ограничения-равенства А =b. Но значение целевой функции

                                              

неограниченно убывает при так как

                                                                

Значит L(x) не ограничена снизу на допустимом множестве.

Критерий доказан

 

3.9 Теорема о ключевом отношении

Если переменная    вводится в базис вместо переменной , для которой выполняется ключевое отношение

                              

, то в новой симплексной таблице все   е.у. новая таблица является допустимой.

 Доказательство.

Новой симплексной таблице с элементами

                                              

соответствует новое базисное решение

                Докажем, что

                                                i=1,..., m.

               

Теорема доказана

 

3.10 Теорема об улучшении базисного решения

Если существует    для некоторого i=1,..., m, то возможен переход к эквивалентной допустимой симплексной таблице, причем значение целевой функции на новом базисе не больше значения целевой функции на старом базисе.

Доказательство.

Значение целевой функции в исходной симплекc-таблице

                                              

Значение целевой функции в новой симплекс-таблице       

Так как     т.е. значение целевой функции при переходе к новому базису возрастает.

Теорема доказана

 

3.11  Алгоритм симплекс-метода.

               Подготовительный этап

                Приводим задачу ЛП  к виду

            

 

                Шаг 0.  Составляем симплексную таблицу, соответствующую исходной задаче :

                Заметим, что этой таблице соответствует допустимое базисное решение     

                                              

задачи ( I ). Значение целевой функции на этом решении

                                              

 

                Шаг 1. Проверка на оптимальность.

                Если среди элементов симплексной таблицы

нет ни одного положительного элемента

то оптимальное решение задачи ЛП найдено :

               

Алгоритм завершает работу.

 

                Шаг 2. Проверка на неразрешимость.

                Если среди элементов симплексной таблицы

                              

есть положительный

               

а в соответствующем столбце

               

нет ни одного положительного элемента

                              

то целевая функция L является неограниченной снизу на допустимом множестве. В этом случае оптимального решения не существует. Алгоритм завершает работу.

               

                Шаг 3. Выбор ведущего столбца q.

                Среди элементов симплексной таблицы

                              

выбираем максимальный положительный элемент

                              

Этот столбец объявляем ведущим (разрешающим).

 

                Шаг 4. Выбор ведущей строки р.

                Среди положительных элементов столбца

                              

находим элемент

                              

для которого выполняется равенство :                                      

               

строку р объявляем ведущей (разрешающей).  Элемент

                              

объявляем ведущим (разрешающим).

               

                Шаг 5. Преобразование симплексной таблицы.

                Составляем новую симплексную таблицу, в которой :

 

 

            д) оставшиеся элементы симплексной таблицы

преобразуются по следующей схеме “прямоугольника”.

        Из элемента вычитается произведение трех сомножителей :

        первый сомножитель - соответствующий ( в той же строке, где и преобразуемый элемент) элемент ведущего столбца;      

        второй сомножитель - соответствующий ( в том же столбце, где и преобразуемый элемент) элемент ведущей строки;        

        третий сомножитель - обратная величина ведущего элемента

        Преобразуемый элемент и соответствующие ему три сомножителя как раз и являются вершинами“прямоугольника”.

               

                Шаг 6. Переход к следующей итерации осуществляется переходом к шагу 1.

 

3.12 Пример.

Решить задачу ЛП, записанную в виде (17)

                              

Составим соответствующую симплексную таблицу

               

                              

                Так как коэффициенты строки целевой функции неотрицательны, то начальное базисное решение

                                              

не является оптимальным. Значение целевой функции для этого базиса  L  = 0.

                Выбираем ведущий столбец - это столбец, соответствующий пере-

менной

               Выбираем ведущую строку. Для этого находим

                                              

Следовательно, ведущая строка соответствует переменной    

Проводим преобразование симплексной таблицы, вводя переменную     в базис и выводя переменную   из базиса. Получим таблицу

                                              

                Одна итерация метода завершена. Переходим к новой итерации, Полученная таблица   неоптимальна. Базисное решение, соответствующее таблице, имеет вид

                                              

Значение целевой функции на этом базисе  L  = -2.

Ведущий столбец здесь - столбец, соответствующий переменной  Ведущая строка - строка, соответствующая переменной После проведения преобразований получим симплексную таблицу

 

                                              

                Еще одна итерация завершена. Переходим к новой итерации.

                Строка целевой функции не содержит положительных значений, значит соответствующее базисное решение

               

является оптимальным и алгоритм завершает работу.