С помощью данного онлайн-калькулятора можно получить:
- решение двойственной задачи линейного программирования через решений прямой задачи (симплексным методом, по теореме двойственности);
- оптимальный план двойственной задачи; оценки ресурсов (двойственные оценки);
- определение дефицитных и недефицитных (избыточных) ресурсов;
- изменение целевой функции при изменении параметров; обоснование эффективности оптимального плана;
- анализ устойчивости двойственных оценок (предельное изменение b i , c i); анализ субоптимальных вариантов плана.
Инструкция . Выберите количество переменных и количество ограничений прямой задачи линейного программирования, нажмите Далее. Полученное решение сохраняется в файле Word и Excel . При этом ограничения типа x i ≥ 0 не учитывайте. Если прямая задача ЛП не имеет решение, но требуется составить двойственную задачу или одна из переменных x i неопределена, то можно использовать этот калькулятор .
Основная идея теории двойственности : для каждой задачи линейного программирования (ЛП) существует некоторая задача ЛП, решение которой тесно связано с прямой. При этом:
- матрица ограничений двойственной задачи (ДЗ) есть транспонированная матрица прямой задачи;
- вектор "цен" для прямой задачи есть вектор правых частей ограничений задачи ДЗ и наоборот.
| Прямая | Двойственная |
| Целевая функция (max) | Правая часть ограничений |
| Правая часть ограничений | Целевая функция (min) |
| A - матрица ограничений | A T - матрица ограничений |
| i -ое ограничение: ≤ 0, (≥ 0) | Переменная y i ≥ 0, (≤ 0) |
| i -ое ограничение: = 0 | Переменная y i ≠ 0 |
| Переменная x j ≥ 0 (≤ 0) | j -ое ограничение: ≤ 0 (≥ 0) |
| Переменная x j ≠ 0 | j -ое ограничение: = 0 |
Пример
. Определим максимальное значение целевой функции F(X) = 3x 1 +5x 2 +4x 3 при следующих условиях-ограничений.
0.1x 1 + 0.2x 2 + 0.4x 3 ≤1100
0.05x 1 + 0.02x 2 + 0.02x 3 ≤120
3x 1 + x 2 + 2x 3 ≤8000
Решим прямую задачу симплексным методом.
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных.
0.1x 1 + 0.2x 2 + 0.4x 3 + 1x 4 + 0x 5 + 0x 6 = 1100
0.05x 1 + 0.02x 2 + 0.02x 3 + 0x 4 + 1x 5 + 0x 6 = 120
3x 1 + 1x 2 + 2x 3 + 0x 4 + 0x 5 + 1x 6 = 8000
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x 4 , x 5 , x 6
Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,1100,120,8000)
Поскольку задача решается на максимум, то ведущий столбец выбирают по максимальному отрицательному числу и индексной строке. Все преобразования проводят до тех пор, пока не получатся в индексной строке положительные элементы.
Переходим к основному алгоритму симплекс-метода.
| План | Базис | В | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | min |
| 1 | x 4 | 1100 | 0.1 | 0.2 | 0.4 | 1 | 0 | 0 | 5500 |
| x 5 | 120 | 0.05 | 0.02 | 0.02 | 0 | 1 | 0 | 6000 | |
| x 6 | 8000 | 3 | 1 | 2 | 0 | 0 | 1 | 8000 | |
| Индексная строка | F(X1) | 0 | -3 | -5 | -4 | 0 | 0 | 0 | 0 |
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x 2 , так как наибольший коэффициент по модулю.
Следовательно, 1-ая строка является ведущей. Разрешающий элемент равен 0.2 и находится на пересечении ведущего столбца и ведущей строки. Формируем следующую часть симплексной таблицы. Вместо переменной x в план 1 войдет переменная x 2 . Строка, соответствующая переменной x 2 в плане 1, получена в результате деления всех элементов строки x 4 плана 0 на разрешающий элемент РЭ=0.2. На месте разрешающего элемента в плане 1 получаем 1. >В остальных клетках столбца x 2 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x 2 и столбец x 2 .
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника .
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (0.2), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
| План | Базис | В | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | min |
| 2 | x 2 | 5500 | 0.5 | 1 | 2 | 5 | 0 | 0 | 11000 |
| x 5 | 10 | 0.04 | 0 | -0.02 | -0.1 | 1 | 0 | 250 | |
| x 6 | 2500 | 2.5 | 0 | 0 | -5 | 0 | 1 | 1000 | |
| Индексная строка | F(X2) | 27500 | -0.5 | 0 | 6 | 25 | 0 | 0 | 0 |
Итерация №1
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ведущего выберем столбец, соответствующий переменной x 1 , так как наибольший коэффициент по модулю.
Вычислим значения D i по строкам как частное от деления и из них выберем наименьшее:
Следовательно, 2-ая строка является ведущей. Разрешающий элемент равен 0.04 и находится на пересечении ведущего столбца и ведущей строки. Формируем следующую часть симплексной таблицы. Вместо переменной x в план 2 войдет переменная x 1 . Строка, соответствующая переменной x 1 в плане 2, получена в результате деления всех элементов строки x 5 плана 1 на разрешающий элемент РЭ=0.04. На месте разрешающего элемента в плане 2 получаем 1. В остальных клетках столбца x 1 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x 1 и столбец x 1 .
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
Пример №2 . Для выполнения задания необходимо, чтобы одновременно взлетели 50 АК I-го вида, 30 АК 2-го вида и 45 АК 3-го вида. АК расположены на аэродромах I и II. В таблице представлено среднее время взлета (в секундах) с соответствующего аэродрома одного АК данного типа.
| Номер аэродрома | Тип АК | ||
| 1 | 2 | 3 | |
| I | 4 | 10 | 10 |
| II | 6 | 8 | 20 |
Решение. Обозначим через:
x 11 - АК 1-го типа на первом аэродроме,
x 12 - АК 1-го типа на втором аэродроме,
x 21 - АК 2-го типа на первом аэродроме,
x 22 - АК 2-го типа на втором аэродроме,
x 31 - АК 3-го типа на первом аэродроме,
x 32 - АК 3-го типа на втором аэродроме,
Ограничения
4x 11 + 6x 12 = 50
10x 21 + 8x 22 = 30
10x 31 + 20x 32 = 45
x 11 , x 12 , x 21 , x 22 , x 31 ,x 32 ≥ 0
x 11 , x 12 , x 21 , x 22 , x 31 ,x 32 -целые числа
Целевая функция
4x 11 + 6x 12 + 10x 21 + 8x 22 +10x 31 + 20x 32 → min
После найденного решения, ответом на первый вопрос будут значения переменных x 11 , x 12 , x 21 , x 22 , x 31 ,x 32 . Информация об ответе на второй вопрос будет расположена в разделе Интервалы устойчивости коэффициентов целевой функции.
Двойственные задачи линейного программирования.
Каждой задаче линейного программирования соответствует двойственная задача.
Алгоритм составления двойственной задачи.
Пример 1.
Составить двойственную задачу
1. Приводим все неравенства системы ограничений исходной задачи к одному смыслу
2. Составляем расширенную матрицу
3. Транспонируем матрицу
4. Формулируем двойственную задачу
|
Исходная (прямая) задача |
Двойственная задача |
|
|
|
Задачу линейного программирования можно рассматривать как модель распределения ограниченных ресурсов, в которой целевая функция, отображающая прибыль или доход от производственной деятельности, подлежит максимизации. Если рассматривать задачу линейного программирования с этой точки зрения, соответствующая ей двойственная задача получает интересную экономическую интерпретацию.
переменная у i двойственной задачи представляет стоимость единицы ресурса i . В литературе по исследованию операций переменные у i двойственной задачи часто называют двойственными ценами . Кроме того, иногда их именуют теневыми ценами и симплексными мультипликаторами .
Аналогично для любой пары допустимых решений прямой и двойственной задач неравенство f < z можно интерпретировать следующим образом:
Доход < Общая стоимость ресурсов
Это соотношение показывает, что до тех пор, пока суммарный доход от всех видов деятельности строго меньше суммарной стоимости всех используемых ресурсов, решение как прямой, так и двойственной задачи не может быть оптимальным. Оптимум (максимальный доход) может быть достигнут только тогда, когда все потребляемые ресурсы использованы полностью.
Большой практический интерес представляет экономическая интерпретация второй теоремы двойственности, а также ее следствия о дополняющей нежесткости.
1. Если суммарная оценка i-го ресурса положительна
то этот ресурс в соответствии с оптимальным планом х* используется полностью
2. Если i-й ресурс используется не полностью
то его оптимальная оценка нулевая и i-е ограничение несущественно.
3. Если в соответствии с оптимальным планом х* j-я продукция производится
то это производство эффективно, так как цена единицы j-й продукции
равна затратам на ее производство в единицах
4. Если производство j-й продукции убыточно (приведенные издержки ненулевые
то в соответствии с оптимальным планом эта продукция не производится
Таким образом, двойственные оценки связаны с оптимальным планом прямой задачи. Всякое изменение исходных данных прямой задачи оказывает влияние на ее оптимальный план и систему двойственных оценок. В свою очередь двойственные оценки служат инструментом анализа и принятия правильных решений в условиях меняющихся коммерческих ситуаций.
Метод, при котором вначале симплекс-методом решается одна из взаимно двойственных задач, а затем оптимум и оптимальное решение другой задачи находятся с помощью теорем двойственности, называется двойственным симплекс-методом .
Теорема 1 (Первая теорема двойственности) . Если одна из взаимно двойственных задач имеет оптимальное решение, то его имеет и
другая, причем оптимальные значения их целевых функций равны:
Если целевая функция исходной задачи не ограничена, то система ограничений двойственной задачи несовместна.
Примечание: утверждение, обратное по отношению ко второй части первой теоремы двойственности, в общем случае неверно.
Теорема 2 . Компоненты оптимального плана двойственной задачи (обладающие условием неотрицательности ) равны абсолютным значениям коэффициентов
Компоненты оптимального плана двойственной задачи (не ограниченные по знаку ) равны значениям коэффициентов при соответствующих переменных целевой функции исходной задачи, выраженной через свободные переменные ее оптимального решения.
Теорема 3 . Положительным (ненулевым) компонентам оптимального решения одной из задач симметричной двойственной пары соответствуют нулевые компоненты оптимального решения другой задачи, т.е. для любых и :
Теорема 4 (Третья теорема двойственности)
. Компоненты оптимального плана двойственной задачи равны значениям частных производных линейной функции 
по соответствующим аргументам, т.е.
. (7.2)
Экономическая интерпретация третьей теоремы двойственности : компоненты оптимального плана двойственной задачи показывают, на сколько денежных единиц изменится максимальная прибыль (выручка) от реализации продукции при изменении запаса соответствующего ресурса на одну единицу.
Пример 9.1. На основе решения примера 5.2 (файл «Алгоритм и примеры симплекс-метода») определим двойственным симплекс- методом оптимальное решение двойственной задачи.
Исходная задача | Двойственная задача |
|
Данная двойственная пара является симметричной. Задачи записаны в стандартной форме, приведем их к каноническому виду:
Исходная задача | Двойственная задача |
|
|
Установим соответствие между переменными взаимно двойственных задач.
На основе решения примера 5.2. симплекс-таблица последней итерации (таблица 5.10) имеет вид:
Таблица 9.3
В соответствии с теоремой 2, оптимальные значения переменных и будут равны абсолютным значениям коэффициентов при соответствующих переменных целевой функции исходной задачи, выраженной через свободные переменные ее оптимального решения.
По таблице 9.3 выпишем целевую функцию исходной задачи, выраженную через свободные переменные ее оптимального решения:
Следовательно, , .
Переменные , , и не присутствуют в целевой функции (т.е. коэффициенты при них равны нулю), следовательно, оптимальные значения соответствующих им переменных , , и равны нулю.
В соответствии с теоремой 1, 
.
Таким образом, оптимальное значение целевой функции , которое достигается при .
Пример 9.2. На основе решения исходной задачи найти оптимальное решение двойственной задачи используя двойственный симплекс-метод.
|
Исходная задача | Двойственная задача |
|
|
Данная двойственная пара является несимметричной. Приведем к каноническому виду двойственную задачу.
|
Исходная задача | Двойственная задача |
|
|
Для установления соответствия переменных двойственной пары введем в исходную задачу две недостающие фиктивные переменные.
|
Исходная задача | Двойственная задача |
|
|
Установим соответствие между переменными взаимно двойственных задач.
Таблица 9.4
Соответствие переменных двойственной пары
Решим исходную задачу симплекс-методом.
Используя метод Жордана-Гаусса, выделим в системе ограничений исходной задачи в качестве базисных переменные и (примечание: не использовать в качестве базисных фиктивные переменные).
В результате преобразований получим следующую матрицу коэффициентов:
.
Система ограничений исходной задачи примет следующий вид:
Выразим базисные переменные через свободные, в результате исходная задача примет следующий вид:
Подставив полученные значения базисных переменных в целевую функцию, она примет следующий вид:
В результате решения симплекс-методом преобразованной исходной задачи на последней итерации получим следующую симплекс-таблицу:
Таблица 9.5
Симплекс-таблица оптимального решения исходной задачи
Каждой задаче ЛП соответствует другая задача, называемая двойственной по отношению к исходной.
2.9.1 Экономическая интерпретация
Ранее была сформулирована задача о планировании производства. Рассмотрим теперь вопрос о покупке ресурсов. Пусть некоторая организация решила закупить ресурсы и необходимо установить оптимальные цены на эти ресурсы. Очевидно, что покупающая организация заинтересована в том, чтобы затраты на все ресурсы в количествах были минимальны, то есть .
С другой стороны, предприятие, продающее ресурсы, заинтересовано в том, чтобы выручка была не менее той суммы, которую предприятие может получить при переработке ресурсов в готовую продукцию . На изготовление единицы продукции вида расходуется единиц ресурса по цене , единиц ресурса по цене , единиц ресурса по цене , единиц ресурса по цене . Поэтому для удовлетворения требований продавца затраты на ресурсы, потребляемые при изготовлении единицы продукции , должны быть не менее её цены , то есть
Соотношение прямой и двойственной задач ЛП показано в таблице:
Прямая задача
Двойственная задача
.
.
Найти такой план 
выпуска продукции, при котором прибыль (выручка) от реализации продукции будет максимальна при условии, что потребление ресурсов по каждому виду продукции не превзойдёт имеющихся запасов.
Найти такой набор цен 
на ресурсы, при котором общие затраты на ресурсы будут минимальны при условии, что затраты на ресурсы при производстве каждого вида продукции будут не менее прибыли (выручки) от реализации этой продукции.
Цены ресурсов в экономической литературе получили различные названия: учётные , неявные , теневые . Смысл этих названий состоит в том, что это условные, «ненастоящие» цены. В отличие от «внешних» цен на продукцию, известных, как правило, до начала производства, цены ресурсов являются внутренними, ибо задаются не извне, а определяются непосредственно в результате решения задачи.
2.9.2 Двойственные задачи и их свойства
Рассмотрим двойственные задачи в общей форме.
Прямая задача:
.
Двойственная задача:
Двойственная задача по отношению к прямой составляется следующим образом:
1. Целевая функция исходной задачи задаётся на максимум, а в двойственной – на минимум.
2. Матрицы коэффициентов прямой и двойственной задач получаются друг из друга заменой строк столбцами, а столбцов – строками (операция транспонирования):
.
3. Число переменных в двойственной задаче равно числу ограничений в исходной задаче (и наоборот).
4. Коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в ограничениях исходной задачи, а правыми частями в ограничениях двойственной задачи являются коэффициенты при неизвестных в целевой функции исходной задачи.
Задача 7. Составить задачу, двойственную следующей задаче:
Поскольку прямая задача на максимум, то приведём все неравенства системы ограничений к виду «£» (обе части первого и четвёртого неравенства умножим на –1):
Составим расширенную матрицу системы:
.
Транспонированная матрица:
.
Сформулируем двойственную задачу:
2.9.3 Теоремы двойственности
Сначала сформулируем основное неравенство теории двойственности .
Пусть имеется пара двойственных задач. Для любых допустимых решений 
и 
прямой и двойственной задач справедливо неравенство
или в координатном виде
.
Теперь сформулируем достаточный признак оптимальности .
Если и – допустимые решения соответственно прямой и двойственной задач, для которых справедливо равенство
,
то – оптимальное решение прямой задачи, а – двойственной задачи.
Связь между оптимальными решениями двойственных задач устанавливается с помощью теорем двойственности.
Первая теорема двойственности. Если одна из взаимно двойственных задач имеет оптимальное решение , то его имеет и другая , причём оптимальные значения их целевых функций равны :
Или .
Если целевая функция одной из задач не достигает оптимума , то условия другой задачи противоречивы .
Экономический смысл первой теоремы двойственности состоит в следующем.
План производства и набор цен ресурсов оптимальны тогда и только тогда, когда прибыль (выручка) от продукции, найденная при «внешних» (известных заранее) ценах , равна затратам на ресурсы по «внутренним» (определяемым только из решения задачи) ценам .
Связь между двойственными задачами проявляется не только в равенстве оптимальных значений их целевых функций (первая теорема двойственности).
Пусть даны двойственные задачи.
Прямая:
.
Двойственная:
.
Если каждую из этих задач решать симплекс-методом, то необходимо привести их к каноническому виду, для чего в систему ограничений
прямой задачи следует ввести неотрицательных переменных , а в систему ограничений
двойственной задачи следует ввести неотрицательных переменных , где – номер неравенства, в которое введена дополнительная переменная . Системы ограничений каждой из задач примут соответственно вид:
прямая задача –
,
двойственная задача –
.
Соответствие между переменными двойственных задач иллюстрирует таблица:
Переменные прямой задачи
Первоначальные
Дополнительные
Дополнительные
Первоначальные
Переменные двойственной задачи
Теорема 16. Положительным (ненулевым ) компонентам оптимального решения одной из взаимно двойственных задач соответствуют нулевые компоненты оптимального решения другой задачи , то есть для любых и: если, то; если, то; и аналогично , если, то; если, то.
Вторая теорема двойственности. Чтобы допустимые решения , пары двойственных задач были оптимальными, необходимо и достаточно, чтобы выполнялись условия:
Следствие . Если в оптимальном решении одной из двойственных задач какая-либо переменная не равна нулю, то соответствующее ей ограничение двойственной задачи на оптимальном решении выполняется как равенство, и наоборот, если на оптимальном решении одной из двойственных задач какое-либо ограничение выполняется как строгое неравенство, то соответствующая ему переменная в оптимальном решении двойственной задачи равна нулю.
Если в одной из взаимно двойственных задач нарушается единственность оптимального решения (геометрически это означает, что оно достигается на ребре/грани многоугольника/многогранника), то оптимальное решение двойственной задачи вырожденное.
Задача 8. Решив симплексным методом задачу
получим: 
, .
Перейдём к неравенствам типа “”:
.
Двойственная задача:
Соответствие между переменными (см. табл. выше):
.
На оптимальном решении прямой задачи имеем:
Так как третье и четвёртое ограничения выполняются как строгие неравенства, то, согласно следствию, 
, , причём оба ограничения двойственной задачи выполняются как равенства:
Подставляя сюда и решая систему, оптимальное решение двойственной задачи 
.
2.9.4 Объективно обусловленные оценки
Компоненты оптимального решения двойственной задачи называются оптимальными (двойственными ) оценками прямой задачи. Канторович назвал их объективно обусловленными оценками .
Превышение затрат на ресурсы
над ценой реализации
Объективно обусловленные оценки ресурсов
(условные цены ресурсов)
Компоненты оптимального решения двойственной задачи
В таблице значения дополнительных переменных прямой задачи представляют разность между запасами ресурсов и их потреблением, то есть выражают остатки ресурсов , а значения дополнительных переменных двойственной задачи представляют разность между затратами на ресурсы для производства из них единицы продукции и ценами продукции , то есть выражают превышение затрат над ценой .
Ресурсы по оптимальному плану полностью использованы (
), и объективно обусловленные оценки этих ресурсов ненулевые (, и в этом случае по оптимальному плану производить продукцию не следовало.
Таким образом, в оптимальный план производства могут попасть только рентабельные, неубыточные виды продукции (правда, критерий рентабельности здесь своеобразный: цена продукции не превышает затраты на потребляемые при её изготовлении ресурсы, а в точности равна им).
Контрольные вопросы
1. Сформулировать понятие о взаимно-двойственной задаче.
2. Дать экономическую интерпретацию пары взаимно-двойственных задач.
3. Сформулировать свойства пары взаимно-двойственных задач.
4. Сформулировать первую теорему двойственности и ее экономическое содержание.
5. Сформулировать вторую теорему двойственности и ее экономическое содержание.
5. Дать определение понятию объективно-обусловленные оценки.
Постановка задачи
Каждой задаче линейного программирования можно поставить в соответствие другую задачу линейного программирования, называемую двойственной или сопряженной по отношению к исходной или прямой:
Прямая:
F(x)=c 1 x 1 + c 2 x 2 +…+ c n x n →max
a 11 x 1 + a 12 x 1 +…+ a 1n x n ≤b 1 ,
a 21 x 1 + a 22 x 1 +…+ a 2n x n ≤b 2 ,
………………………………
a k1 x 1 + a k2 x 1 +…+ a kn x n ≤b k ,
a k+1,1 x 1 + a k+1,2 x 1 +…+ a k+1,n x n =b k+1 ,
………………………………
a m1 x 1 + a m2 x 1 +…+ a mn x n= b m ,
Двойственная:
F*(Y)=b 1 y 1 + b 2 y 2 +…+ b m y m →min
a 11 y 1 + a 21 y 2 +…+ a m1 y m ≥c 1 ,
a 12 y 1 + a 22 y 2 +…+ a m2 y m ≥c 2 ,
………………………………
a 1l y 1 + a 2l y 1 +…+ a ml y m ≤c l ,
a 1,l+1 y 1 + a 2,l+1 y 2 +…+ a m,l+1 y m =c l+1 ,
………………………………
a 1n y 1 + a 2n y 1 +…+ a mn y m= c m ,
Двойственная задача по отношению к исходной составляется согласно правилам:
1. Целевая функция исходной задачи задается на максимум, а двойственной на минимум.
2. Матрица из коэффициентов при неизвестных исходной задачи и аналогичная матрица двойственной задачи получаются друг из друга транспонированием.
3. Число переменных в двойственной задаче равно числу соотношений в системе ограничений исходной задачи, а число ограничений двойственной задачи - числу переменных в исходной задаче.
4. Коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе исходной задачи, а правыми частями в системе ограничений двойственной задачи - коэффициенты при неизвестных в целевой функции исходной задачи.
5. Если переменная хj исходной задачи может принимать только лишь положительные значения, то j- e условие в системе ограничений двойственной задачи является неравенством вида "≥ ". Если же переменная хj может принимать и отрицательные значения, то j -e соотношение в двойственной задаче будет равенством. Если i -e соотношение в исходной задаче является неравенством, то і- я переменная двойственной задачи yi≥0. В противном случае yi может принимать как положительные, так и отрицательные значения.
Двойственные пары задач подразделяются на симметричные и несимметричные. В симметричной паре двойственных задач ограничения прямой и двойственной задач могут принимать лишь неотрицательные значения.
Связь между решениями прямой и двойственной задач.
Если основная задача линейного программирования имеет оптимальный план Х*, то Y*= C δ . является оптимальным планом двойственной задачи. Здесь C δ - вектор-строка коэффициентов целевой функции при базисных переменных оптимальной симплекс-таблицы прямой задачи, а - матрица обратная матрице, составленной из компонентов векторов, входящих в последний базис, при котором получен оптимальный план. Если прямая задача приведена к единичному базису при неотрицательных свободных членах уравнений, вычисление обратной матрицы не требуется, так как будет состоять из столбцов оптимальной симлекс-таблицы, полученных на месте единичных столбцов исходной таблицы.
Пример 1.
Задана прямая задача:
х 1 , х 2 ≥0
Составить двойственную задачу.
Решение:
Прежде всего третье ограничение умножим на "-1", так как оно имеет знак «≥». Это ограничение примет вид
-5х 1 +3х 2 -6х 3 ≤-19
Матрица из коэффициентов при неизвестных в ограничениях будет:
Запишем транспонированную к ней матрицу:
Тогда двойственная задача запишется:
у 1 , у 3 ≥0
Так как в прямой задаче второе ограничение имеет знак "=", то переменная y 2 не имеет ограничения на знак. Третье ограничение двойственной задачи имеет знак "=" так как переменная х 3 не имеет ограничения на знак.
Пример 2.
Прямая задача
х 1 , х 4 ≥0
Двойственная задача
| Баз. вект | С баз | А 0 | ||||||
| А 1 | А 2 | А 3 | А 4 | А 5 | ||||
| А 3 | -1 | |||||||
| ← | А 5 | -1 | ||||||
| ∆ | -1 | -5 | -3 | |||||
| Баз. вект | С баз | А 0 | ||||||
| А 1 | А 2 | А 3 | А 4 | А 5 | ||||
| ← | А 3 | 14/3 | 10/3 | 8/3 | 1/3 | |||
| А 2 | 5/3 | 1/3 | -1/3 | 1/3 | ||||
| ∆ | 34/3 | 5/3 | -14/3 | 5/3 | ||||
| Баз. вект | С баз | А 0 | |||||
| А 1 | А 2 | А 3 | А 4 | А 5 | |||
| А 4 | 7/4 | 5/4 | 3/8 | 1/8 | |||
| А 2 | 9/4 | 3/4 | 1/8 | 3/8 | |||
| ∆ | 78/4 | 15/2 | 7/4 | 9/4 |
Из последней таблицы получим оптимальный план:
Х опт =(0, 9/4, 0, 7/4);
Данные этой же таблицы используются для определения оптимального решения двойственной задачи.
Вектор С опт =(С 4 , С 2)=(6,4) . Матрица Ах состоит из векторов А 4 А 2 , взятых из ограничений по которым составляется двойственная задача:
А х =(А 4 А 2)=
Обратная матрица будет:
Тогда: 
F min
= 
Примечание: Так как исходная задача приведена к единичному базису при неотрицательных свободных членах уравнений, то обратная матрица Ах -1 состоит из компонентов векторов А 3 и А 5 последней симплекс- таблицы.
3. Варианты заданий
К данной задаче составить сопряженную, решить одну из них и по найденному решению получить решение второй.
| 1) | F=x 1 +x 2 →max
| 2) | F=3x 1 +x 2 →min | |
| 3) | F=3x 1 +3x 2 →min | 4) | F=6x 1 -5x 2 →max | |
| 5) | F=8x 1 +2x 2 →max | 6) | F=x 1 +2x 2 →max | |
| 7) | F=14x 1 +10x 2 +14x 3 +14x 4 →max
| 8) | F=2x 1 +3x 2 →min | |