Вектор коэффициентов целевой функции двойственной задачи

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

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

  • решение двойственной задачи линейного программирования через решений прямой задачи (симплексным методом, по теореме двойственности);
  • оптимальный план двойственной задачи; оценки ресурсов (двойственные оценки);
  • определение дефицитных и недефицитных (избыточных) ресурсов;
  • изменение целевой функции при изменении параметров; обоснование эффективности оптимального плана;
  • анализ устойчивости двойственных оценок (предельное изменение bi, ci); анализ субоптимальных вариантов плана.
  • решение задачи о расшивке узких мест производства.
  • Шаг №1
  • Шаг №2
  • Видеоинструкция
  • Оформление Word

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

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

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

ПрямаяДвойственная
Целевая функция (max)Правая часть ограничений
Правая часть ограниченийЦелевая функция (min)
A — матрица ограниченийA T – матрица ограничений
i -ое ограничение: ≤ 0, (≥ 0)Переменная yi ≥ 0, (≤ 0)
i -ое ограничение: = 0Переменная yi≠ 0
Переменная xj ≥ 0 (≤ 0)j -ое ограничение: ≤ 0 (≥ 0)
Переменная xj ≠ 0j -ое ограничение: = 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)
Поскольку задача решается на максимум, то ведущий столбец выбирают по максимальному отрицательному числу и индексной строке. Все преобразования проводят до тех пор, пока не получатся в индексной строке положительные элементы.
Переходим к основному алгоритму симплекс-метода.

ПланБазисВx 1x 2x 3x 4x 5x 6min
1x 411000.10.20.41005500
x 51200.050.020.020106000
x 680003120018000
Индексная строкаF(X1)0-3-5-40000
Итерация №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), А и В — элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:

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

ПланБазисВx 1x 2x 3x 4x 5x 6min
2x 255000.51250011000
x 5100.040-0.02-0.110250
x 625002.500-5011000
Индексная строкаF(X2)27500-0.50625000

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

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

ПланБазисВx 1x 2x 3x 4x 5x 6min
3x 25375012.256.25-12.5011000
x 125010-0.5-2.5250250
x 61875001.251.25-62.511000
Индексная строкаF(X3)27625005.7523.7512.500
Оптимальный план можно записать так: x2 = 5375, x1 = 250, x6 = 1875; F(X) = 3*250 + 5*5375 = 27625

Решение двойственной задачи дает оптимальную систему оценок ресурсов.
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из теоремы двойственности следует, что 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 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

Базисные переменныеЗначение базисных переменныхКоэффициент структурных сдвигов k cПроизведение k c на (50)Расчет варианта плана
x 253756.25312.55687.5
x 1250-2.5-125125
x 618751.2562.51937.5
F(X)2762523.751187.528812.5
Пусть 1-ый ресурс уменьшили на -5

Базисные переменныеЗначение базисных переменныхКоэффициент структурных сдвигов k cПроизведение k c на (-5)Расчет варианта плана
x 25375-12.562.55437.5
x 125025-125125
x 61875-62.5312.52187.5
F(X)2762512.5-62.527562.5

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

БазисBx1x2x3x4x5x6x7
x52-70-2012-1
x4440110-10
x24-21-10010
F(X3)4-50-1001-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. В таблице представлено среднее время взлета (в секундах) с соответствующего аэродрома одного АК данного типа.

Номер аэродромаТип АК
123
I41010
II6820

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

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

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

Видео:Урок 2. Экономический смысл двойственной задачиСкачать

Урок 2. Экономический смысл двойственной  задачи

Двойственная задача линейного программирования. Онлайн калькулятор

С помощю этого онлайн калькулятора можно построить двойственную задачу линейного программирования (ЛП) по отношению к исходной задаче. Для построения двойственной задачи, введите данные исходной задачи и нажмите на кнопку «Вычислить». Теоретическую часть и численные примеры смотрите ниже.

Предупреждение

Запись

  • Содержание
  • 1. Построение двойственной задачи к исходной задаче линейного программирования
  • 2. Теория двойственности в задачах линейного программирования
  • 3. Двойственные к разным формам задач линейного программирования
  • 4. Условие дополняющей нежесткости

Видео:Прямая и двойственная задачи линейного программирования (ЗЛП)Скачать

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

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

Пусть задана прямая задача линейного программирования (ЛП) в общем виде:

Вектор коэффициентов целевой функции двойственной задачи(1a)
Вектор коэффициентов целевой функции двойственной задачи(1b)
Вектор коэффициентов целевой функции двойственной задачи(1c)
Вектор коэффициентов целевой функции двойственной задачи(1d)
Вектор коэффициентов целевой функции двойственной задачи(1e)

Задаче (1) соответствует следующая двойственная задача ЛП:

Вектор коэффициентов целевой функции двойственной задачи(2a)
Вектор коэффициентов целевой функции двойственной задачи(2b)
Вектор коэффициентов целевой функции двойственной задачи(2c)
Вектор коэффициентов целевой функции двойственной задачи(2d)
Вектор коэффициентов целевой функции двойственной задачи(2e)

В этих задачах знак ∀ — определяет, что на данную переменную не налагается ограничение в виде неотрицательности, т.е. она произвольная.

Отметим, что если задача ЛП (2) является двойственной к задаче ЛП (1), то задача ЛП (1) является двойственной к задаче ЛП (2). Говорят, что задачи ЛП (1) и (2) взаимно двойственные задачи линейного программирования.

Рассмотрим подробно процесс построения двойственной задачи к исходной задачи линейного программирования. Для построения двойственной задачи:

1. Упорядочивается запись исходной задачи ЛП: если целевая функция исследуется на максимум, то ограничения (1b), (1c) должны иметь знак или «=», или «≤», а если целевая функция исследуется на минимум, то ограничения (1b), (1c) должны иметь знак или «=» , или «≥». Если в исходной задаче ЛП есть ограничения, не удовлетворяющие этим условиям, то это можно исправить, умножая данное ограничение на −1.

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

3. Если в исходной задаче целевая функция исследуется на максимум, то целевая функция двойственной задачи исследуется на минимум.

4. Свободные члены исходной задачи становятся коэффициентами целевой функции двойственной задачи.

5. Коэффициенты целевой функции исходной задачи становятся свободными членами двойственной задачи.

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

7. Если на переменную Вектор коэффициентов целевой функции двойственной задачиналожено ограничение в виде неотрицательности, то j-е ограничение двойственной задачи записывается в виде неравенства. Если же переменная Вектор коэффициентов целевой функции двойственной задачиисходной задачи произвольная, то j-е ограничение двойственной задачи имеет знак равенства.

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

Чтобы посмотреть пример построения двойственной задачи воспользуйтесь онлайн калькулятором в начале страницы. Для этого введите коэффициенты исходной задачи в ячейки калькулятора и нажмите на кнопку «Построить».

Видео:Графический метод решения задачи линейного программирования (ЗЛП)Скачать

Графический метод решения задачи линейного программирования (ЗЛП)

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

Утверждение 1. Если X и Y − допустимые точки задач (1) и (2), соответственно, то

Вектор коэффициентов целевой функции двойственной задачи.(3)

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

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

Вектор коэффициентов целевой функции двойственной задачи(4a)
Вектор коэффициентов целевой функции двойственной задачи(4b)
Вектор коэффициентов целевой функции двойственной задачи(4c)
Вектор коэффициентов целевой функции двойственной задачи(4d)

где Вектор коэффициентов целевой функции двойственной задачи,Вектор коэффициентов целевой функции двойственной задачи,Вектор коэффициентов целевой функции двойственной задачи,Вектор коэффициентов целевой функции двойственной задачи,Вектор коэффициентов целевой функции двойственной задачи,Вектор коэффициентов целевой функции двойственной задачи,

Вектор коэффициентов целевой функции двойственной задачи

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

Сделаны также следующие обозначения:

Вектор коэффициентов целевой функции двойственной задачи, Вектор коэффициентов целевой функции двойственной задачи, Вектор коэффициентов целевой функции двойственной задачи
Вектор коэффициентов целевой функции двойственной задачи(5a)
Вектор коэффициентов целевой функции двойственной задачи(5b)
Вектор коэффициентов целевой функции двойственной задачи(5c)
Вектор коэффициентов целевой функции двойственной задачи(5d)

где Вектор коэффициентов целевой функции двойственной задачи, Вектор коэффициентов целевой функции двойственной задачи, Вектор коэффициентов целевой функции двойственной задачи.

Вектор коэффициентов целевой функции двойственной задачиВектор коэффициентов целевой функции двойственной задачи
Вектор коэффициентов целевой функции двойственной задачиВектор коэффициентов целевой функции двойственной задачиВектор коэффициентов целевой функции двойственной задачиВектор коэффициентов целевой функции двойственной задачи(6)

(5b) и (5c) можно записать так:

Вектор коэффициентов целевой функции двойственной задачи, Вектор коэффициентов целевой функции двойственной задачи(7)

Легко показать, что

Вектор коэффициентов целевой функции двойственной задачи(8)
Вектор коэффициентов целевой функции двойственной задачиВектор коэффициентов целевой функции двойственной задачи(9)

Множители в правой части выражения (9) неотрицательны. Тогда их произведение не отрицательно, т.е. выполнено условие (8).

Учитывая (7) и (8) упростим выражение 6:

Вектор коэффициентов целевой функции двойственной задачи(9)

С другой стороны:

Вектор коэффициентов целевой функции двойственной задачиВектор коэффициентов целевой функции двойственной задачи(10)
Вектор коэффициентов целевой функции двойственной задачиВектор коэффициентов целевой функции двойственной задачиВектор коэффициентов целевой функции двойственной задачиВектор коэффициентов целевой функции двойственной задачиВектор коэффициентов целевой функции двойственной задачи(11)

(4b) и (4c) можно записать так

Вектор коэффициентов целевой функции двойственной задачиВектор коэффициентов целевой функции двойственной задачи(12)

Учитывая (12) и Y1 упростим выражение (11):

Вектор коэффициентов целевой функции двойственной задачи(13)

Из (9) и (13) получим:

Вектор коэффициентов целевой функции двойственной задачи(14)

т.е. выполнено условие (3).

Докажем вторую часть утверждения 1. Для любой допустимой точки x задачи (1) Вектор коэффициентов целевой функции двойственной задачив том числе Вектор коэффициентов целевой функции двойственной задачи. Тогда

Вектор коэффициентов целевой функции двойственной задачи

Поэтому Вектор коэффициентов целевой функции двойственной задачинаибольшее значение целевой функции задачи (1).

С другой стороны для любой допустимой точки y задачи (2)

Вектор коэффициентов целевой функции двойственной задачи

т.е. Вектор коэффициентов целевой функции двойственной задачи− наименьшее из значений целевой функции задачи (2). Таким образом получили, что Вектор коэффициентов целевой функции двойственной задачиявляется решением задачи (1), а Вектор коэффициентов целевой функции двойственной задачиявляется решением задачи (2).

Теорема 1 (первая теорема двойственности). Если исходная задача имеет решение Вектор коэффициентов целевой функции двойственной задачи, то двойственная ей задача также имеет решение Вектор коэффициентов целевой функции двойственной задачи, и

Вектор коэффициентов целевой функции двойственной задачи.

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

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

Вектор коэффициентов целевой функции двойственной задачиВектор коэффициентов целевой функции двойственной задачи

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

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

Вектор коэффициентов целевой функции двойственной задачи(15)
Вектор коэффициентов целевой функции двойственной задачи,(16)

или выполняется условие:

Вектор коэффициентов целевой функции двойственной задачи.(17)

Докажем эквивалентность условий (15) и (16) с условием (17).

Из (4с) и (5с) имеем:

Вектор коэффициентов целевой функции двойственной задачи, Вектор коэффициентов целевой функции двойственной задачи.(18)
Вектор коэффициентов целевой функции двойственной задачи,(19)
Вектор коэффициентов целевой функции двойственной задачи.(20)

Из (15) и (16) имеем:

Вектор коэффициентов целевой функции двойственной задачиВектор коэффициентов целевой функции двойственной задачи.(21)
Вектор коэффициентов целевой функции двойственной задачиВектор коэффициентов целевой функции двойственной задачи,(22)

Подставляя (19),(20) в (21),(22) соответственно и упрощая получим:

Вектор коэффициентов целевой функции двойственной задачиВектор коэффициентов целевой функции двойственной задачи,(23)
Вектор коэффициентов целевой функции двойственной задачиВектор коэффициентов целевой функции двойственной задачи,(24)

Выразив, например, Вектор коэффициентов целевой функции двойственной задачичерез остальные слагаемые из (23) и подставляя в (24) получим:

Вектор коэффициентов целевой функции двойственной задачи
Вектор коэффициентов целевой функции двойственной задачи.(25)

А Запись (25) − это другой вид записи равенства (17).

Видео:Двойственная задача. Как составить и решить? Вторая теорема двойственностиСкачать

Двойственная задача. Как составить и решить? Вторая теорема двойственности

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

В статье Формы записи задачи линейного программирования мы рассмотрели различные формы записи задачи линейного программирования. В этом параграфе мы рассмотрим двойственные задачи к задачам ЛП в различных формах.

1) Двойственной к задаче ЛП в канонической форме

Вектор коэффициентов целевой функции двойственной задачиВектор коэффициентов целевой функции двойственной задачи, Вектор коэффициентов целевой функции двойственной задачи
Вектор коэффициентов целевой функции двойственной задачи

является задача ЛП в основной форме

Вектор коэффициентов целевой функции двойственной задачиВектор коэффициентов целевой функции двойственной задачиВектор коэффициентов целевой функции двойственной задачи

2) Двойственной к задаче ЛП в основной форме

Вектор коэффициентов целевой функции двойственной задачиВектор коэффициентов целевой функции двойственной задачиВектор коэффициентов целевой функции двойственной задачи

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

Вектор коэффициентов целевой функции двойственной задачиВектор коэффициентов целевой функции двойственной задачиВектор коэффициентов целевой функции двойственной задачи
Вектор коэффициентов целевой функции двойственной задачи

3) Двойственной к задаче ЛП в стандантной форме

Вектор коэффициентов целевой функции двойственной задачиВектор коэффициентов целевой функции двойственной задачиВектор коэффициентов целевой функции двойственной задачи
Вектор коэффициентов целевой функции двойственной задачи

является задача ЛП также в стандартной форме

Вектор коэффициентов целевой функции двойственной задачиВектор коэффициентов целевой функции двойственной задачиВектор коэффициентов целевой функции двойственной задачи
Вектор коэффициентов целевой функции двойственной задачи

Все эти три пары взаимно двойственных задач получаются из пары двойственных задач в общем виде (1) и (2) при различных значениях n1 и m1. Первая пара задач получается из (1) и (2) при m1=0, n1=n. Вторая пара задач получается из задач (1) и (2) при m1=m, n1=0. Третья пара задач получается из (1) и (2) при m1=m, n1=n.

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

1) Двойственной к задаче ЛП в канонической форме

Вектор коэффициентов целевой функции двойственной задачи

является задача ЛП в основной форме

Вектор коэффициентов целевой функции двойственной задачи.

2) Двойственной к задаче ЛП в основной форме

Вектор коэффициентов целевой функции двойственной задачи

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

Вектор коэффициентов целевой функции двойственной задачи.

3) Двойственной к задаче ЛП в стандантной форме

Вектор коэффициентов целевой функции двойственной задачи.

является задача ЛП также в стандартной форме

Вектор коэффициентов целевой функции двойственной задачи.

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

Видео:Двойственная задача линейного программирования (ЗЛП)Скачать

Двойственная задача линейного программирования (ЗЛП)

4.Условие дополняющей нежесткости

Равенства (15) и (16) называются условиями дополняющей нежесткости. Рассмотрим уравнение (16). Левая часть уравнения является скалярным произведением неотрицательных векторов Вектор коэффициентов целевой функции двойственной задачии Вектор коэффициентов целевой функции двойственной задачи, а это означает, что если один из координат одного из этих векторов больше нуля, то соответствующая координата другого вектора равна нулю (поскольку их скалярное произведение равно нулю). Получается, что если в системе линейных неравенств (4b) некоторое неравенство в точке Вектор коэффициентов целевой функции двойственной задачине удовлетворяется как равенство, то соответствующая координата вектора Вектор коэффициентов целевой функции двойственной задачиравна нулю и обратно − если некоторая координата вектора Вектор коэффициентов целевой функции двойственной задачибольше нуля, то соответствующее неравенство в системе (4b) в точке Вектор коэффициентов целевой функции двойственной задачиудовлетворяется как равенство.

Аналогичные рассуждения можно привести и для равенства (15). Условие дополняющей нежесткости позволяет найти оптимальный план двойственной задачи, если известен оптимальный план исходной задачи. Рассмотрим это на примере пар двойственных задач ЛП записанных в стандартной форме.

Пример 1. Дана следующая задача ЛП:

Вектор коэффициентов целевой функции двойственной задачи(26a)
Вектор коэффициентов целевой функции двойственной задачи(26b)
Вектор коэффициентов целевой функции двойственной задачи(26c)
Вектор коэффициентов целевой функции двойственной задачи(26d)

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

Запишем задачу ЛП в матричном виде:

Вектор коэффициентов целевой функции двойственной задачи
Вектор коэффициентов целевой функции двойственной задачи, Вектор коэффициентов целевой функции двойственной задачи, Вектор коэффициентов целевой функции двойственной задачи, Вектор коэффициентов целевой функции двойственной задачи.

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

Вектор коэффициентов целевой функции двойственной задачи

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

Вектор коэффициентов целевой функции двойственной задачи(27)

Решая систему линейных уравнений (27) получим координаты точки M, т.е. оптимальный план задачи ЛП (26):

Вектор коэффициентов целевой функции двойственной задачи(28)

или в векторном виде:

Вектор коэффициентов целевой функции двойственной задачи(29)

Целевая функция в этой точке равна:

Вектор коэффициентов целевой функции двойственной задачи

Построим двойственную к (26) задачу ЛП:

Вектор коэффициентов целевой функции двойственной задачи(30a)
Вектор коэффициентов целевой функции двойственной задачи(30b)
Вектор коэффициентов целевой функции двойственной задачи(30c)
Вектор коэффициентов целевой функции двойственной задачи(30d)

В векторно матричном виде задача ЛП (30) будет выглядеть так:

Вектор коэффициентов целевой функции двойственной задачи
Вектор коэффициентов целевой функции двойственной задачиВектор коэффициентов целевой функции двойственной задачи
Вектор коэффициентов целевой функции двойственной задачи

Условие дополняющей нежесткости (15) и (16) в случае задач ЛП в стандартной форме примут вид:

Вектор коэффициентов целевой функции двойственной задачи,(31)
Вектор коэффициентов целевой функции двойственной задачи.(32)

Условие (32) позволяет найти оптимальный план двойственной задачи ЛП (30). Поскольку все координаты оптимального плана Вектор коэффициентов целевой функции двойственной задачиисходной задачи положительны, то из равенства (32) следует, что неравенства (30b) и (30c) в оптимальной точке Вектор коэффициентов целевой функции двойственной задачидолжны выполняться как равенства, т.е. надо решить систему линейных уравнений

Вектор коэффициентов целевой функции двойственной задачи

Решив данное уравнение находим оптимальный план

Вектор коэффициентов целевой функции двойственной задачи.

Найдем значение целевой функции в данной точке:

Вектор коэффициентов целевой функции двойственной задачи.

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

Графический метод решения задачи ЛП (30) смотрите на Рис.2:

Вектор коэффициентов целевой функции двойственной задачи

Рассмотрим пример с той же допустимой областью, что и пример 1, но с другой целевой функцией.

Пример 2. Дана следующая задача ЛП:

Вектор коэффициентов целевой функции двойственной задачи(33a)
Вектор коэффициентов целевой функции двойственной задачи(33b)
Вектор коэффициентов целевой функции двойственной задачи(33c)
Вектор коэффициентов целевой функции двойственной задачи(33d)

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

Запишем задачу ЛП в матричном виде:

Вектор коэффициентов целевой функции двойственной задачи
Вектор коэффициентов целевой функции двойственной задачи, Вектор коэффициентов целевой функции двойственной задачи, Вектор коэффициентов целевой функции двойственной задачи, Вектор коэффициентов целевой функции двойственной задачи.

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

Вектор коэффициентов целевой функции двойственной задачи

Из Рис.3 видно, что оптимальным является точка

Вектор коэффициентов целевой функции двойственной задачи

Целевая функция в этой точке равна:

Вектор коэффициентов целевой функции двойственной задачи

Построим двойственную задачу:

Вектор коэффициентов целевой функции двойственной задачи(34a)
Вектор коэффициентов целевой функции двойственной задачи(34b)
Вектор коэффициентов целевой функции двойственной задачи(34c)
Вектор коэффициентов целевой функции двойственной задачи(34d)

В оптимальной точке Вектор коэффициентов целевой функции двойственной задачиограничение (33b) удовлетворяется как строгое неравенство следовательно исходя из условия дополняющей нежесткости (31), первая координата вектора Вектор коэффициентов целевой функции двойственной задачидолжна быть равна нулю: Вектор коэффициентов целевой функции двойственной задачи. Из равенства (32) следует, что неравенство (34b) в оптимальной точке Вектор коэффициентов целевой функции двойственной задачидолжно выполняться как равенство, поскольку соответствующая координата опттимального плана исходной задачи Вектор коэффициентов целевой функции двойственной задачибольше нуля. Таким образом имеем систему линейных уравнений:

Вектор коэффициентов целевой функции двойственной задачи
Вектор коэффициентов целевой функции двойственной задачи

Откуда получим Вектор коэффициентов целевой функции двойственной задачи.

В векторном виде оптимальный план двойственной задачи имеет вид:

Вектор коэффициентов целевой функции двойственной задачи.

Найдем значение целевой функции в данной точке:

Вектор коэффициентов целевой функции двойственной задачи.

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

Вектор коэффициентов целевой функции двойственной задачи

Графический метод решения задачи ЛП (34) представлен на Рис.4. Прямая, ортогональная к вектору целевой функции B перемещаем перпендикулярно к вектору целевой функции до соприкосновения к допустимой области задачи ЛП (желтая область). Полученная точка M является решением задачи ЛП.

Видео:Решение задачи линейного программирования при помощи надстройки Поиск решенияСкачать

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

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

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

Обычно с задачей линейного программирования (ЗЛП) связана другая линейная задача, называемая двойственной. Обе эти задачи можно считать двойственными одну по отношению к другой, считать равносильными. Первая задача называется обычно исходной, или прямой, другая — обратной. Переменные, используемые в двойственной задаче называются двойственными или множителями Лагранжа. На них не накладывается ограничений по знаку. Рассматриваются двойственные критерии оптимальности. Специальные случаи называют симметричными двойственными задачами линейного программирования. Связь между оптимальными решениями двойственных задач устанавливается теоремой двойственности.

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

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

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

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

Теорема существования решения

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

Теорема (принцип) дополняющей нежесткости

Если (xQ , xL) – оптимальное решение прямой задачи, а (yQ, yL) – решение двойственной задачи, то (xQ , xL, yQ , yL) – решение задачи Лагранжа. В частности, в этом случае удовлетворяются соотношения между переменными прямой и двойственной задач и условия дополняющей нежесткости.

Оптимальное решение прямой задачи программирования получается только при одном значении xQ. Это справедливо и для переменной yQ в двойственной задаче.

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

Основное неравенство двойственности. Для любых допустимых решений Х и Y пары двойственных ЗЛП имеет место неравенство

Вектор коэффициентов целевой функции двойственной задачи

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

Теорема существования (малая тероема двойственности)

Чтобы прямая и двойственная задачи имели opt решения, необходимо и достаточно, чтобы существовали допустимые решения для каждой из них.

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

Если одна из пары двойственных задач имеет opt решение, то и другая его имеет. Причем экспериментальные решения их целевых ф. равны; если же ЦФ одной из задач не ограничена, то система ограничений другой противоречива. Интерпретация: оптимальное использование ресурсов – opt план. Суммарная оценка ресурсов = оценке продукта полученного при opt плане. Любой другой план не рентабелен. Cj – стоимость единицы продукции (внешняя оценка) yi – стоимость единицы ресурса (внутренняя оценка). Эти двойственные оценки выступают как инструменты балансирования затрат и результатов. Имеет место xj ym +j ; xn+i yi.

Теорема 2 двойственности (о дополняющей нежесткости)

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

Вектор коэффициентов целевой функции двойственной задачи

То есть, если какое-либо ограничение одной ЗЛП обращается ее opt планом в строгое равенство, то соответствующая переменная двойственной задачи в ее opt плане равна нулю; если же какая-либо переменная opt-го решения одной ЗЛП положительна, то соответствующее ограничение в двойственной ЗЛП ее opt планом обращается в точное равенство.

Теорема Кёнига хорошо иллюстрирует использование принципа двойственности ЗЛП.

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

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

Вектор коэффициентов целевой функции двойственной задачи

Минимальное число линий, покрывающих все единицы матрицы [Cij], найдем, решив линейную задачу:

Вектор коэффициентов целевой функции двойственной задачи

Оптимальному решению (u*i, v*j) последней задачи отвечает минимальное покрытие, состоящее из множества строк I, для которых u*i = 1 и столбцов J, для которых u*j =1.

Матрицы А и А Т коэффициентов (*), (**), (***) являются абсолютно унимодулярными, как матрицы двудольного графа. Поэтому условия целочисленности переменных заменяем на условие их неотрицательности, и тогда получаем пару двойственных задач линейного программирования и согласно теореме двойственности имеем:

Вектор коэффициентов целевой функции двойственной задачи

Линией матрицы называется ее строка или столбец. Два элемента матрицы называются неколлинеарными, если они не лежат на одной линии.

Матрица называется абсолютно унимодулярной, если все ее ненулевые миноры равны 1, либо -1.

Следствие. Матрица инциденций неориентированного графа G абсолютно унимодулярна тогда и только тогда, когда G – двудольный граф. В двудольном графе все простые циклы имеют четкую длину

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

Предположим, что руководство предприятия из анализа конъюнктуры рынка продукции приняли решение: производство сократить, а от запасов сырья избавиться, (продать на рынке) и при этом не нанести себе убытков.

С этой целью руководство должно назначить стоимости yi за единицу сырья вида Si, стремясь при этом минимизировать общую стоимость сырья (чтобы быстрее продать сырье): Ф = Σ 4 i=1 biyi

Выручка предприятия от продажи сырья, расходуемого на единицу продукции Пi, составит: Σ 4 i=1 aij yi

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

Сформулируем исходную и двойственную задачи:

Вектор коэффициентов целевой функции двойственной задачи

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

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

Коэффициенты ЦФ первой задачи являются свободными членами системы ограничений второй.

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

Матрица коэффициентов второй задачи является транспонированной к матрице коэффициентов ограничений первой задачи.

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

Оптимальный план X opt одной из задач тесно связан с оптимальным планом Y opt другой. Если одна из задач имеет решение, то другая также разрешена, причем для оптимальных клонов X opt = и Y opt = справедливо равенство Q( X opt ) =Q’( Y opt ). Если линейная форма одной из задач неограниченна, то условия другой задачи несовместны. Если A -1 обратная матрица к матрице В, состоящей из векторов базиса оптимального плана исходной задачи, то оптимальный план двойственной задачи равен Y opt =СВ -1 , здесь С – вектор базисных переменных. Решение двойственной задачи получается в последней симплексной таблице исходной задачи, в (m+1) строке, в столбцах, соответствующих дополнительным параметрам.

Для того чтобы векторы X opt = и Y opt = были решениями пары задач, необходимо и достаточно, чтобы их компоненты удовлетворяли следующим условиям:

Вектор коэффициентов целевой функции двойственной задачи

Эти условия называют принципом дополняющей нежесткости. Если исходная (прямая) задача задана в канонической форме, то двойственная к ней называется несимметричной. Для несимметричной двойственной задачи соблюдается условие yi ≥ 0.

Теория ЗЛП доказывает, что компоненты оптимальных планов взаимно двойственных задач, приведенных к каноническому виду, соответствуют одни другим. То есть базисные переменные основной задачи соответствуют свободным переменным двойственной задачи и наоборот, j = 1(1)n, x*j ​ y*m +j ; x*n+i ​ y*i ; i = 1(1)m.

Вектор коэффициентов целевой функции двойственной задачи

Размерности в табличке m и n берутся в задаче для y-ков записанной в канонической форме.

Пример. Двойственный симплекс метод.

Исходная задача. Имеется три вида продуктов Пj, причем единица веса каждого из видов продуктов содержит aij единиц (питательных веществ). Для нормальной жизнедеятельности человек должен потреблять не менее bi единиц вещества Bi в сутки. Стоимость единицы продукта Пj равняется Cj. Требуется составить оптимальный суточный рацион питания, т.е. найти количество xj продукта, которое должен потреблять человек, чтобы стоимость питания была бы минимальной, если известно, что

Вектор коэффициентов целевой функции двойственной задачи

такие значения его компонентов xj, j = 1(1)3, которые минимизируют целевую функцию (Ц) Q = 3x1 + 2x2 + x3 и удовлетворяют ограничениям неравенствам

xj 0; j = 1(1)3 = n

Для приведения задачи к каноническому виду введем дополнительные переменные x4, x5, x6, x7, переменных стало больше чем уравнений n – m = 7 – 4 = 3, следовательно, части из них (трем любым,) для получения решения можно задать произвольные значения (задают, как правило, нулевые значения), возникает число сочетаний из n по m вариантов. Система ограничений примет вид равенств

xj 0; j = 1(1)3 = n, i = 1(1)4 = m.

Назначаем опорный план. Выбор в качестве базисных переменных x4, x5, x6, x7 приводит к недопустимому опорному плану. Так как знаки левой и правой частей различны. (Свободные переменные x1 = x2 = x3 = 0) Метод искусственного базиса приводит к увеличению числа неизвестных задач, что нежелательно. Анализ задачи показывает, что число уравнений в системе ограничений больше числа переменных. Поэтому попытаемся применить принцип двойственности, т.е. вначале решим двойственную ЗЛП, а затем найдем решение исходной.

Двойственная задача. Коэффициентами линейной формы в двойственной задаче выступают правые части bi , i = 1(1)4 = m, исходной основной задачи. Переменные получают другие имена y1, y2, y3, y4, и формулируется двойственная задача иначе. Найти максимум линейной формы Q’:

yi 0; i = 1(1)4.

Приведем задачу к каноническому виду, вводим дополнительные неотрицательные переменные y5 , y6 , y7 :

Найти минимум ЦФ (знаки у коэффициентов ЦФ поменяли на противоположные): Q’= — 0,2y1 — 0,5y2 — 0, 6y3 — 0,1y4;

при ограничениях (в ограничения добавили новые переменные):

yi 0; i = 1(1)7.

Задача решается симплекс методом. Исходный опорный план в качестве переменных может иметь y5, y6, y7 и свободные переменные y1 = y2 = y3 = y4 = 0, т.е. Y = [0, 0, 0, 0, 3, 2, 1] .

Вектор коэффициентов целевой функции двойственной задачи

Базисные переменные y5, y6, y7 и ЦФ выражаем через свободные переменные, т.е. из свободных членов (правых частей, обозначенных γi ) вычитаем левые части ограничений

γ0 =0, так как ЦФ не содержит свободного члена.

и строим симплекс таблицу с двумя полуклетками. Направляющий столбец y3, направляющая строка y6.

Вектор коэффициентов целевой функции двойственной задачи

Анализ таблицы показывает, что все коэффициенты ЦФ при свободных переменных положительны. Следовательно, план Y не является оптимальным, ЦФ можно уменьшить, увеличивая значения соответствующих свободных переменных.

Находим γ = max<γi> =max = 0,6. Переменную y3 надо ввести в базис. После этого устанавливаем, существует ли оптимальный план. В направляющем столбце все коэффициенты положительны, следовательно, оптимальный план существует. В базисе есть переменные, которые можно уменьшать до нуля увеличивая значения y3, тем самым минимизируя ЦФ. Раньше других в нуль обратиться переменная y6 и ее исключаем из базиса.

Вектор коэффициентов целевой функции двойственной задачи

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

Вектор коэффициентов целевой функции двойственной задачи

Анализ этой таблицы показывает, что все коэффициенты в выражении ЦФ свободных переменных отрицательны. Следовательно, опорный план Y = [0, 0, 20/3, 0, 5/3, 0, 1/3] является оптимальным. ЦФ при этом Q’1 = — 4 достигла наименьшего значения. Возвращаемся к двойственной задаче. Используя соответствие между оптимальными планами двойственных задач ЛП, определяем: базисными переменными в оптимальном плане будут x2 x4 x5 x7; их значения с противоположным знаком записаны в последней строке таблицы. Таким образом, X opt = , т.е. оптимальный рацион из двух единиц продукта П2. Стоимость такого рациона минимальна и составляет 4 единицы. Это значение с противоположным знаком записано в той же таблице.

Ваулин А. Е. Методы цифровой обработки данных.– СПб.: ВИККИ им. А. Ф. Можайского, 1993.– 106 с.

Гэри М., Джонсон Д. Вычислительные машины и трудно решаемые задачи. М.: Мир, 1982.

Квейд Э. Методы системного анализа // Новое в теории и практике управления производством в США.–М.: Прогресс, 1971.– с.78-99. .

Корбут А.А., Финкельштейн Ю. Ю. Дискретное программирование М. Наука. Гл. ред. физ.-мат. лит. 1969.

Макаров И. М. и др. Теория выбора и принятия решений.– М.: Наука, 1982.– 328 с.

Пфанцагль И. Теория измерений. – М.: Наука, 1988.–384 с.

Таха Х. А. Введение в исследование операций. 7-е изд. М.: Изд. дом «Вильямс», 2005.

Фишберн П. С. Теория полезности для принятия решений. – М.: Наука,1978. –352 с.

🔍 Видео

Векторные диаграммы и коэффициент мощностиСкачать

Векторные диаграммы и коэффициент мощности

Cимплексный метод решения задачи линейного программирования (ЗЛП)Скачать

Cимплексный метод решения задачи линейного программирования (ЗЛП)

Вектор. Сложение и вычитание. 9 класс | МатематикаСкачать

Вектор. Сложение и вычитание. 9 класс | Математика

Урок 2. Двойственная задача линейного программирования. Решение двойственной задачи в Excel.Скачать

Урок 2. Двойственная задача линейного программирования. Решение двойственной задачи в Excel.

СИМПЛЕКС МЕТОД: ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯСкачать

СИМПЛЕКС МЕТОД: ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

8. Двойственная задача. Two-way partitioning problem. Проекция на вероятностный симплекс. МФТИ 2023Скачать

8. Двойственная задача. Two-way partitioning problem. Проекция на вероятностный симплекс. МФТИ 2023

РК6. Методы математического программирования. Двойственность задач линейного программированияСкачать

РК6. Методы математического программирования. Двойственность задач линейного программирования

Симплексный метод (табличный оформление №1) решения задачи линейного программирования.Скачать

Симплексный метод (табличный оформление №1)  решения задачи линейного программирования.

Лекция 5 от 09.10.2021Скачать

Лекция 5 от 09.10.2021

SVM. Часть 8. Двойственная задачаСкачать

SVM. Часть 8.  Двойственная задача

АиСД S04E10. Линейное программированиеСкачать

АиСД S04E10. Линейное программирование

Урок 1.Поиск решения, оптимизация, оптимальный план производстваСкачать

Урок 1.Поиск решения, оптимизация, оптимальный план производства

#вектор Разложение вектора по ортам. Направляющие косинусыСкачать

#вектор Разложение вектора по ортам.  Направляющие косинусы
Поделиться или сохранить к себе: