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

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

Двойственность является важным понятием в линейном программировании, имеющим экономическое (практическое) применение. Например, для задачи оптимального распределения ресурсов для производства некоторых видов товаров пара прямой и двойственной задачи принимает следующий экономический смысл:
Прямая задача: Сколько и какой продукции xj необходимо производить, чтобы при заданных доходах Cj и объемах ресурсов bi максимизировать доход от продажи продукции?
Двойственная задача: Какова должна быть «теневая» цена каждого ресурса yi, чтобы при заданных количествах bi и доходах Cj минимизировать затраты?

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

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

Примеры составления и решения двойственных задач онлайн

Задача 1. Записать математическую модель двойственной ЗЛП по заданной прямой:

Задача 2. Составить задачу, двойственную исходной задаче:

Задача 3. Решить задачу линейного программирования; составить задачу, двойственную данной, и также найти ее решение:

Источник

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

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

Определив обратную матрицу А -1 через алгебраические дополнения, получим:
Как видно из последнего плана симплексной таблицы, обратная матрица A -1 расположена в столбцах дополнительных переменных x₄ , x₅ , x₆ .
Тогда Y = C*A -1 =
Оптимальный план двойственной задачи равен: y₁ = 23.75, y₂ = 12.5, y₃ = 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-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y₁>0).
2-ое ограничение прямой задачи выполняется как равенство. Это означает, что 2-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y₂>0).
3-ое ограничение выполняется как строгое неравенство, т.е. ресурс 3-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y₃ = 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-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x₁>0).
2-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 2-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x₂>0).
3-ое ограничение выполняется как строгое неравенство, т.е. ресурс 3-го вида использовать экономически не выгодно. И действительно в оптимальном плане прямой задачи x₃ = 0.
Величина двойственной оценки показывает, на сколько возрастает значение целевой функции при увеличении дефицитного ресурса на единицу.
Например, увеличении 1-го ресурса на 1 приведет к получению нового оптимального плана, в котором целевая функция возрастает на 23.75 и станет равной: F(x) = 27625 + 23.75 = 27648.75
Проведем анализ устойчивости оптимального плана и оценим степень влияния изменения ресурсов на значение целевой функции.
Пусть каждое значение параметра целевой функции изменится на ∆ с_i. Найдем интервалы, при которых будет экономически выгодно использование ресурсов.
1-ый параметр целевой функции может изменяться в пределах:

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

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

Базисные переменные	Значение базисных переменных	Коэффициент структурных сдвигов k c	Произведение k c на (50)	Расчет варианта плана
x 2	5375	6.25	312.5	5687.5
x 1	250	-2.5	-125	125
x 6	1875	1.25	62.5	1937.5
F(X)	27625	23.75	1187.5	28812.5

Пусть 1-ый ресурс уменьшили на -5

Базисные переменные	Значение базисных переменных	Коэффициент структурных сдвигов k c	Произведение k c на (-5)	Расчет варианта плана
x 2	5375	-12.5	62.5	5437.5
x 1	250	25	-125	125
x 6	1875	-62.5	312.5	2187.5
F(X)	27625	12.5	-62.5	27562.5

Задание : Для исходной задачи составить двойственную. Решить обе задачи симплексным методом или двойственным симплексным методом и по решению каждой из них найти решение другой. Одну из задач решить графическим методом.
F(X) = 3x₁ + x₂ → min
— 2x₁ + x₂≥4
2x₁ + x₂≤8
3x₁ + 2x₂≥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

Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым. Записываем оптимальный план:
x₁ = 0, x₂ = 4, F(X) = 1•4 = 4 Составим двойственную задачу к прямой задаче.
— 2y₁ + 2y₂ + 3y₃≤3
y₁ + y₂ + 2y₃≤1
4y₁ + 8y₂ + 6y₃ → max
y₁ ≥ 0, y₂ ≤ 0, y₃ ≥ 0
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи. Из теоремы двойственности следует, что Y = C*A -1 . Составим матрицу A из компонентов векторов, входящих в оптимальный базис.

Источник

Решение двойственной задачи

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

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

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

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

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

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

Вторая теорема двойственности

Пусть мы имеем симметричную пару двойственных задач (1) и (2):
(1.1) ;
(1.2)
(2.1) ;
(2.2)
Для того чтобы допустимые решения и являлись оптимальными решениями двойственных задач (1) и (2),
необходимо и достаточно, чтобы выполнялись следующие равенства:
(3) , ;
(4) , .

Для наглядности, выпишем равенства (3) и (4) в развернутом виде:
(3.1)
(3.2)

(3.m)

Метод решения двойственной задачи

Применяя теоремы двойственности, можно получить решение двойственной задачи из решения прямой. Опишем метод решения двойственной задачи.

Пусть мы нашли решение прямой задачи (1) с оптимальным значением целевой функции и с оптимальным планом . Подставим найденные значения в систему ограничений (1.2). Тогда если -е неравенство не является равенством, то есть если
,
то, согласно (3.i),
.
Рассматривая все строки системы ограничений (1.2), мы найдем, что часть переменных двойственной задачи равна нулю.

Далее замечаем, что если , то, согласно (4.k), -я строка системы ограничений (2.2) является равенством:
.
Составив все строки системы ограничений (2.2), для которых , мы получим систему уравнений, из которой можно найти ненулевые значения переменных .

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

Если известно решение задачи (2), то аналогичным образом можно найти решение задачи (1).

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

Пример 1

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

Известно решение этой задачи:
; .

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

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

Применим вторую теорему двойственности. Подставим оптимальные значения переменных в систему ограничений прямой задачи.
(П1.1.1) ;
(П1.1.2) ;
(П1.1.3) ;
(П1.1.4) .
Поскольку первая и четвертая строки являются строгими неравенствами (не являются равенствами), то
и .

Поскольку и , то 2-я и 4-я строки двойственной задачи являются равенствами:

Подставим уже найденные значения и , имеем:

Отсюда
;
; .

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

Ее решение
;

Пример 2

Дана задача линейного программирования:
(П2.1.1) ;
(П2.1.2)
Найти решение этой задачи, решив двойственную задачу графическим методом.

Решение задачи (П2.2) приводится на странице “Решение задач линейного программирования графическим методом”. Решение задачи (П2.2) имеет вид:
; .

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

Применим вторую теорему двойственности. Подставим оптимальные значения переменных в систему ограничений прямой задачи (П2.2).
;
;
.
Поскольку третья строка является строгим неравенством (не являются равенством), то
.

Поскольку и , то 1-я и 2-я строки двойственной задачи (П2.1) являются равенствами:

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

Решаем систему уравнений.
;
;
;
; ;
.

Решение исходной задачи (П2.1) имеет вид:
; .

Автор: Олег Одинцов . Опубликовано: 27-08-2016

Источник

A = (A5, A4, A2) =