Реферат: Линейное программирование как метод оптимизации

--PAGE_BREAK--1. Общая постановка задачи линейного программирования (ЛП)

Задача линейного программирования(ЛП) состоит в нахождении минимума (или максимума) линейной функции при линейных ограничениях.

Общая формазадачи имеет вид: найти <img border=«0» width=«53» height=«16» src=«ref-1_1235019443-1044.coolpic» alt="\min сх" v:shapes="_x0000_i1025"> при условиях
<img border=«0» width=«173» height=«75» src=«ref-1_1235020487-2090.coolpic» alt="\begin{align*}& a_i x — b_i \geq 0, \quad i \in I_1, \\& a_i x — b_i = 0, \quad i \in I_2, \\& x_j \geq 0, \quad j \in J_1,\end{align*}" v:shapes="_x0000_i1026">
Где
<img border=«0» width=«547» height=«49» src=«ref-1_1235022577-3099.coolpic» alt="\begin{align*}I_1 \cup I_2 & = \{ 1, \ldots, m \}, \;I_1 \cap I_2 = \emptyset, \;J_1 \subset \{ 1, \ldots, n \}, \;x = ( x_1, \ldots, x_n )^T, \\c & = ( c_1, \ldots, c_n ), \;a_i = (a_{i1}, \ldots, a_{in}), \;i = 1, \ldots, m .\end{align*}" v:shapes="_x0000_i1027">
Здесь и далее нам удобнее считать с и аі вектор — строками, а x и b= (b1,...,bm) T — вектор столбцами.

Наряду с общей формой широко используются также каноническая и стандартная формы. Как в канонической, так и в стандартной форме
<img border=«0» width=«124» height=«20» src=«ref-1_1235025676-1184.coolpic» alt=«J_1 = \{ 1, \ldots, n \}» v:shapes="_x0000_i1028">
т.е. все переменные в любом допустимом решении задачи должны принимать неотрицательные значения (такие переменные принято называть неотрицательные в отличие от так называемых свободных переменных, на область значений которых подобное ограничение не накладывается). Отличие же между этими формами состоит в том, что в одном случае I2 = 0, а в другом — I1 = 0.

Задача ЛП в канонической форме:


<img border=«0» width=«115» height=«14» src=«ref-1_1235026860-1129.coolpic» alt=«w = cx \rightarrow \min» v:shapes="_x0000_i1029">                        (2.1)

<img border=«0» width=«60» height=«14» src=«ref-1_1235027989-1081.coolpic» alt=«Ax = b» v:shapes="_x0000_i1030">                                   (2.2)

<img border=«0» width=«52» height=«17» src=«ref-1_1235029070-1061.coolpic» alt=«x \geq 0.» v:shapes="_x0000_i1031">                                     (2.3)
Задача ЛП в стандартной форме:
<img border=«0» width=«127» height=«72» src=«ref-1_1235030131-1511.coolpic» alt="\begin{align*}w & = cx \rightarrow \min \\Ax & \geq b \\x & \geq 0.\end{align*}" v:shapes="_x0000_i1032">
В обоих случаях А есть матрица размерности m x n, i-я строка которой совпадает с вектором аi.

Задача ЛП в общей форме сводится (в определенном смысле) к задаче ЛП в канонической (стандартной) форме. Под этим понимается существование общего способа построения по исходной задаче (в общей форме) новой задачи ЛП (в нужной нам форме), любое оптимальное решение которой «легко» преобразуется в оптимальное решение исходной задачи и наоборот. (Фактически, связь между этими задачами оказывается еще более тесной). Тем самым мы получаем возможность, не теряя общности, заниматься изучением задач ЛП, представленных либо в канонической, либо в стандартной форме. Ввиду этого наши дальнейшие рассмотрения задач ЛП будут посвящены, главным образом, задачам в канонической форме.
2. Приведение задачи линейного программирования к стандартной форме
Любая задача линейного программирования приводится к стандартной (канонической) форме основной задачи линейного программирования, которая формулируется следующим образом: найти неотрицательные значения переменных X1, X2, Xn, удовлетворяющих ограничениям в виде равенств:
A11X1 + A12X2 + … + A1nXn = B1;

A21X1 + A22X2 + … + A2nXn = B2;

……………………………………

Am1X1 + Am2X2 + … + AmnXn = Bm;

Xj≥ 0, j=1,…,n
и обращающих в максимум линейную функцию этих переменных:
E= C1X1 + C2X2 + … + CnXnÞmax
При этом также требуется, чтобы правые части равенств были неотрицательны, т.е. должны соблюдаться условия:
Bj≥ 0, j=1,…,n
Приведение к стандартной форме необходимо, так как большинство методов решения задач линейного программирования разработано именно для стандартной формы. Для приведения к стандартной форме задачи линейного программирования может потребоваться выполнить следующие действия:

перейти от минимизации целевой функции к ее максимизации;

изменить знаки правых частей ограничений;

перейти от ограничений-неравенств к равенствам;

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

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

3. Примеры экономических задач, приводящихся к задачам ЛП


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

Рассмотрим некоторые из них.

Определение оптимального ассортимента. Имеются m видов ресурсов в количествах b1, b2,., bi, bm и n видов изделий. Задана матрица A=||aij||, i=1,.,m, j=1,.,n, где aij характеризует нормы расхода i-го ресурса на единицу j-го вида изделий. Эффективность производства j-го вида изделий характеризуется показателем Cj, удовлетворяющим условию линейности. Нужно определить такой план выпуска изделий (оптимальный ассортимент), при котором суммарный показатель эффективности будет наибольший.

Обозначим количество единиц k-го вида изделий, выпускаемых предприятием, через xk, <img border=«0» width=«72» height=«23» src=«ref-1_1235031642-308.coolpic» alt=«k = \overline{1, K}» v:shapes="_x0000_i1033">. Тогда математическая модель этой задачи будет иметь такой вид:
<img border=«0» width=«219» height=«43» src=«ref-1_1235031950-1817.coolpic» alt="\text{максимизировать} \; \sum_k c_k x_k" v:shapes="_x0000_i1034">                     (3.1)
при ограничениях
<img border=«0» width=«236» height=«40» src=«ref-1_1235033767-1607.coolpic» alt="\begin{align*}\sum_k a_{ik} x_k \leq b_i, \quad i = 1, 2,., m.\end{align*}" v:shapes="_x0000_i1035">                   (3.2)
Кроме ограничений на ресурсы (3.2) в эту модель можно ввести дополнительные ограничения на планируемый уровень выпуска продукции <img border=«0» width=«69» height=«20» src=«ref-1_1235035374-1116.coolpic» alt=«x_j \geq x_{j0}» v:shapes="_x0000_i1036">, xi: xj: xk = bi: bj: bk для всех i, j, k и т.д.

Оптимальное распределение взаимозаменяемых ресурсов. Имеются m видов взаимозаменяемых ресурсов а1, а2,., аm, используемых при выполнении n различных работ (задач). Объемы работ, которые должны быть выполнены, составляют b1, b2,., bi, bn единиц. Заданы числа <img border=«0» width=«26» height=«20» src=«ref-1_1235036490-568.coolpic» alt="\lambda_{ij}" v:shapes="_x0000_i1037">, указывающие, сколько единиц j-й работы можно получить из единицы і-го ресурса, а также Cij — затраты на производство j-й работы из единицы i-го ресурса. Требуется распределить ресурсы по работам таким образом, чтобы суммарная эффективность выполненных работ была максимальной (или суммарные затраты — минимальными).

Данная задача называется общей распределительной задачей. Количество единиц i-го ресурса, которое выделено на выполнение работ j-го вида, обозначим через xij.

Математическая модель рассматриваемой задачи такова:
<img border=«0» width=«219» height=«46» src=«ref-1_1235037058-1858.coolpic» alt="\text{минимизировать} \; \sum_{j=1}^n \sum_{i=1}^m c_{ij} x_{ij}" v:shapes="_x0000_i1038">                     (3.3)
при ограничениях
<img border=«0» width=«207» height=«43» src=«ref-1_1235038916-1546.coolpic» alt="\sum_{i=1}^m \lambda_{ij} x_{ij} \geq b_j, \quad j = 1, 2, ., n ," v:shapes="_x0000_i1039">                       (3.4)

<img border=«0» width=«190» height=«46» src=«ref-1_1235040462-1453.coolpic» alt="\sum_{j=1}^n x_{ij} = a_i, \quad i=1,2,.,m." v:shapes="_x0000_i1040">                         (3.5)
Ограничение (3.4) означает, что план всех работ должен быть выполнен полностью, а (3.5) означает, что ресурсы должны быть израсходованы целиком.

Примером этой задачи может быть задача о распределении самолетов по авиалиниям.

Задача о смесях. Имеется р компонентов, при сочетании которых в разных пропорциях получают разные смеси. Каждый компонент, а следовательно и смесь, содержит q веществ. Количество k-го вещества k = 1, 2,., q, входящее в состав единицы і-го компонента и в состав единицы смеси, обозначим через аik и аk соответственно.

Предположим, что аk зависит от аik линейно, то есть если смесь состоит из x1 единиц первого компонента, x2 — единицу второго компонента и т.д., то
<img border=«0» width=«118» height=«40» src=«ref-1_1235041915-1289.coolpic» alt=«a_k = \sum_i a_{ik} x_i .» v:shapes="_x0000_i1041">
Задано р величин Ci, характеризующих стоимость, массу или калорийность единицы i-го компонента, и q величин bk, указывающих минимально необходимое процентное содержание k-го вещества в смеси. Обозначим через x1, x2,.,xр значение компонента р-го вида, входящего в состав смеси.

Математическая модель этой задачи имеет такой вид:
<img border=«0» width=«207» height=«52» src=«ref-1_1235043204-1802.coolpic» alt="\text{минимизировать} \; \sum_{i=1}^p c_i x_i" v:shapes="_x0000_i1042">                       (3.6)
при ограничении
<img border=«0» width=«233» height=«52» src=«ref-1_1235045006-1671.coolpic» alt="\sum_{i=1}^p a_{ik} x_i \geq b_k, \quad k=1,2,.,q ," v:shapes="_x0000_i1043">                   (3.7)

<img border=«0» width=«81» height=«52» src=«ref-1_1235046677-1229.coolpic» alt="\sum_{i=1}^p x_i =1" v:shapes="_x0000_i1044">
Ограничение (3.7) означает, что процентное содержание k-го вещества в единице смеси должно быть не меньше bk.

К этой же модели принадлежит также задача определения оптимального рациона кормления скота.
    продолжение
--PAGE_BREAK--4. Геометрический метод решение задач ЛП


Задача 1. При откорме каждое животное должно получить не менее 14 ед.питательного вещества S1, не менее 15 ед. вещества S2и не менее 10 вещества S3. Для составления рациона используют два вида корма. Содержание количества единиц питательных веществ в 1 килограмме каждого вида корма и стоимость одного килограмма корма дана в таблице 1.
Таблица 1



Составить рацион минимальной стоимости.

Решение:
X1 + 2X2 ≥ 14

X1 + 3X2 ≥ 15

2X1 + X2 ≥ 10

X1, X2 ≥ 0

<img width=«12» height=«96» src=«ref-1_1235047906-467.coolpic» v:shapes="_x0000_s1026">3X1 + 7 X2 → min

 X1 + 2X2 = 14

X1 + 3X2 =15

2X1 + X2 = 10


<img border=«0» width=«572» height=«396» src=«ref-1_1235048373-35230.coolpic» v:shapes="_x0000_i1045">
5. Симплексный метод решения задач ЛП


Задача 2. Для изготовления 4-ёх видов продукции P1, P2, P3, P4используют два вида сырья: S1и S2. Запасы сырья, количество единиц сырья, затрачиваемых на изготовление единицы продукции, а так же величина прибыли, получаемая от реализации единицы продукции, приведены в таблице 2.
Таблица 2.



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

Решение:

1. Формальная постановка задачи имеет следующий вид:
9X1 + 14X2 + 15 X3 + 10X4 → max

X1 + X2 + X3 + 2X4 ≤ 3

X1 + 2X2 + 3X3 + X4 ≤ 7

X1, X2, X3, X4 ≥ 0
2. Приведем к стандартной (канонической) форме:
F = 9X1 + 14X2 +15X3 + 10X4 + 0X5 + 0X6

X1 + X2 + X3 + 2X4 + X5 = 3

X1 + 2X2 +3X3 + X4 + X6 = 7

X1, X2, X3, X4 ≥ 0
3. Запишем систему ограничений в векторной форме:
X1 (1/1) + X2 (1/2) + X3 (1/3) + X4 (2/1) + X5 (1/0) + X6 (0/1) = (3/7)

P1 P2 P3 P4 P5 P6 P0

P5, P6 — базисные
4. Запишем первоначальный опорный план:
Х0 (0, 0, 0, 0, 3,7), F0 = 9*0 + 14*0 +15*0 +10*0 + 0*3 +0*7 = 0
Составим соответствующую плану 1 симплексную таблицу:





Вычислим оценки:
∆ = (Сб*А) — С

∆1 = (0 *1 + 0*1) — 9 = — 9; ∆2 = (0 *1 + 0*2) — 14 = — 14; ∆3 = (0 *1 + 0*3) — 15 = — 15; ∆4 = (0 *2 + 0*1) — 10 = — 10; ∆5 = (0 *1 + 0*0) — 0 = 0; ∆6 = (0 *0 + 0*1) — 0 = 0
Критерием оптимальности является условие, что все ∆ ≥ 0, т.к. это не так, решение не оптимально.

Выберем вектор, который будем включать в базис:
min1 = (3/1; 7/1) = 3; min2 = (3/1; 7/2) =3; min3 = (3/1; 7/3) = 2 1/3; min4 = (3/2; 7/1) = 1 1/2,
теперь посмотрим соотношение minc∆:
∆
f= — ∆*
min

∆
f1 = — (-9) *3 = 27; ∆f2 = — (-14) *3 = 42; ∆f3 = — (-15) *2 1/3 = 34.95; ∆f4 = — (-10) *1 1/2 = 15,
Отсюда следует, что менять будем Р5 на Р2.

5. Составим 2 симплексную таблицу:





7- (3*2) /1 = 1; 1 — (1*2) /1 = — 1; 3 — (2*1) /1 = 1; 1- (2*1) /1 = — 1; 0- (1*1) /1 = — 1; 1- (0*1) /1 = 1

∆1 = 14*1+0* (-1) — 9 = 5; ∆3 = 14*1+0*1-15 = — 1; ∆4 = 14*2+0* (-1) — 10 = 4;

∆5 = 14*1+0* (-1) — 0 = 14; ∆6 = 14*0+0*1-0 = 0;

Х1 (0,3,0,0,0,1); F1 = 9*0+14*3+15*0+10*0+0*0+0*1 = 42
Приняв этот план видим, что выпуск 2го вида продукции является наиболее выгодным, остаток сырья 2го вида продукции составит 1 единица.

Т.к. не все ∆ ≥ 0, план не является оптимальным, поэтому продолжим…..

Вектором Р3 заменим Р6 min= (3/1, 1/1) = (3,1)

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





3-1*1/1=2; 1- (-1) *1/1=2; 1-0*1/1=1; 2-1* (-1) /1=3; 1-1* (-1) /1=2; 0-1*1/1=-1

∆1 = 14*2+15* (-1) — 9 = 4; ∆2 = 14*1+15*0-14 = 0; ∆4 = 14*3+15* (-1) — 10 = 17;

∆5 = 14*2+15* (-1) — 0 = 13; ∆6 = 14* (-1) +15*1-0 = 1;

Х2 = (0,2,1,0,0,0); F2 = 9*0+14*2+15*1+0 = 43
План является оптимальным, говорим о том, что наиболее выгодным является производство 2единиц 2 вида продукции и 1единицы 3 вида продукции, причем сырье расходуется полностью.

    продолжение
--PAGE_BREAK--6. Теоремы двойственности и их использование в задачах ЛП


Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу (линейного программирования), называемую двойственной или сопряженной по отношению к исходной или прямой задаче. Дадим определение двойственной задачи по отношению к общей задаче линейного программирования, состоящей, как мы уже знаем, в нахождении максимального значения функции
<img border=«0» width=«207» height=«29» src=«ref-1_1235083603-2150.coolpic» v:shapes="_x0000_i1046"> (42)
при условиях
<img border=«0» width=«199» height=«127» src=«ref-1_1235085753-6899.coolpic» v:shapes="_x0000_i1047"> (43)

<img border=«0» width=«115» height=«23» src=«ref-1_1235092652-1042.coolpic» v:shapes="_x0000_i1048"> (44)

Определение.

Задача, состоящая в нахождении минимального значения функции
<img border=«0» width=«156» height=«20» src=«ref-1_1235093694-1235.coolpic» v:shapes="_x0000_i1049"> (45)
при условиях


<img border=«0» width=«213» height=«141» src=«ref-1_1235094929-1519.coolpic» v:shapes="_x0000_i1050"> (46)

<img border=«0» width=«121» height=«20» src=«ref-1_1235096448-1147.coolpic» v:shapes="_x0000_i1051"> (47)
называется двойственной по отношению к задаче (42) — (44). Задачи (42) — (44) и (45) — (47) образуют пару задач, называемую в линейном программировании двойственной парой. Сравнивая две сформулированные задачи, видим, что двойственная задача составляется согласно следующим правилам:

1. Целевая функция исходной задачи (42) — (44) задается на максимум, а целевая функция двойственной (45) — (47) — на минимум.

2. Матрица
<img border=«0» width=«153» height=«84» src=«ref-1_1235097595-704.coolpic» v:shapes="_x0000_i1052"> (48)
составленная из коэффициентов при неизвестных в системе ограничений (43) исходной задачи (42) — (44), и аналогичная матрица
<img border=«0» width=«150» height=«84» src=«ref-1_1235098299-709.coolpic» v:shapes="_x0000_i1053"> (49)
в двойственной задаче (45) — (47) получаются друг из друга транспонированием (т.е. заменой строк столбцами, а столбцов — строками).

3. Число переменных в двойственной задаче (45) — (47) равно числу ограничений в системе (43) исходной задачи (42) — (44), а число ограничений в системе (46) двойственной задачи — числу переменных в исходной задаче.

4. Коэффициентами при неизвестных в целевой функции (45) двойственной задачи (45) — (47) являются свободные члены в системе (43) исходной задачи (42) — (44), а правыми частями в соотношениях системы (46) двойственной задачи — коэффициенты при неизвестных в целевой функции (42) исходной задачи.

5. Если переменная xj исходной задачи (42) — (44) может принимать только лишь положительные значения, то j-е условие в системе (46) двойственной задачи (45) — (47) является неравенством вида “". Если же переменная xj может принимать как положительные, так и отрицательные значения, то 1 — соотношение в системе представляет собой уравнение. Аналогичные связи имеют место между ограничениями (43) исходной задачи (42) — (44) и переменными двойственной задачи (45) — (47). Если i — соотношение в системе (43) исходной задачи является неравенством, то i-я переменная двойственной задачи <img border=«0» width=«37» height=«20» src=«ref-1_1235099008-514.coolpic» v:shapes="_x0000_i1054">. В противном случае переменная уj может принимать как положительные, так и отрицательные значения.

Двойственные пары задач обычно подразделяют на симметричные и несимметричные. В симметричной паре двойственных задач ограничения (43) прямой задачи и соотношения (46) двойственной задачи являются неравенствами вида “<img border=«0» width=«14» height=«17» src=«ref-1_1235099522-330.coolpic» v:shapes="_x0000_i1055">". Таким образом, переменные обеих задач могут принимать только лишь неотрицательные значения.

Теорема двойственности.

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

Лемма 1.

Если Х — некоторый план исходной задачи, a Y — произвольный план двойственной задачи, то значение целевой функции исходной задачи при плане Х всегда не превосходит значения целевой функции двойственной задачи при плане Y, т.е. <img border=«0» width=«84» height=«20» src=«ref-1_1235099852-954.coolpic» v:shapes="_x0000_i1056">

Лемма 2.

Если <img border=«0» width=«86» height=«20» src=«ref-1_1235100806-955.coolpic» v:shapes="_x0000_i1057">для некоторых планов X* и Y* задач, то X* — оптимальный план исходной задачи, а Y* — оптимальный план двойственной задачи.

Теорема 8

(первая теорема двойственности). Если одна из задач двойственной пары или, имеет оптимальный план, то и другая имеет оптимальный план и значения целевых функций задач при их оптимальных планах равны между собой, т.е. <img border=«0» width=«69» height=«20» src=«ref-1_1235101761-725.coolpic» v:shapes="_x0000_i1058">

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

Теорема 9

(вторая теорема двойственности).

План <img border=«0» width=«109» height=«20» src=«ref-1_1235102486-1063.coolpic» v:shapes="_x0000_i1059">задачии план <img border=«0» width=«112» height=«20» src=«ref-1_1235103549-1123.coolpic» v:shapes="_x0000_i1060">задачи, являются оптимальными планами этих задач тогда и только тогда, когда для любого <img border=«0» width=«58» height=«20» src=«ref-1_1235104672-690.coolpic» v:shapes="_x0000_i1061">выполняется равенство


<img border=«0» width=«124» height=«49» src=«ref-1_1235105362-435.coolpic» v:shapes="_x0000_i1062">

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

1) обе задачи имеют планы;

2) планы имеет только одна задача;

3) для каждой задачи двойственной пары множество планов пусто.

а) Составить задачу двойственную к примеру 2.

б) Найти её решение любым методом.

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

а) Задача имеет вид:





1

1





1

2





1

3





2

1



 f = 9X1 + 14X2 + 15 X3 + 10X4 → max



1

1

1

2





1

2

3

1



X1 + X2 + X3 + 2X4 ≤ 3

X1 + 2X2 + 3X3 + X4 ≤ 7

X1, X2, X3, X4 ≥ 0
Составим двойственную задачу по следующей схеме:

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

в дв. задаче меняется вид экстремума (min→max);

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

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

знаки в системе ограничений двойственной задачи определяются знаками ограничений неотрицательности в исходной задаче.
<img width=«10» height=«84» src=«ref-1_1235105797-422.coolpic» hspace=«12» v:shapes="_x0000_s1027">g = 3Y1+7Y2 → min

Y1 + Y2 ≥ 9

Y1 + 2Y2 ≥ 14

Y1 + 3Y2 ≥ 15

2Y1 + Y2 ≥ 10

Y1, Y2 ≥ 0

б) Решим задачу графическим методом
<img border=«0» width=«477» height=«332» src=«ref-1_1235106219-24786.coolpic» v:shapes="_x0000_i1063">
в) Оптимальным планом задачи 2, решенной симплексным методом является:
Х2 = (0,2,1,0,0,0); F2 = 9*0+14*2+15*1+0 = 43
Используя 3 симплексную таблицу найдем оптимальный план двойственной задачи.

Из 1 теоремы двойственности следует что: Y=Cб*А — 1

Составим матрицу А из компонентов векторов входящих в оптимальный базис





1

1





2

3



А = Р2; Р3 =
Определим обратную матрицу А-1:





2

-1





-1

1





А-1 =Р5; Р6= = (12;
1)

Оптимальный план двойственности равен:
Y= (12, 1, 0, 0, 0, 0); G= 3*12+7*1 = 43
Подставим оптимальный план прямой задачи в систему ограничений

<img width=«16» height=«132» src=«ref-1_1235131005-793.coolpic» hspace=«12» v:shapes="_x0000_s1028">

12+1 > 9

12+2*1 = 14

12+3*1 = 15

2*12+1 > 10
Первое ограничение двойственной задачи выполняется как строгое неравенство. Это означает, что двойственная оценка сырья, используемого на производство одного изделия 1 и 4 вида, выше цены этого изделия и, следовательно, выпускать изделия этих видов невыгодно. Его производство и не предусмотрено оптимальным планом прямой задачи. Второе и третье ограничения двойственной задачи выполняются как строгие равенства. Это означает, что двойственные оценки сырья, используемого для производства единицы соответственно изделий 2 и 3 вида, равны в точности их ценам. Поэтому выпускать эти два вида продукции по двойственным оценкам экономически целесообразно. Их производство и предусмотрено оптимальным планом прямой задачи.

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

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

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

На итерации, приводящей к оптимуму, <img border=«0» width=«199» height=«23» src=«ref-1_1235131798-480.coolpic» v:shapes="_x0000_i1064"> Это равенство справедливо всегда и фактически соответствует оптимальным значениям переменных обеих задач.

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

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

Значение линейной функции двойственной задачи от Y численно равно минимальному значению линейной функции исходной задачи

Пропустим процесс решения двойственной ЗЛП, записав только результаты:
Y1=12 Y2=1 Y3=0 min (φ) =43
Т.к max (f) =min (φ), решение исходной задачи уже известно. Остаётся только найти значения X1, X2, X3, при которых это значение достигается. Здесь мы применим вторую теорему двойственности, которая устанавливает следующее соответствие:


<img border=«0» width=«440» height=«148» src=«ref-1_1235132278-2060.coolpic» v:shapes="_x0000_i1065">
В нашем примере получается следующая система линейных уравнений:
<img width=«17» height=«135» src=«ref-1_1235134338-818.coolpic» hspace=«12» v:shapes="_x0000_s1029">Y1 + Y2 = 9

Y1 + 2Y2 = 14

Y1 + 3Y2 = 15

2Y1 + Y2 = 10

С= (3,7) y1=12 y2=1 т.к. у1>0 и y2>0, то

<img width=«14» height=«112» src=«ref-1_1235135156-216.coolpic» hspace=«12» v:shapes="_x0000_s1030">X1 + X2 + X3 + 2X4 =3

X1 + 2X2 + 3X3 + X4 =7

12+1≠ 9, х1=0

12+2*1=14 → х2≠ 0

12+3*1=15→ х3≠ 0

2*12+1≠10, х4=0

х2+х3=3 Х2*=2

2х2+3х3=7 Х3*=1

F= 9*0+14*2+15*1+0 = 43
    продолжение
--PAGE_BREAK--