Постановка задачи лп в канонической форме:

      Найти          max{(c,x)}            (1)

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

      Ax = b,                    (2)         x >=0,                    (3)

где x = (x₁, . . . ,x_n) - вектор неизвестных;      b = (b₁, . . . b_m) - вектор ограничений ;      c = (c₁, . . . , c_n) - вектор коэффициентов функции цели;     A = {a_ij}, i = 1,m; j = 1,n - матрица коэффициентов системы линейных уравнений (2).

Основные шаги симплекс алгоритма.

 Для решения задачи модифицированным симплекс методом исходную задачу (1) - (3) преобразуют к следующему виду

максимизировать      f(x) = c^TB B^-1b -(c_B ^TB^-1N - c^T _N)x_N           (4) при ограничениях     x_B =  B^-1b - B^-1Nx_N   (x_N >=0).                (5)

В выражениях (4),(5)            x_B = (x_Bj), j=1,m - вектор базисных переменных,           x_N = (x_Nj), - вектор небазисных переменных;           c_B = (c_Bj), j = 1,m - коэффициенты функции цели соответствующие базисным                    переменным;           c_N = (c_Nj), j = m+1,n  - коэффициенты функции цели соответствующие небазисным                    переменным;           В - матрица составленная из столбцов матрицы А соответствующих базисным переменным                и образующих линейно независимую систему.          N - матрица составленная из столбцов матрицы А соответствующих небазисным                  переменным.

Преобразование исходной задачи к виду (4), (5) называется приведением ее к каноническому виду и если при этом  вектор β =  B^-1b>= 0 , то форма (4), (5) называется канонически допустимой. Допустимое базисное решение получается если положить x_N = 0. Если вектор β > 0 то решение называется невырожденным, в противном случае вырожденным.

Шаг 1.Выбор ведущего столбца. Определяется переменная которая должна быть введена в базис.  Вычисляется вектор строка относительных оценок небазисных переменных                                          d^T = (c_B ^TB^-1N - c^T _N). Если все d_j >=0 , то решение оптимально, иначе выбирается ведущий столбец и соответствующая ему базисная переменная для ввода в базис  d_q = min{d_j},  (d_j < 0).

Шаг 2. Выбор ведущей строки. На этом шаге определяется переменная которая должна быть выведена из базиса. Если  все элементы ведущего столбца a_iq <= 0 , то решение прекращается так как целевая функция не ограничена на множестве допустимых решений. Иначе определяется β_p/a_pq = min{β_ι/a_iq}  (a_iq > 0). Переменная x_p выводится из базиса.

Шаг 3. Формируется новая матрица В. Столбец соответствующий переменной x_q вводится в матрицу В , а столбец соответсвующий переменной x_p выводится из нее. Решение повторяется с шага 1. 

Правило приведения задачи линейного программирования к каноническому виду состоит в следующем:

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

• если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1;

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

• если некоторая переменная x_j не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными: x₃ = x₃⁺ - x₃^-, где x₃⁺, x₃^- ≥ 0.

Допустимым решением (планом) задачи линейного программирования называется любой n-мерный вектор X=(X₁, X₂,...,X_n), удовлетворяющий системе ограничений и условиям неотрицательности.

Множество допустимых решений (планов) задачи образует область допустимых решений (ОДР).

Оптимальным решением (планом) задачи линейного программирования называется такое допустимое решение (план) задачи, при котором целевая функция достигает экстремума.

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

Приведем математическую модель задачи к каноническому виду.Для этого избавимся от знаков неравенств посредством ввода дополнительных переменных и замены знака неравенства на знак равенства. Дополнительная переменная добавляется для каждого неравенства эксклюзивно, причем эта переменная указывается в целевой функции с нулевым коэффициентом. Правило ввода дополнительных переменых: при ">=" - переменная вводится в неравенство с коэффициентом +1; при "<=" - с коэффициентом (-1).

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

Также можно переориентировать целевую функцию с минимума на максимум или наоборот умножив все коэффициенты при переменных в этой функции на (-1).

13. Двойственные задачи ЛП

Понятие двойственной задачи ЛП.

Пусть задана каноническая задача ЛП

    (5.1)

Если целевая функция f(x) = cx достигает максимального значения на множестве D, то обоснованным представ­ляется вопрос о том, каким образом можно построить верхнюю оценку для нее. Очевидно, что если через и обозначить некото­рый m-мерный вектор, то

cx = cx+u(-Ax+b) = (c-uA)x+bu

Предположим, что и можно выбрать таким образом, чтобы иА ≥ с. Тогда при любых х≥0 справедливо неравенство

сх≤bи                          (5.2)

Стремясь получить наилучшую оценку (5.2), мы приходим к формулировке некоторой новой экстремальной задачи, кото­рая в некотором смысле логически сопряжена с задачей (5.1) и называется двойственной.

Общая схема построения двойственной задачи.

Если задана общая задача ЛП

    (5.5)50

где D определяется системой уравнений и неравенств

то двойственной по отношению к ней называется общая задача ЛП

  (5.6)

где D* определяется системой уравнений и неравенств

Как следует из приведенной схемы при переходе от прямой задачи ЛП к двойственной:

1.  Тип оптимума меняется на противоположный, т. е. максимум на минимум, и наоборот.

2.  Вектор коэффициентов целевой функции c и столбец ограничений b меняются местами.

3.  Матрица ограничений задачи А транспонируется.

4.  Множество индексов переменных, на которые наложено условие неотрицательности в прямой задаче (например, х_j≥0 или u_i≥0), определяют номера ограничений, имеющих форму неравенств в двойственной задаче (а^jи≥с_j или a_ix≤b_i).

5.  Множество номеров ограничений, имеющих форму неравенств в прямой задаче (например, a_ix≤b_i или а^jи≥с_j), определяют множество индексов переменных, на которые накладывается условие неотрицательности, в двойственной задаче (u_i≥0 или х_j≥0).

Из приведенного определения вытекает важное свойство — симметричность отношения двойственности, т. е. задача, двойственная по отношению к двойственной, со­впадает с прямой (исходной) задачей:

((D*)*, (f*)*)≡(D, f),

Тем самым имеет смысл говорить о паре взаимно двой­ственных задач.

 

Пример построения двойственной задачи

Рассмотрим процесс построения двойственной задачи на конкретном примере. Пусть задана ОЗЛП

f_max(x)= 5x₁ -2x₂ +7x₃ +4x₄ -3x₅

D={xcR⁵ |

4x₁ +x₂ -x₃ +x₄                  ≤2,

       5x₂ +x₃ -6x₄ +2x₅ =4,

2x₁ +3x₂ +6x₃ +x₄ -3x₅≤5,

x_2, x₅≥0 }

тогда двойственной к ней будет задача

f*_min(u)= 2u₁ +4u₂ +5u₃

D={ucR³ |

4u₁          +2u₃=5,

  u₁ +5u₂ +3u₃≥ -2,

 -u₁ +  u₂ +6u₃=7,

  u₁ -6u₂ +  u₃=4,

        2u₂  -3u₃≥ -3,

u_1, u₃≥0 }