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

1.3 Симплекс-таблицы

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

Обозначим через хi свободные переменные, через уj- базисные переменные. Пусть есть система ограничений: необходимо поменять местами переменную у3 и свободную переменную х2  из третьего уравнения (а32≠0) и подставить во все остальные.

y1 = a11x1 + a12x2 + a13x3 + a14x4 + b1 ,              (3.1)

y2 = a21x1 + a22x2 + a23x3 + a24x4 + b2 ,

y3 = a31x1 + a32x2 + a33x3 + a34x4 + b3 ,

y4 = a41x1 + a42x2 + a43x3 + a44x4 + b4 ,

y5 = a51x1 + a52x2 + a53x3 + a54x4 + b5 ,

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

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

y1= b1- (-a11x1 - a12x2- …- a14x4).              (3.2)

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

                                                                                                 Таблица 1

Алгоритм замены:

1)     разрешающий элемент заменяется на обратную ему величину;

2)     все элементы разрешающей строки делятся на разрешающий элемент;

3)     все элементы разрешающего столбца, кроме разрешающего элемента, меняют на противоположный и делятся на разрешающий элемент;

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

Алгоритм преобразования коэффициентов стандартной таблицы следующий:

1)     выделяют в таблице разрешающий элемент a1k;

2)     найти обратную ему величину λ=1/аlk и записать ее в правом нижнем углу этой же ячейки;

3)     все элементы разрешающей строки, кроме разрешающего элемента, умножить на λ и результат записать в правой нижней части ячейки;

4)     все элементы разрешающего столбца, кроме разрешающего элемента, умножить на (-λ).

5)     выделить в разрешающей строке все верхние числа, а в разрешающем столбце – все нижние числа;

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

7)     переписать таблицу, заменив переменные: элементы разрешающего столбца и строки- числами, стоящими в нижних частях этих ячеек; каждый из оставшихся элементов- суммой чисел в верхнем и нижнем частях это ячейки .

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

1) нахождение опорного решения;

2) нахождение оптимального решения.

В процессе первого этапа выясняется имеет ли данная задача допустимое решение. Если да, то находится опорное решение.

В процессе второго этапа выясняется ограничена ли сверху целевая функция . Если нет, то оптимального решения нет.

1.4 Двойственная задача линейного программирования

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

Пусть есть общая задача линейного программирования, состоящая в нахождении максимума целевой функции

F=c1x1 +…+ cnxn→ max                                                                          (4.1)

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

a11x1 + a12x1 + …+ а1nxn ≤b1 ,               (4.2)

………..,

ak1x1 + ak2x2 + …+ аknxn ≤bk  ,

ak+1x1 + ak+2x2 + …+ аk+1xn =bk+1  ,

…………….,

am1x1 + am2x2 + …+ аmnxn =bm ,

xj ≥ 0 (j=l,…,l; l≤n).

Это прямая задача. Двойственной к этой задаче является задача, состоящая в нахождении минимума функции

F*=b1y1 + …+ bmym

              (4.3)

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

a11у1 + a21у1 + …+ аm1ym ≥c1 ,               (4.4)

………..,

a11y1 + a21y2 + …+ аm1ym ≥c1 ,

a11+1y1 + a21+1y2 + …+ аm 1+1ym =cl+1  ,

…………….,

a1ny1 + a2ny2 + …+ аmnym =cn,

yi≥ 0 (i=l,…,k; k≤m).

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

1)                       если прямая задача является задачей максимизации, то двойственная будет будет задачей минимизации, и наоборот;

2)                       коэффициенты целевой функции прямой задачи с1 , с2 , …,сn становятся свободными членами ограничений двойственной задачи;

3)                       свободные члены ограничений прямой задачи b1 , b2 , …,bm становятся коэффициентами целевой функции двойственной задачи;

4)                       матрица ограничений двойственной задачи получается транспонированием матрицы ограничений прямой задачи;

5)                       число ограничений прямой задачи равно числу переменных двойственной задачи, а число ограничений двойственной задачи равно числу переменных прямой задачи;

6)                       если переменная xj  прямой задачи может принимать только неотрицательные значения, то j-ое ограничение в двойственной задаче является неравенством вида больше или равно; если же переменная xj  может принимать как положительные, так и отрицательные значения, то j-ое ограничение в двойственной задаче – уравнение.

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

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

Правила перехода от прямой к двойственной задаче для симметричных и несимметричных задач (табл.2).

Связь между оптимальными решениями прямой и двойственной задач устанавливают посредством следующих теорем теории двойственности.

Теорема 1. если х0 и u0  - допустимые решения прямой и двойственной задач соответственно, то значение целевой функции прямой задачи никогда не превышают значения целевой функции двойственной задачи.

Теорема 2. Если х0 и u0   - допустимые решения прямой и двойственной задач соответственно, и если выполняется равенство

CT х0 =u0T*B,              (4.5)

то   х0 и u0   - оптимальные решения пары двойственных задач.

Таблица2
 

1.5 Транспортная задача

Транспортная задача- это более простой метод решения задач линейного программирования.

Пусть имеются m пунктов отправления (ПО) А1, А2,…,Аm, в которых сосредоточены запасы каких-то однородных грузов в количестве соответственно а1, а2,…, аm, единиц. Имеются n пунктов назначения (ПН) В1, В2,…,Вm, подавших заявки соответственно на b1, b2,…, bm, единиц груза. Сумма всех заявок в сумме равна сумме всех запасов:

=

Условие называется балансовым условием, а транспортная задача- задача с правильным балансом.

Известны стоимости Су перевозки единицы груза от каждого пункта отправления А до каждого пункта назначения В. Задана матрица стоимостей С. Считается, что стоимость перевозки нескольких единиц груза пропорциональна их числу.

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

Нужно обозначить через хij количество единиц груза, отправляемого из i-ого ПО А1  в j-ый ПН В1 .

Совокупность чисел (хij) будет называться «планом перевозок», а сами величины хij  - «перевозками». Эти положительные переменные должны удовлетворять следующим условиям:

1. Суммарное количество груза, направляемого из каждого ПО во все ПН, должно быть равно запасу груза в данном пункте. Это даст m условий-равенств:

х11 +х 12  +…+ х1n= а1,              (5.2)

.

.

xm1 +х m2  +…+ хmn= аm,

или в общем виде

=ai, (i=1,m).

2. Суммарное количество груза, доставляемого в каждый ПН из всех ПО, должно быть равно заявке, поданной данным пунктом.

Это даст n условий-равенств:

х11 +х 12  +…+ хm1= b1,              (5.3)

.

.

x1n +х 2n  +…+ хmn= bn,

=bj, (i=1,n).

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

L=→min,

где знак двойной суммы означает, что суммирование производится по всем комбинациям индексов i и j, то есть по всем парам ПО-ПН.

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

1.                              Все коэффициенты при переменных в ограничениях равны единицы.

2.                              Значение имеет структура связей между переменными. Число линейно-независимых уравнений равно не m+n, а (n+m-1). Общее число в данной задаче равно mn.