Структура и свойства двойственной задачи

Любую задачу максимизации ЛП с экономической точки зрения можно рассматривать как задачу о распределении ограниченных ресурсов b 1 ,b 2 ,…,b m между различными потребителями, например, между некоторыми технологическими процессами, которые представляются столбцамиA 1 ,A 2 ,…A n матрицы ограничений задачи. Любое допустимое решение задачи ЛПx 1 ,x 2 ,…x n дает конкретное распределение, указывающее ту долю каждого из ресурсов, которая должна быть использована при осуществлении соответствующего технологического процесса.

Рассмотрим пример. Завод производит три вида продукции x 1 ,x 2 иx 3 , каждый из которых требует затрат времени на обработку на токарном, фрезерном и сверлильном станках. Количество машинного времени для каждого из станков ограничено. Пустьc 1 ,c 2 ,c 3 – прибыль от реализации единицы соответствующего вида продукции. Необходимо определить, какое количество каждого вида продукции необходимо производить в течение недели, чтобы получить максимальную прибыль.

Формально эта задача записывается так:

максимизировать (c 1 x 1 +c 2 x 2 +c 3 x 3) (1)

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

a 11 x 1 + a 12 x 2 + a 13 x 3 ≤ b 1 ;

a 21 x 1 + a 22 x 2 + a 23 x 3 ≤ b 2 ;

a 31 x 1 +a 32 x 2 +a 33 x 3 ≤b 3 , (2)

где a 1 j ,a 2 j ,a 3 j – время, необходимое для обработки единицыj-го вида продукции соответственно на токарном, фрезерном и сверлильном станках (j= 1, 2, 3);b 1 ,b 2 ,b 3 – недельный ресурс машинного времени соответственно для токарного, фрезерного и сверлильного станков.

Обозначим y 1 ,y 2 иy 3 –цену единицы времени работы на токарном, фрезерном и сверлильном станках. Тогдаa 11 y 1 +a 21 y 2 +a 31 y 3 – можно трактовать как расходы на изготовление единицы продукции первого вида;a 12 y 1 +a 22 y 2 +a 32 y 3 – расходы на изготовление единицы продукта второго вида и т. д.

Предположим, что цены ресурсов y 1 ,y 2 ,…,y m выбраны так, что выполняются следующие соотношения:

a 11 y 1 + a 21 y 2 + a 31 y 3 ≥ с 1 ;

a 12 y 1 + a 22 y 2 + a 32 y 3 ≥ с 2 ;

a 13 y 1 +a 23 y 2 +a 33 y 3 ≥ с 3 . (3)

Поскольку b 1 ,b 2 иb 3 – использованный ресурс машинного времени для каждого из станков, тоb 1 y 1 +b 2 y 2 +b 3 y 3 – суммарные расходы на производство.

Требуется найти такие y 1 ,y 2 иy 3 , удовлетворяющие условиям (3), при которых минимизируются суммарные расходы на производство:

минимизировать g(y 1 ,y 2 ,y 3)=b 1 y 1 +b 2 y 2 +b 3 y 3 (4)

при условиях

y 1 ≥0;y 2 ≥0;y 3 ≥0.

Такую задачу называют двойственной задачей по отношению к задаче (1), называемой прямой.

Запишем теперь прямую и двойственную задачи в общем случае.

Прямая задача :

максимизировать

при условиях

(7)

Двойственная задача :

минимизировать

при условиях

(10)

В матричном виде пара двойственных задач записывается следующим образом:

максимизировать

при условиях

минимизировать

при условиях

A T y≥c; (15)

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

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

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

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

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

знаки неравенств в ограничениях изменяются на обратные;

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

Переменные y 1 ,y 2 ,…,y m двойственной задачи иногда называют теневыми ценами.

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

задаче при малом количестве переменных имеется большое количество ограничений (m n).

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

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

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

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

ТЕОРЕМА 3. Если в оптимальном решении прямой задачи (5) – (7) i -ое ограничение выполняется как строгое неравенство, то оптимальное значение соответствующей двойственной переменной равно нулю, т. е.

где - i -ая строка матрицы А.

Смысл теоремы 3 состоит в следующем. Если некоторый ресурс имеется в избытке иi-е ограничение при оптимальном решении выполняется как строгое неравенство, то оно становится несущественным, и оптимальная цена соответствующего ресурса равна 0.

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

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

Дадим экономическую интерпретацию теоремы 4.

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

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

Таким образом, теорема 4 выражает принцип рентабельности оптимально организованного производства.

Из нее вытекает также, что то

(20)

Предположим, что среди переменных x 1 ,x 2 ,…,x n прямой задачи есть множество изmпеременных, которые в оптимальном решении имеют ненулевое значение. Пусть, например, таковыми оказались первые по порядкуmпеременных.

Тогда на основании уравнения (22) получают mусловий рентабельности:

(21)

Приведем еще две важные теоремы теории двойственности.

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

ТЕОРЕМА 6 (теорема двойственности). Допустимый вектор x 0 оптимален тогда, и только тогда, когда в двойственной задаче имеется такое допустимое решение y 0 , что

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

i=1, 2, …,m;j=1, 2, …,n,

где n– количество переменных прямой задачи;m– количество ее ограничений; - соответствующие элементы индексной строки прямой и двойственной задач соответственно. При этом, еслиn+i, где 1 ≤i≤mбольше числа векторов-столбцов матрицы ограничений расширенной формы соответствующей задачи, то элементы находятся путем циклической перестановки элементов индексной строки, начиная с элемента

Общий случай двойственности

В предыдущем разделе были установлены основные соотношения для пары двойственных ЛП-задач при ограничениях в форме неравенств. Обобщим теперь эти результаты на случай произвольных ограничений.

Пусть прямая ЛП-задача задана в виде:

максимизировать

при условиях

Тогда двойственная задача по отношению к (24)-(26) (или сопряженная с ней) состоит в минимизации линейной формы:

минимизировать

при условиях

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

Если переменная x j прямой задачи предполагается неотрицательной, то j-е условие системы ограничений (28) является неравенством.

Если на x j не накладывается такое ограничение, то j-е ограничение двойственной задачи будет равенством.

Аналогичным образом связаны знаки переменных двойственной задачи y i и соответствующие им ограничения прямой задачи. Заметим, что если положитьm 1 =mиn 1 =n, то получим частный случай пары двойственных задач с ограничениями в форме неравенств.

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

при условиях

(33)

(34)

Определение 1. Задача, состоящая в нахождении минимального значения функции

при условиях

(36)

(37)

называется двойственной по отношению к задаче (32) – (34). Задачи (32) – (34) и (35) – (37) образуют пару задач, называемую в линейном программировании двойственной парой. Сравнивая две сформулированные задачи, видим, что двойственная задача составляется согласно следующим правилам:

1. Целевая функция исходной задачи (32) – (34) задается на максимум, а целевая функция двойственной (35) – (37) – на минимум.

2. Матрица

(38)

составленная из коэффициентов при неизвестных в системе ограничений (33) исходной задачи (32) – (34), и аналогичная матрица

(39)

в двойственной задаче (35) – (37) получаются друг из друга транспонированием (т. е. заменой строк столбцами, а столбцов – строками).

3. Число переменных в двойственной задаче (35) – (37) равно числу ограничений в системе (33) исходной задачи (32) – (34), а число ограничений в системе (36) двойственной задачи – числу переменных в исходной задаче.

4. Коэффициентами при неизвестных в целевой функции (35) двойственной задачи (35) – (37) являются свободные члены в системе (33) исходной задачи (32) – (34), а правыми частями в соотношениях системы (36) двойственной задачи – коэффициенты при неизвестных в целевой функции (32) исходной задачи.

5. Если переменная x j исходной задачи (32) – (34) может принимать только лишь положительные значения, то j –е условие в системе (36) двойственной задачи (35) – (37) является неравенством вида “? ”. Если же переменная x j может принимать как положительные, так и отрицательные значения, то 1 – соотношение в системе (54) представляет собой уравнение. Аналогичные связи имеют место между ограничениями (33) исходной задачи (32) – (34) и переменными двойственной задачи (35) – (37). Если i – соотношение в системе (33) исходной задачи является неравенством, то i –я переменная двойственной задачи . В противном случае переменная у j может принимать как положительные, так и отрицательные значения.

Двойственные пары задач обычно подразделяют на симметричные и несимметричные. В симметричной паре двойственных задач ограничения (33) прямой задачи и соотношения (36) двойственной задачи являются неравенствами вида “ ”. Таким образом, переменные обеих задач могут принимать только лишь неотрицательные значения.

Пример 1. Составить двойственную задачу по отношению к задаче, состоящей в максимизации функции

(40)

при условиях

(41)

Решение. Для данной задачи

и

Число переменных в двойственной задаче равно числу уравнений в системе (41), т. е. равно трем. Коэффициентами в целевой функции двойственной задачи являются свободные члены системы уравнений (41), т.е. числа 12, 24, 18.

Целевая функция исходной задачи (40) – (42) исследуется на максимум, а система условий (41) содержит только уравнения. Поэтому в двойственной задаче целевая функция исследуется на минимум, а ее переменные могут принимать любые значения (в том числе и отрицательные). Так как все три переменные исходной задачи (40) – (42) принимают только лишь неотрицательные значения, то в системе условий двойственной задачи должны быть три неравенства вида “? ”. Следовательно, для задачи (40) – (42) двойственная задача такова: найти минимум функции при условиях

Пример 2. Для задачи, состоящей в максимизации функции

при условиях

сформулировать двойственную задачу.

Решение. Для данной задачи

,

В соответствии с общими правилами задача, двойственная по отношению к данной, формулируется следующим образом: найти минимум функции при условиях

Связь между решениями прямой и двойственной задач

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

при условиях

(44)

Двойственная задача: найти минимум функции

при условиях

(47)

Каждая из задач двойственной пары (43) – (45) и (46), (47) фактически является самостоятельной задачей линейного программирования и может быть решена независимо одна от другой. Однако при определении оптимального плана одной из задач тем самым находится решение и другой задачи.

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

Лемма 1. Если Х – некоторый план исходной задачи (43) – (45), Y – произвольный план двойственной задачи (46), (47), то значение целевой функции исходной задачи при плане Х всегда не превосходит значения целевой функции двойственной задачи при плане Y, т. е.

Лемма 2. Если для некоторых планов X * и Y * задач (43) – (45) и (46), (47), то X * – оптимальный план исходной задачи, а Y * – оптимальный план двойственной задачи.

Теорема 8 (первая теорема двойственности). Если одна из задач двойственной пары (43) – (45) или (46), (47) имеет оптимальный план, то и другая имеет оптимальный план и значения целевых функций задач при их оптимальных планах равны между собой, т. е.

Если же целевая функция одной задачи из двойственной пары неограничена (для исходной (43) – (45) – сверху, для двойственной (46), (47) – снизу), то другая задача вообще не имеет планов.

Теорема 9 (вторая теорема двойственности). План задачи (43) – (45) и план задачи (46), (47) являются оптимальными планами этих задач тогда и только тогда, когда для любого выполняется равенство

Геометрическая интерпретация двойственных задач

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

Пример 3.

составить двойственную задачу и найти решение обеих задач.

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

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

Как видно из рис. 8, максимальное значение целевая функция исходной задачи принимает в точке В. Следовательно, Х * = (2, 6) является оптимальным планом, при котором . Минимальное значение целевая функция двойственной задачи принимает в точке Е (рис. 8). Значит, Y * =(1; 4) является оптимальным планом двойственной задачи, при котором Таким образом, значения целевых функций исходной и двойственной задач при их оптимальных планах равны между собой.

Из рис . 7 видно, что при всяком плане исходной задачи значение целевой функции не больше 46. Одновременно, как видно из рис . 8, значение целевой функции двойственной задачи при любом ее плане не меньше 46. Таким образом, при любом плане исходной задачи значение целевой функции не превосходит значения целевой функции двойственной задачи при ее произвольном плане.

Пример 4.

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

Исходная задача;

Двойственная задача:

Решение. Как исходная, так и двойственная задача содержат по две переменные. Поэтому их решение находим, используя геометрическую интерпретацию задачи линейного программирования (рис. 7 и 8). Из рис . 7 видно, что исходная задача не имеет оптимального плана из-за неограниченности снизу ее целевой функции на множестве допустимых решений.

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

Нахождение решения двойственных задач. Рассмотрим пару двойственных задач – основную задачу линейного программирования (43) – (45) и двойственную к ней задачу (46), (47).

Предположим, что с помощью симплексного метода найден оптимальный план X * задачи (43) – (45) и этот план определяется базисом, образованным .

Обозначим через вектор-строку, составленную из коэффициентов при неизвестных в целевой функции (43) задачи (43) – (45), а через – матрицу, обратную матрице Р , составленной из компонент векторов базиса. Тогда имеет место следующее утверждение.

Теорема 10. Если основная задача линейного программирования имеет оптимальный план X * , то является оптимальным планом двойственной задачи.

Таким образом, если найти симплексным методом оптимальный план задачи (43) – (45), то, используя последнюю симплекс–таблицу , можно определить и и с помощью соотношения найти оптимальный план двойственной задачи (46), (47).

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

Сказанное выше имеет место и для симметричной пары двойственных задач. При этом так как система ограничений исходной задачи содержит неравенства вида “ ”, то компоненты оптимального плана двойственной задачи совпадают с соответствующими числами (m +1)–й строки последней симплекс–таблицы решения исходной задачи. Указанные числа стоят в столбцах векторов, соответствующих дополнительным переменным.

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

составить двойственную задачу и найти ее решение.

Решение. Двойственная задача по отношению к исходной состоит в нахождении минимума функции при условиях

Чтобы найти решение двойственной задачи, сначала находим решение исходной задачи методом искусственного базиса. Оно приведено в таблице 12. Из последней симплекс-таблицы видно, что двойственная задача имеет решение

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

Таблица 12

i	Базис	С б	p 0	1	2	-1	0	0	-M
				p 1	p 2	p 3	p 4	p 5	p 6
1 2 3 4 5 1 2 3 4 1 2 3 4	p4 p5 p6 P4 p5 p1 P2 p5 p1	0 0 -M 0 0 1 2 0 1	12 17 4 0 -4 14 15 2 2 4 9 4 12	-1 1 2 -1 -2 0 0 1 0 0 0 1 0	4 1 -1 -2 1 7/2 3/2 -1/2 -5/2 1 0 0 0	-2 2 2 1 -2 -1 1 1 2 -2/7 13/7 6/7 9/7	1 0 0 0 0 1 0 0 0 2/7 -3/7 1/7 5/7	0 1 0 0 0 0 1 0 0 0 1 0 0	0 0 1 0 0 1/2 -1/2 1/2 1/2 1/7 -5/7 4/7 6/7

Экономическая интерпретация двойственных задач

Экономическую интерпретацию двойственных задач и двойственных оценок рассмотрим на примере.

Пример 6. Для производства трех видов изделий А , В и С используется три различных вида сырья. Каждый из видов сырья может быть использован в количестве, соответственно не большем 180, 210 и 244 кг. Нормы затрат каждого из видов сырья на единицу продукции данного вида и цена единицы продукции каждого вида приведены в таблице 13.

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

Таблица 13

Вид сырья	Нормы затрат сырья (кг ) на единицу продукции
Цена единицы продукции (руб.)

Решение. Предположим, что производится x 1 изделий А , изделий В и изделий С. Для определения оптимального плана производства нужно решить задачу, состоящую в максимизации целевой функцииу 3 должны удовлетворять следующей системе неравенств:

(52)

Как видно, задачи (48) – (50) и (51) – (53) образуют симметричную пару двойственных задач. Решение прямой задачи дает оптимальный план производства изделий A , В и С , а решение двойственной – оптимальную систему оценок сырья, используемого для производства этих изделий. Чтобы найти решение этих задач, следует сначала отыскать решение какой–либо одной из них. Так как система ограничений задачи (48) – (50) содержит лишь неравенства вида “ ”, то лучше сначала найти решение этой задачи. Ее решение приведено в таблице 14.

Из этой таблицы видно, что оптимальным планом производства изделий является такой, при котором изготовляется 82 изделия В и 16 изделий С. При данном плане производства остается неиспользованным 80 кг сырья II вида, а общая стоимость изделий равна 1340 руб. Из таблицы 14 также видно, что оптимальным решением двойственной задачи является

Таблица 14

i	Базис	С б	p 0	10	14	12	0	0	0
				p 1	p 2	p 3	p 4	p 5	p 6
1 2 3	p 2 p 5 p 3	14 0 12	82 80 16 1340	19/8 23/8 -3/4 57/4	1 0 0 0	0 0 1 0	5/8 1/8 -1/4 23/4	0 1 0 0	-1/8 -5/8 1/4 5/4

Переменные и обозначают условные двойственные оценки единицы сырья, соответственно I и III видов. Эти оценки отличны от нуля, а сырье 1 и III видов полностью используется при оптимальном плане производства продукции. Двойственная оценка единицы сырья II вида равна нулю. Этот вид сырья не полностью используется при оптимальном плане производства продукции.

Таким образом, положительную двойственную оценку имеют лишь те виды сырья, которые полностью используются при оптимальном плане производства изделий. Поэтому двойственные оценки определяют дефицитность используемого предприятием сырья. Более того, величина данной двойственной оценки показывает, на сколько возрастает максимальное значение целевой функции прямой задачи при увеличении количества сырья соответствующего вида на 1 кг. Так, увеличение количества сырья I вида на 1 кг приведет к тому, что появится возможность найти новый оптимальный план производства изделий, при котором общая стоимость изготовляемой продукции возрастет на 5,75 руб. и станет равной 1340+5,75= 1345,75 руб. При этом числа, стоящие в столбце вектора таблицы 14, показывают, что указанное увеличение общей стоимости изготовляемой продукции может быть достигнуто за счет увеличения выпуска изделий В на 5/8 ед. и сокращения выпуска изделий С на 1/4 ед. Вследствие этого использование сырья II вида уменьшится на 1/8 кг. Точно так же увеличение на 1 кг сырья III вида позволит найти новый оптимальный план производства изделий, при котором общая стоимость изготовляемой продукции возрастет на 1,25 руб. и составит 1340+1,25=1341,25 руб. Это будет достигнуто в результате увеличения выпуска изделий С на 1/4 ед. и уменьшения изготовления изделий В на 1/8 ед., причем объем используемого сырья II вида возрастет на 5/8 кг.

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

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

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

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

По определённым правилам можно составить соответствующую задачу, называемую двойственной задачей .

Рассмотрим прямую задачу линейного программирования и двойственную задачу .

Прямая задача .
Максимизировать функцию

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

Двойственная задача .
Минимизировать функцию

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

Эти задачи обладают следующими свойствами:

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

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

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

Итак мы рассмотрели соответствие между прямой и двойственной задачей линейного программирования, правда, пока только для задач, записанных в канонической форме. Сформулируем пока правила составления задачи, двойственной по отношению к исходной для канонической задачи (а позже перейдём к задаче, записанной в общей форме):

1. Приводят все неравенства системы ограничений исходной задачи к неравенствам одного смысла(то есть с одним и тем же знаком): если в исходной задаче ищется максимум функции цели (линейной формы) - они записываются со знаком "меньше или равно", если же минимум - со знаком "больше или равно". Для этого неравенства, в которых это требование не выполняется, умножают на минус единицу.
2. Выписывают матрицу A коэффициентов при переменных исходной задачи, полученых после преобразований, описанных в предыдущем пункте, и составляют матрицу A ", транспонированную относительно матрицы A .
3. Составляют систему ограничений двойственной задачи, взяв в качестве коэффициентов при переменных элементы матрицы A ", а в качестве свободных членов - коэффициенты при переменных в функци цели исходной задачи и записывают неравенства противоположного смысла (то есть меняют знак) по сравнению с неравенствами, полученными в пункте 1.
4. Составляют функцию цели (линейную форму) двойственной задачи, приняв за коэффициенты при переменных свободные члены системы ограничений исходной задачи, полученные в пункте 1.
5. Указывают, что необходимо найти при решении двойственной задачи, а именно: минимум функции цели, если в исходной задаче ищется максимум, и максимум, если в исходной задаче ищется минимум.
6. Записывают условие неотрицательности переменных двойственной задачи.

Пример 1. Составить задачу, двойственную следующей : найти максимум функции при ограничениях

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

Для облегчения составления двойственной задачи лучше пользоваться расширенной матрицей B , в которую наряду с коэффициентами при переменных системы ограничений исходной задачи запишем свободные члены и коэффициенты при переменных в функции цели, выделив для этой цели дополнительные столбец (отделён чертой) и строку (выделена красным цветом). Матрицу B транспонируем и, используя транспонированную матрицу B ", составляем задачу, двойственную исходной. Матрицы B и B " имеют вид

,

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

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

1. Свободные члены в прямой задаче - коэффициенты функции цели в двойственной задаче.
2. Коэффициенты функции цели в прямой задаче - свободные члены в двойственной задаче.
3. Расширенная матрица в прямой задаче - транспонированная расширенная матрица в двойственной задаче.
4. j -й неизвестный в прямой задаче неотрицательный - j -е неравенство в двойственной задаче со знаком "больше или равно".
5. j -й неизвестный в прямой задаче без ограничения знака - j -е ограничение в двойственной задаче в виде уравнения.
6. j -й неизвестный в прямой задаче неположительный - j -е неравенство в двойственной задаче со знаком "меньше или равно".
7. i -е неравенство в прямой задаче со знаком "меньше или равно" - i -е неизвестный в двойственной задаче неотрицательный.
8. i -е ограничение в прямой задаче в виде уравнения - i -й неизвестный в двойственной задаче без ограничения знака.
9. i -е неравенство в прямой задаче со знаком "больше или равно" - i -й неизвестный в двойственной задаче неположительный.

Пример 2. Составить задачу, двойственную следующей : найти минимум функции при ограничениях

Решение. Как видим, прямая задача записана в общей форме. Это будем учитывать при расстановке знаков в условиях двойственной задачи. А пока, как и в предыдущем примере, произведём универсальное действие - составим матрицу B прямой задачи и транспонированную матрицу B " двойственной задачи:

,

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

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

Теория двойственности в линейном программировании строится на двух основных теоремах.

Теорема 1. Для прямой и двойственной задач в силе одно и только одно из следующих утверждений. 1. Если одна из задач линейного программирования имеет конечный оптимум, то и двойственная к ней задача также имеет конечный оптимум, причём оптимальные значения линейных форм обеих задач совпадают, т. е. F max = Z min или F min = Z max . 2. Если линейная форма одной из двойственных задач не ограничена, то условия другой задачи противоречивы. 3. Обе задачи не имеют решения, так как системы ограничений противоречивы.

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

При решении симплекс-методом исходной задачи для сведения системы неравенств к эквивалентной ей системе уравнений нужно ввести m добавочных неотрицательных переменных (по числу неравенств в системе ограничений) x n+1 , x n+2 , ..., x n+i , ..., x n+m , где i = 1, 2, ..., m означает номер неравенства, в которое была введена добавочная переменная x n+i .

Система ограничений двойственной задачи состоит из n неравенств, содержащих m переменных. Если решать эту задачу симплекс-методом, то следует ввести n добавочных неотрицательных переменных y m+1 , y m+2 , ..., y m+j , ..., y m+n , где j = 1, 2, ..., n означает номер неравенства системы ограничений двойственной задачи, в которое была введена добавочная переменная y m+j .

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

x 1 ↔ y m+1

x 2 ↔ y m+2

x j ↔ y m+j

x n ↔ y m+n

x n+1 ↔ y 1

x n+2 ↔ y 2

x n+i ↔ y i

x n+m ↔ y m

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

Иными словами, каждой первоначальной переменной исходной задачи x j (j = 1, 2, ..., n ) ставится в соответствие добавочная переменная y m+j , введённая в j -е неравенство двойственной задачи, а каждой добавочной переменной x n+i исходной задачи (i = 1, 2, ..., m ), введённой в i -е неравенство исходной задачи, - первоначальная переменная y i двойственной задачи.

Всё вышесказанное, как уже было отмечено, станет более понятным из примера 2, который будет вскоре после Теоремы 2.

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

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

Пример 3. На основании решений прямой и двойственной задач линейного программирования из примера 1 убедиться в справедливости теорем 1 и 2.

В примере 1 была дана исходная задача: найти максимум функции при ограничениях

Мы составили двойственную ей задачу: найти минимум функции при ограничениях

Для решения прямой задачи симплекс-методом система ограничений-неравенств сводится к системе уравнений путём введения добавочных неотрицательных переменных x 3 , x 4 , x 5 , x 6 :

Читатель может проверить, решив задачу симплекс-методом , что она имеет следующие решения:

а максимум целевой функции F max = 13 ,

Система ограничений двойственной задачи сводится к системе уравнений путём введения добавочных переменных y 5 , y 6 :

Решение двойственной задачи симплекс-методом даёт следующий ответ:

а минимум целевой функции Z min = 13 ,

при этом сама целевая функция выражается как

Решив двойственную задачу, убеждаемся в справедливости первой части теоремы 1: двойственная задача тоже имеет конечный оптимум, причём Z min = F max = 13 .

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

x 1 ↔ y 5

x 2 ↔ y 6

x 3 ↔ y 1

x 4 ↔ y 2

x 5 ↔ y 3

x 6 ↔ y 4

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

Функцию цели, полученную на последнем шаге решения двойственной задачи, выразим через все переменные этой задачи:

Рассматривая коэффициенты при переменных y j в этой функции цели и учитывая их соответствие коэффициентам при переменных x i , получим решение (4; 1; 0; 5; 4; 0) , совпадающее с решением прямой задачи.

Линейное программирование. Постановка задач линейного программирования

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

Математическая модель ЗЛП:

1.Максимум или минимум целевой функции(критерий оптимальности).

2.Система ограничений в форме линейных уравнений и неравенств.

3.Неотрицательность переменных.

Решение, удовлетворяющее системе ограничений и требованиям неотрицательности решений является допустимым, а решения, удовлетворяющие одновременно с этим и условиям min/max являются оптимизированными.

Общий вид ЗЛП

Max(min)F(x)=c1x1+c2x2+…cnxn

A11x1+a12x2+…a1nxn<=b1

A21x1+a22x2+…a2nxn<=b2

Am1x1+am2x2+…amnxn<=bnm, x1,x2,…xn>=0

Свойства ЗЛП:

1.Допустимое множество решений ЗЛП либо пустое, либо является выпуклым многогранником.

2.Если допустимое множество не пустое, а целевая функция ограничена сверху для максимизации, а снизу – для минимизации, то она имеет оптимальное решение.

3.Оптимпльное решение задач линейного программирования (если они существуют), то находятся на границе, т.е. если существует оптимальное решение, то им является одна из вершин многогранника допустимых решений, если 2 или несколько вершин допустимые решения, то любая их комбинация является оптимальным решением.

Графический метод решения ЗЛП

Если число неизвестных равно 2, то ее можно решить графическим методом. Найти решение X=(x1,x2)? Удовлетворяющее условию max(min)z=c1x1+c2x2. При ограничениях сумм j от 1 до n (aij*xj)<=bj, x1, x2 >=0.

Каждое из неравенств 2 определяет на координатной плоскости полуплоскость, а система неравенств 2 и 3 в случае ее совместимости – пересечение плоскостей. Это будет выпуклое множество, которое может быть представлено как:

1.Выпуклый многоугольник.

2.Выпуклая неограниченная многоугольная область.

3.Отрезок.

5.Одна точка.

6.Пустое множество.

Геометрическая интерпретация целевой функции:

Z=C 1 X 1 +C 2 X 2 (1)

При фиксированных значениях Z=Z 0 определяет линию z0=c1x1+c2x.

При изменении Z получим семейство параллельных прямых, называемых линиями уровня.

Вектор С=(С 1 , С 2) с координатами при x1 и x2 перпендикулярен каждой из линий уровня.

Вектор С показывает направления наибольшего возрастания (убывания) целевой функции.

Если построить на одном рисунке область допустимых решений вектор С и одну из линий уровня, например Z=0, то задача сводится к определению области допустимых решений точки направления вектора С, через которую проходит линия уровня Z макс(мин), соответствующая наибольшему(меньшему) значению функции Z. Если задача рерзрешима могкт представиться следующие случаи:

1.Задача имеет единственное решение.

2.Задача имеет бесконечное множество решений(альтернативный оптимум).

3.Целевая функция не ограничена, область допустимых решений – единственная точка(рис. 1).

Симплекс-метод

Построение начального опорного плана

Рассмотрим 3 случая.

1) Пусть система ограничений имеет вид

X i + ij X j =b i , b i =>0,(i=1,m)

X 0 =(0,0,…,0,b i)

Ограничение канонической задачи линейного программирования имеет предпочтительный вид, если при неотрицательной его части левая часть содержит переменную, входящую с коэффициентом равным 1, а остальные с коэффициентом равным 0. Если каждое ограничение канонической задачи линейного программирования имеет предпочтительный вид, т.е. система ограничений приведена к единичному неотрицательному базису, то начальный опорный план строиться следующим образом: Предпочтительные переменные выбираются в качестве базисных, а все остальные свободные.

Ij X j <=b i , b i >=0

Дополнительную переменную вводят с коэффициентом равным 0

Ij X j +X n+1 =b i , b i >=0

X 0 =(0,…,0,b 1 ,...,b m)

Ij X j >=b i , b i >=0

Ij X j -X n+i =b i

Max(min)Z= j X j -(+)M i

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

Признак оптимальности опорного плана. Задача максимизации

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

Рассмотрим переход к нехудшему опорному плану на примере задачи ЛП на макс.

Если в индексной строке dj < 0, то план не оптимален и его можно улучшить. Среди отрицательных оценок находят максимальную по абсолютной величине.

Если задача на минимум, то разрешающий столбец Max|dj|=|dj 0 |

Переменную Xj 0, следует ввести в базис. Для определения переменной, выводимой из базиса, находят отношения: B i /A ij , A ij >0

Min = B i 0 /A i 0 j 0

НА пересечении разрешающей строки и разреш столбца находиться разр элемент.

1.Элементы строки I 0 новой таблицы равны соответствующим элементам разрешающей строки предыдущей таблицы деленной на разреш элемент.

2.Все элементы столбцы J 0 равны 0, за исключением разрешающего элемента.

3.Все остальные элементы новой таблицы высчитываются по правилу: произведение главной диагонали минус произведение побочной диагонали деленной на разрешающий элемент.

Три признака:

1.Альтернативный оптимум (признак бесконечности множества оптимальных планов). Если в индексной строке последней симплексной таблицы (содержащей оптимальный план) имеется хотя бы одна нулевая оценка, соответствующая свободной переменной, то задача ЛП имеет бесконечное множество оптимальных планов.

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

3.Признак несовместности системы ограничений. Если в оптимальном плане М-задачи не все искусственные переменные равны 0, то система ограничений исходной задачи несовместна.

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

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

Прямая - maxZ = Xj>=0

Двойственная minZ = Xj>=0

Пара двойственных задач может быть экономически интерпретирована:

Прямая – Сколько и какой продукции Xj надо произвести чтобы при заданных стоимостях единицы продукции Cj объемах ресурсов Bi и нормах расхода Aij максимизироваит выпуск продукции в стоимостном выражениии.

Двойственная – Какова должна быть оценка единицы каждого из ресурсов чтобы при заданных Bi Cj Aij минимизировать общую оценку затрат на все ресурсы.

Правила построения:

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

2.Если прямая задача решается на максимум, то двойственная на минимум.

3.Каждому ограничению прямой задачи соответствует переменная двойственной задачи и наоборот.

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

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

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

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

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

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

Поставщики	ПОТРЕБИТЕЛИ	Запас груза
B 1	B 2	…	B n
А 1	X 11 c 11	X 12 c 12	…	X 1n c 1n	a 1
…	…				…
А m	…				a n
Потребность в грузе	b 1

В таблице указаны поставщики А1… , у которых имеется в наличии соответственно а 1 … единиц однородного груза. Данный груз должен быть доставлен n потребителям, в количествах в 1 … единиц, заданы стоимости с ij перевозок груза от i поставщика j потребителю. Требуется спланировать перевозки(указать, сколько единиц груза должно быть отправлено от I того поставщика j потребителю, так чтобы максимально удовлетворить спрос потребителя и чтобы суммарные затрата на перевозки были при этом минимальными).

c 1 – цена.

Задачи, где суммарные запасы грузов поставщиков равны суммарным потребностям, называются закрытыми.

I != I – то задача открытая.

При решении транспортных задач важное значение имеет теорема о ранге матрицы:

Ранг матрицы транспортной задачи на 1 меньше числа уравнений(r=m+n-1).

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

1.Определение исходного опорного плана.

2.Оценка этого плана.

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

Существуют различные способы реализации этапов решения транспортной задачи:

Правило северо-западного угла

Правило минимального элемента

Метод Фогеля4

Метод потенциалов

Метод потенциалов

Перейдем к построению оптимального плана перевозок. По данному опорному плану, у которого число занятых клеток m+n-1. Каждому поставщику и каждому потребителю передается число, называемое потенциалом. Потенциалы выбираются так, чтобы их сумма для каждой загруженной грузом клетки была равна тарифу перевозки единицы груза. Так если клетка (I,k) – базисная(занятая), то u i +v k =C ik где у итое потенциал итого поставщика.

Тогда вычисляем оценки свободных клеток по формуле: S ij =C ij -(U i +V j)

Если для свободных клеток все оценки S ij больше или ровны 0, то полученный план перевозок оптимален. При наличии хотя бы одной оценки S ij < 0 число базисных вводят в клетку, для которой оценка S ij минимальной. Для такой клетки строится цикл и производится перемещение груза так, чтобы баланс цикла сохранялся.

A/B	B 1 (80)	B 2 (170)	B 3 (150)	B 4 (180)	B 5 (70)
A 1 (300)	4/80	7/-	1/150	5/-	2/70
A 2 (150)	6/-	2/-	4/-	1/150	3/0
A 3 (200)	5/-	6/170	7/-	4/30	8/-

U 3 =
В заполненой клетке таріф равен сумме потенциалов

A/B	B 1 (80)	B 2 (170)	B 3 (150)	B 4 (180)	B 5 (70)
A 1 (300)	4/80	7/-	1/150	5/-	2/70
A 2 (150)	6/-	2/-	4/-	1/150	3/0
A 3 (200)	5/-	6/170	7/-	4/30	8/-

A/B	B 1 (80)	B 2 (170)	B 3 (150)	B 4 (180)	B 5 (70)
A 1 (300)	4/80	7/-	1/150	5/-	2/70
A 2 (150)	6/-	2/-	4/-	1/150	3/-
A 3 (200)	5/0	6/170	7/-	4/30	8/-

F=320+150+140+150+1020+120=1900

С помощью данного онлайн-калькулятора можно получить:

• решение двойственной задачи линейного программирования через решений прямой задачи (симплексным методом, по теореме двойственности);
• оптимальный план двойственной задачи; оценки ресурсов (двойственные оценки);
• определение дефицитных и недефицитных (избыточных) ресурсов;
• изменение целевой функции при изменении параметров; обоснование эффективности оптимального плана;
• анализ устойчивости двойственных оценок (предельное изменение b i , c i); анализ субоптимальных вариантов плана.

Инструкция . Выберите количество переменных и количество ограничений прямой задачи линейного программирования, нажмите Далее. Полученное решение сохраняется в файле Word и Excel . При этом ограничения типа x i ≥ 0 не учитывайте. Если прямая задача ЛП не имеет решение, но требуется составить двойственную задачу или одна из переменных x i неопределена, то можно использовать этот калькулятор .

Основная идея теории двойственности : для каждой задачи линейного программирования (ЛП) существует некоторая задача ЛП, решение которой тесно связано с прямой. При этом:

• матрица ограничений двойственной задачи (ДЗ) есть транспонированная матрица прямой задачи;
• вектор "цен" для прямой задачи есть вектор правых частей ограничений задачи ДЗ и наоборот.

Общие правила составления двойственной задачи ():

Прямая	Двойственная
Целевая функция (max)	Правая часть ограничений
Правая часть ограничений	Целевая функция (min)
A - матрица ограничений	A T - матрица ограничений
i -ое ограничение: ≤ 0, (≥ 0)	Переменная y i ≥ 0, (≤ 0)
i -ое ограничение: = 0	Переменная y i ≠ 0
Переменная x j ≥ 0 (≤ 0)	j -ое ограничение: ≤ 0 (≥ 0)
Переменная x j ≠ 0	j -ое ограничение: = 0

Пример . Определим максимальное значение целевой функции F(X) = 3x 1 +5x 2 +4x 3 при следующих условиях-ограничений.
0.1x 1 + 0.2x 2 + 0.4x 3 ≤1100
0.05x 1 + 0.02x 2 + 0.02x 3 ≤120
3x 1 + x 2 + 2x 3 ≤8000

Решим прямую задачу симплексным методом.
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных.
0.1x 1 + 0.2x 2 + 0.4x 3 + 1x 4 + 0x 5 + 0x 6 = 1100
0.05x 1 + 0.02x 2 + 0.02x 3 + 0x 4 + 1x 5 + 0x 6 = 120
3x 1 + 1x 2 + 2x 3 + 0x 4 + 0x 5 + 1x 6 = 8000
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x 4 , x 5 , x 6
Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,1100,120,8000)
Поскольку задача решается на максимум, то ведущий столбец выбирают по максимальному отрицательному числу и индексной строке. Все преобразования проводят до тех пор, пока не получатся в индексной строке положительные элементы.
Переходим к основному алгоритму симплекс-метода.

План	Базис	В	x 1	x 2	x 3	x 4	x 5	x 6	min
1	x 4	1100	0.1	0.2	0.4	1	0	0	5500
	x 5	120	0.05	0.02	0.02	0	1	0	6000
	x 6	8000	3	1	2	0	0	1	8000
Индексная строка	F(X1)	0	-3	-5	-4	0	0	0	0

Итерация №0
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x 2 , так как наибольший коэффициент по модулю.
Следовательно, 1-ая строка является ведущей. Разрешающий элемент равен 0.2 и находится на пересечении ведущего столбца и ведущей строки. Формируем следующую часть симплексной таблицы. Вместо переменной x в план 1 войдет переменная x 2 . Строка, соответствующая переменной x 2 в плане 1, получена в результате деления всех элементов строки x 4 плана 0 на разрешающий элемент РЭ=0.2. На месте разрешающего элемента в плане 1 получаем 1. >В остальных клетках столбца x 2 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x 2 и столбец x 2 .
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника .
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (0.2), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

План	Базис	В	x 1	x 2	x 3	x 4	x 5	x 6	min
2	x 2	5500	0.5	1	2	5	0	0	11000
	x 5	10	0.04	0	-0.02	-0.1	1	0	250
	x 6	2500	2.5	0	0	-5	0	1	1000
Индексная строка	F(X2)	27500	-0.5	0	6	25	0	0	0

Итерация №1
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ведущего выберем столбец, соответствующий переменной x 1 , так как наибольший коэффициент по модулю.
Вычислим значения D i по строкам как частное от деления и из них выберем наименьшее:
Следовательно, 2-ая строка является ведущей. Разрешающий элемент равен 0.04 и находится на пересечении ведущего столбца и ведущей строки. Формируем следующую часть симплексной таблицы. Вместо переменной x в план 2 войдет переменная x 1 . Строка, соответствующая переменной x 1 в плане 2, получена в результате деления всех элементов строки x 5 плана 1 на разрешающий элемент РЭ=0.04. На месте разрешающего элемента в плане 2 получаем 1. В остальных клетках столбца x 1 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x 1 и столбец x 1 .
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:

Пример №2 . Для выполнения задания необходимо, чтобы одновременно взлетели 50 АК I-го вида, 30 АК 2-го вида и 45 АК 3-го вида. АК расположены на аэродромах I и II. В таблице представлено среднее время взлета (в секундах) с соответствующего аэродрома одного АК данного типа.

Номер аэродрома	Тип АК
	1	2	3
I	4	10	10
II	6	8	20

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

Решение. Обозначим через:
x 11 - АК 1-го типа на первом аэродроме,
x 12 - АК 1-го типа на втором аэродроме,
x 21 - АК 2-го типа на первом аэродроме,
x 22 - АК 2-го типа на втором аэродроме,
x 31 - АК 3-го типа на первом аэродроме,
x 32 - АК 3-го типа на втором аэродроме,

Ограничения
4x 11 + 6x 12 = 50
10x 21 + 8x 22 = 30
10x 31 + 20x 32 = 45
x 11 , x 12 , x 21 , x 22 , x 31 ,x 32 ≥ 0
x 11 , x 12 , x 21 , x 22 , x 31 ,x 32 -целые числа

Целевая функция
4x 11 + 6x 12 + 10x 21 + 8x 22 +10x 31 + 20x 32 → min

После найденного решения, ответом на первый вопрос будут значения переменных x 11 , x 12 , x 21 , x 22 , x 31 ,x 32 . Информация об ответе на второй вопрос будет расположена в разделе Интервалы устойчивости коэффициентов целевой функции.