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

 

     В оценочной строке нет положительных чисел. Таблица 3.5 будет последней. По ней можно записать решение исходной стандартной задачи линейного программирования

 

Выпишем из проверочной строки решение двойственной задачи

 
 

3.4. Примеры решения  по методу.

Пример 3.2. Решить задачу линейного программирования симплекс – методом

 
 
 
 

     Задача  задана в стандартной форме. Перепишем  её в равносильной канонической форме

 
 
 
 

     Данные  полученной задачи заносим в симплекс таблицу.

     Таблица 3.6.

 

     В таблице 3.6 первая и вторая строки соответствуют  ограничениям задачи, последняя строка – функции цели. Это оценочная  строка. Значение функции цели берём 0. Выделяем базисные переменные. Эта  переменная находится в столбце  для которой имеется одна единица, остальные нули. В столбце “Базис”  отмечаем одноимённые переменные в  той строке, где расположена эта  единственная единица. Остальные переменные называются свободными.

     По  заполненной симплекс таблице определяем решение, соответствующее этой (нулевой) итерации. Свободные переменные равны 0. Базисные переменные и значение функции  находим из таблицы. Они представлены в столбце “Значение”. Отметим, что значение функции цели берём  с противоположным знаком. Итак,

 

     В оценочной строке имеются положительные  числа. Значит, решение можно улучшить. Выберем наибольшее из положительных  чисел. Если таких чисел несколько  – берём любое из них. Соответствующий  столбец называют ведущим. По ведущему столбу и столбцу “Значения” определяем оценку для каждой строки. Число  из столбца “Значение” делим на соответствующее число из ведущего столбца. Получаем оценку строки. По условию  задачи это положительное число. Объявляем ведущей строкой ту, оценка у которой наименьшее положительное  число. В таблице 3.3 ведущая строка и столбец выделены цветом. На их пересечении находится ведущий  элемент. В нашем случае это число 2.

     Переходим к первой итерации. Её суть состоит  в том, чтобы свободную переменную сделать базисной, а базисную переменную - свободной. В таблице выполняем преобразования аналогичные элементарным строчным преобразованиям в методе Гаусса при решении системы линейных уравнений. В результате преобразований получаем

     Таблица 3.7.

 

     Из  таблицы находим базисные переменные и значение функции  Этот результат можно проверить. Полученные результаты должны удовлетворять функции цели в канонической (стандартной) задаче линейного программирования. Действительно,

 получили  верное равенство.

     В оценочной строке таблицы 3.7 имеется  положительное число, значит можно  перейти к следующей итерации. В таблице 3.7 цветом выделены ведущий  столбец и ведущая строка. Суть второй итерации состоит в том, чтобы  свободную переменную преобразовать в базисную, а базисную переменную сделать свободной. Преобразования проводим по методу Гаусса. Результаты представлены в таблице 3.8.

     Таблица 3.8.

 

     Из  таблицы находим базисные переменные и значение функции  Этот результат можно проверить. Действительно, получили верное равенство.

     В оценочной строке нет положительных  чисел. Значит симплекс – метод завершён. Результат последней итерации даёт ответ канонической задачи. По нему можно записать решение исходной стандартной задачи ЛП

 

     Рассмотренный вариант записи решения в симплекс – таблице имеет одно очень  важное преимущество. В последней  таблице представлено решение двойственной задачи к стандартной задаче ЛП.

     Таким образом, симплекс – метод, рассмотренный  выше, позволяет одновременно решать прямую и двойственную задачу линейного  программирования.

6. ВИДЫ  ДВОЙСТВЕННЫХ ЗАДАЧ. ОСНОВНЫЕ ТЕОРЕМЫ ДВОЙСТВЕННОСТИ.

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

     Различают симметричные, несимметричные и смешанные  двойственные задачи.

 

1. Симметричные  двойственные задачи

 

     Дана  исходная задача

 

при ограничениях:

     

     Задача  дана в неканоническом виде. Составим математическую модель двойственной задачи, для этого:

     каждому неравенству системы ограничений  исходной задачи приводим в соответствие переменную y_i;

     составляем  целевую функцию, коэффициентами которой  являются свободные члены системы  ограничений исходной задачи;

     составляем  систему ограничений. Коэффициенты системы ограничений образуют транспонированную матрицу коэффициентов системы ограничений

 

исходной  задачи. Знаки неравенств меняются на противоположные;

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

     Математическая  модель двойственной задачи имеет вид

 

при ограничениях:

     

 

2. Несимметричные  двойственные задачи

     Дана  исходная задача

 

при ограничениях:

     

     Задача  дана в каноническом виде. Составим математическую модель двойственной задачи.

     Для ее составления пользуются тем же правилом, что и для составления  симметричной задачи, с учетом следующих  особенностей: ограничениями двойственной задачи будут неравенства. Если в целевой функции двойственной задачи требуется найти минимум, то знак неравенства ≥, если максимум, то ≤; переменные — произвольные по знаку.

     Математическая  модель двойственной задачи имеет вид

 

при ограничениях:

     

 

3. Смешанные двойственные задачи

     Математическая  модель исходной задачи имеет условия  симметричных и несимметричных задач. При составлении двойственной задачи необходимо выполнять правила симметричных и несимметричных задач.

     4.2. Основные теоремы двойственности

     ТЕОРЕМА 1. Если одна из двойственных задач имеет оптимальное решение, то другая также имеет оптимальное решение, причем для любых оптимальных решений и выполняется равенство

 

     Если  одна из двойственных задач неразрешима  ввиду того, что L( )_max → (или S( )_min → - ), тo другая задача не имеет допустимых решений.

     ТЕОРЕМА 2. Для оптимальности допустимых решений и пары двойственных задач необходимо и достаточно, чтобы они удовлетворяли системе уравнений

 
 

     Теоремы позволяют определить оптимальное  решение одной из пары задач по решению другой.

 

     4.3. Решение двойственных задач

     1. Решение симметричных задач

 

     Рассмотрим  решение задач с использованием теорем двойственности.

     

     Решим исходную задачу графическим методом, получим  _опт = (4, 1), при этом L( )_mах = 3.

     На  основании 1-й теоремы двойственности

 

     Так как x₁, х₂ > 0, то по 2-й теореме двойственности систему ограничений двойственной задачи можно записать в виде равенств:

 

Подставим _опт в систему ограничений исходной задачи:

 

Тогда система ограничений двойственной задачи примет вид

 

Откуда  _опт = (0, 2/3, 1/3), при этом S( )_min = 3.

Пусть дано решение двойственной задачи _опт = (0, 2/3, 1/3), S( )_min = 3, найдем решение исходной.

     По 1-й теореме двойственности L( )_max = S( )_min = 3. Так как , то по 2-й теореме двойственности второе и третье неравенства исходной задачи обращаются в равенства:

 

Откуда  _опт = (4,1), при этом L( )_mах = 3.

     Рассмотрим  решение задач методом, основанным на взаимно однозначном соответствии между переменными: основным переменным исходной задачи соответствуют балансовые переменные двойственной, и наоборот. Для этого решим двойственную задачу симплексным методом:

 

при ограничениях:

 
 

     Из  табл. 4.1 следует, что _опт = (0, 2/3, 1/3), S( )_min = 3.

 

     Таблица 4.1.