Динамическое программирование
Задачи динамического программирования: задача распределения инвестиций, задача замены оборудования, задача Джонсона
xf1(x)f2(x)f3(x)
16.345
25.267
34.34.67.8
4563
5*76.38.2
Решить онлайн
Примеры решений Метод Гомори Графический метод Теория игр Симплекс-метод M-задача Теоремы двойственности Одноканальные СМО Задача коммивояжера Транспортная задача

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

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

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

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

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

Общие правила составления двойственной задачи (более подробно):
Прямая Двойственная
Целевая функция (max) Правая часть ограничений
Правая часть ограничений Целевая функция (min)
A - матрица ограничений AT – матрица ограничений
i-ое ограничение: ≤ 0, (≥ 0) Переменная yi ≥ 0, (≤ 0)
i-ое ограничение: = 0 Переменная yi≠ 0
Переменная xj ≥ 0 (≤ 0) j-ое ограничение: ≤ 0 (≥ 0)
Переменная xj ≠ 0 j-ое ограничение: = 0

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

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

План Базис В x1 x2 x3 x4 x5 x6 min
1 x4 1100 0.1 0.2 0.4 1 0 0 5500
x5 120 0.05 0.02 0.02 0 1 0 6000
x6 8000 3 1 2 0 0 1 8000
Индексная строка F(X1) 0 -3 -5 -4 0 0 0 0
Итерация №0
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x2, так как наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления и из них выберем наименьшее:
Следовательно, 1-ая строка является ведущей. Разрешающий элемент равен 0.2 и находится на пересечении ведущего столбца и ведущей строки. Формируем следующую часть симплексной таблицы. Вместо переменной x в план 1 войдет переменная x2. Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x4 плана 0 на разрешающий элемент РЭ=0.2. На месте разрешающего элемента в плане 1 получаем 1. >В остальных клетках столбца x2 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x2 и столбец x2.
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (0.2), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:

Посмотреть таблицу

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

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

Посмотреть таблицу
Конец итераций: найден оптимальный план. Окончательный вариант симплекс-таблицы:

План Базис В x1 x2 x3 x4 x5 x6 min
3 x2 5375 0 1 2.25 6.25 -12.5 0 11000
x1 250 1 0 -0.5 -2.5 25 0 250
x6 1875 0 0 1.25 1.25 -62.5 1 1000
Индексная строка F(X3) 27625 0 0 5.75 23.75 12.5 0 0
Оптимальный план можно записать так: x2 = 5375, x1 = 250, x6 = 1875; F(X) = 3*250 + 5*5375 = 27625

Составим двойственную задачу к прямой задаче.
0.1y1+0.05y2+3y3≤3
0.2y1+0.02y2+y3≤5
0.4y1+0.02y2+2y3≤4
1100y4+120y4+8000y4 => min
y1 ≥ 0, y2 ≥ 0, y3 ≥ 0

Решение двойственной задачи дает оптимальную систему оценок ресурсов.
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из теоремы двойственности следует, что Y = C*A-1.
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.

Определив обратную матрицу А-1 через алгебраические дополнения, получим:
Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных  x4 , x5 , x6 .
Тогда Y = C*A-1 =
Оптимальный план двойственной задачи равен: y1 = 23.75, y2 = 12.5, y3 = 0
Z(Y) = 1100*23.75+120*12.5+8000*0 = 27625
Подставим оптимальный план прямой задачи в систему ограниченной математической модели:
0.1*250 + 0.2*5375 + 0.4*0  = 1100 = 1100
0.05*250 + 0.02*5375 + 0.02*0  = 120 = 120
3*250 + 1*5375 + 2*0  = 6125 < 8000

1-ое ограничение прямой задачи выполняется как равенство. Это означает, что 1-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y1>0).
2-ое ограничение прямой задачи выполняется как равенство. Это означает, что 2-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y2>0).
3-ое ограничение выполняется как строгое неравенство, т.е. ресурс 3-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y3 = 0.
Таким образом, отличную от нуля двойственные оценки имеют лишь те виды ресурсов, которые полностью используются в оптимальном плане. Поэтому двойственные оценки определяют дефицитность ресурсов.
При постановке оптимальных двойственных оценок в систему ограничений двойственной задачи получим:
0.1*23.75 + 0.05*12.5 + 3*0  = 3 = 3
0.2*23.75 + 0.02*12.5 + 1*0  = 5 = 5
0.4*23.75 + 0.02*12.5 + 2*0  = 9.75 > 4
1-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 1-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x1>0).
2-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 2-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x2>0).
3-ое ограничение выполняется как строгое неравенство, т.е. ресурс 3-го вида использовать экономически не выгодно. И действительно в оптимальном плане прямой задачи x3 = 0.
Величина двойственной оценки показывает, на сколько возрастает значение целевой функции при увеличении дефицитного ресурса на единицу.
Например, увеличении 1-го ресурса на 1 приведет к получению нового оптимального плана, в котором целевая функция возрастает на 23.75 и станет равной: F(x) = 27625 + 23.75 = 27648.75
Проведем анализ устойчивости оптимального плана и оценим степень влияния изменения ресурсов на значение целевой функции.
Пусть каждое значение параметра целевой функции изменится на ∆ сi. Найдем интервалы, при которых будет экономически выгодно использование ресурсов.
1-ый параметр целевой функции может изменяться в пределах:

-3.8 ≤ с1 ≤ 1
Таким образом, 1-параметр может быть уменьшен на 3.8 или увеличен на 1
Интервал изменения равен: [3-3.8; 3+1] = [-0.8;4]
Если значение c1 будет лежать в данном интервале, то оптимальный план не изменится.

2-ый параметр целевой функции может изменяться в пределах:

-0.5 ≤ с2 ≤ 9.5
Таким образом, 2-параметр может быть уменьшен на 0.5 или увеличен на 9.5
Интервал изменения равен: [5-0.5; 5+9.5] = [4.5;14.5]
Если значение c2 будет лежать в данном интервале, то оптимальный план не изменится.

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

-860 ≤ b1 ≤ 100
Таким образом, 1-ый запас может быть уменьшен на 860 или увеличен на 100
Интервал изменения равен: [1100-860; 1100+100] = [240;1200]
2-ый запас может изменяться в пределах:

-10 ≤ b2 ≤ 30
Таким образом, 2-ый запас может быть уменьшен на 10 или увеличен на 30
Интервал изменения равен: [120-10; 120+30] = [110;150]
Составим субоптимальные варианты плана с учетом изменений исходных данных модели (таблицы).
Пусть 2-ый ресурс увеличили на 50

Базисные переменные Значение базисных переменных Коэффициент структурных сдвигов kc Произведение kc на (50) Расчет варианта плана
x2 5375 6.25 312.5 5687.5
x1 250 -2.5 -125 125
x6 1875 1.25 62.5 1937.5
F(X) 27625 23.75 1187.5 28812.5
Пусть 1-ый ресурс уменьшили на -5
Базисные переменные Значение базисных переменных Коэффициент структурных сдвигов kc Произведение kc на (-5) Расчет варианта плана
x2 5375 -12.5 62.5 5437.5
x1 250 25 -125 125
x6 1875 -62.5 312.5 2187.5
F(X) 27625 12.5 -62.5 27562.5

Задание: Для исходной задачи составить двойственную. Решить обе задачи симплексным методом или двойственным симплексным методом и по решению каждой из них найти решение другой. Одну из задач решить графическим методом.
F(X) = 3x1 + x2 → min
- 2x1 + x2≥4
2x1 + x2≤8
3x1 + 2x2≥6
Решение.
I этап. Приводим систему к каноническому виду.
II этап. Решаем симплекс-методом.
Примечание: Если задача решается данным калькулятором, то предыдущие два этапа пропускаем, поскольку они автоматически включены в решение.
На втором этапе окончательный вариант симплекс-таблицы имеет вид:

Базис B x1 x2 x3 x4 x5 x6 x7
x5 2 -7 0 -2 0 1 2 -1
x4 4 4 0 1 1 0 -1 0
x2 4 -2 1 -1 0 0 1 0
F(X3) 4 -5 0 -1 0 0 1-M -M
Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым. Записываем оптимальный план:
x1 = 0, x2 = 4, F(X) = 1•4 = 4

Составим двойственную задачу к прямой задаче.
- 2y1 + 2y2 + 3y3≤3
y1 + y2 + 2y3≤1
4y1 + 8y2 + 6y3 → max
y1 ≥ 0, y2 ≤ 0, y3 ≥ 0
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи. Из теоремы двойственности следует, что Y = C*A-1. Составим матрицу A из компонентов векторов, входящих в оптимальный базис.

A = (A5, A4, A2) =
001
011
-102
Определяем обратную матрицу D = А-1 через алгебраические дополнения:
D = A-1 =
20-1
-110
100
Обратите внимание, обратная матрица A-1 расположена в столбцах дополнительных переменных окончательного варианта симплекс-таблицы. Тогда Y = C*A-1 =
(0, 0, 1) x
20-1
-110
100
= (1;0;0)
Примечание: см. как умножать матрицы.
Оптимальный план двойственной задачи равен (двойственные оценки): y1 = 1, y2 = 0, y3 = 0, Z(Y) = 4*1+8*0+6*0 = 4

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

Проверим критерий оптимальности полученного решения. Если существуют такие допустимые решения X и Y прямой и двойственной задач, для которых выполняется равенство целевых функций F(x) = Z(y), то эти решения X и Y являются оптимальными решениями прямой и двойственной задач соответственно.
Связь прямой и двойственной задач состоит, в частности, в том, что решение одной из них может быть получено непосредственно из решения другой.
Двойственные оценки обладают тем свойством, что они гарантируют рентабельность оптимального плана, т.е. равенство общей оценки продукции и ресурсов, и обуславливают убыточность всякого другого плана, отличного от оптимального. В данном примере двойственная оценка (теневая или альтернативная) y1 больше всех, что означает ценность ресурса №1.

Далее решается вопрос об экономической интерпретации двойственных оценок.

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

Номер аэродрома Тип АК
1 2 3
I 4 10 10
II 6 8 20
Как следует разместить АК по аэродромам, чтобы время последовательного взлета всего наряда АК было минимальным? До какой степени можно изменить время взлета каждого АК, чтобы при этом оптимальное решение осталось прежним.

Решение. Обозначим через:
x11 – АК 1-го типа на первом аэродроме,
x12 – АК 1-го типа на втором аэродроме,
x21 – АК 2-го типа на первом аэродроме,
x22 – АК 2-го типа на втором аэродроме,
x31 – АК 3-го типа на первом аэродроме,
x32 – АК 3-го типа на втором аэродроме,

Ограничения
4x11+ 6x12 = 50
10x21+ 8x22 = 30
10x31+ 20x32 = 45
x11, x12, x21, x22, x31,x32 ≥ 0
x11, x12, x21, x22, x31,x32 –целые числа

Целевая функция
4x11+ 6x12 + 10x21+ 8x22 +10x31+ 20x32 → min

После найденного решения, ответом на первый вопрос будут значения переменных x11, x12, x21, x22, x31,x32. Информация об ответе на второй вопрос будет расположена в разделе Интервалы устойчивости коэффициентов целевой функции.

Транспортная задача
Используя метод минимального тарифа, представить первоначальный план для решения транспортной задачи. Проверить на оптимальность, используя метод потенциалов. Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
1234b
112436
243858
3276310
a4688 
Решить онлайн
Динамическое программирование
Задачи динамического программирования: задача распределения инвестиций, задача замены оборудования, задача Джонсона
xf1(x)f2(x)f3(x)
16.345
25.267
34.34.67.8
4563
5*76.38.2
Решить онлайн
Нелинейное программирование
Метод Лагранжа
Метод множителей Лагранжа
Решить онлайн