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

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

Задача, состоящая в нахождении минимального значения функции. Задачи 32 — 34 и 35 — 37 образуют пару задач, называемую в линейном программировании двойственной парой. Сравнивая две сформулированные задачи, видим, что двойственная задача составляется согласно следующим правилам: Целевая функция исходной задачи 32 — 34 задается на максимум, а целевая функция двойственной 35 — 37 — на минимум. Число переменных в двойственной задаче 35 — 37 равно числу ограничений в системе 33 исходной задачи 32 — 34 , а число ограничений в системе 36 двойственной задачи — числу переменных в исходной задаче.

Коэффициентами при неизвестных в целевой функции 35 двойственной задачи 35 — 37 являются свободные члены в системе 33 исходной задачи 32 — 34 , а правыми частями в соотношениях системы 36 двойственной задачи — коэффициенты при неизвестных в целевой функции 32 исходной задачи. Если же переменная x j может принимать как положительные, так и отрицательные значения, то 1 — соотношение в системе 54 представляет собой уравнение. Аналогичные связи имеют место между ограничениями 33 исходной задачи 32 — 34 и переменными двойственной задачи 35 — Если i — соотношение в системе 33 исходной задачи является неравенством, то i —я переменная двойственной задачи.

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

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

Составить двойственную задачу по отношению к задаче, состоящей в максимизации функции. Число переменных в двойственной задаче равно числу уравнений в системе 41 , т. Коэффициентами в целевой функции двойственной задачи являются свободные члены системы уравнений 41 , то есть числа 12, 24, Целевая функция исходной задачи 40 — 42 исследуется на максимум, а система условий 41 содержит только уравнения.

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

Поэтому в двойственной задаче целевая функция исследуется на минимум, а ее переменные могут принимать любые значения в том числе и отрицательные. Следовательно, для задачи 40 — 42 двойственная задача такова: Для задачи, состоящей в максимизации функции. В соответствии с общими правилами задача, двойственная по отношению к данной, формулируется следующим образом: Рассмотрим пару двойственных задач, образованную основной задачей линейного программирования и двойственной к ней. Каждая из задач двойственной пары 43 — 45 и 46 , 47 фактически является самостоятельной задачей линейного программирования и может быть решена независимо одна от другой.

Однако при определении симплексным методом оптимального плана одной из задач тем самым находится решение и другой задачи. Существующие зависимости между решениями прямой и двойственной задач характеризуются сформулированными ниже леммами и теоремами двойственности. Если Х — некоторый план исходной задачи 43 — 45 , a Y — произвольный план двойственной задачи 46 , 47 , то значение целевой функции исходной задачи при плане Х всегда не превосходит значения целевой функции двойственной задачи при плане Y, т.

Теорема 8 первая теорема двойственности. Если одна из задач двойственной пары 43 — 45 или 46 , 47 имеет оптимальный план, то и другая имеет оптимальный план и значения целевых функций задач при их оптимальных планах равны между собой, т. Если же целевая функция одной задачи из двойственной пары неограничена для исходной 43 — 45 — сверху, для двойственной 46 , 47 — снизу , то другая задача вообще не имеет планов. Теорема 9 вторая теорема двойственности. План задачи 43 — 45 и план задачи 46 , 47 являются оптимальными планами этих задач тогда и только тогда, когда для любого выполняется равенство.

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

Как в исходной, так и в двойственной задаче число неизвестных равно двум. Следовательно, их решение можно найти, используя геометрическую интерпретацию задачи линейного программирования рис. Минимальное значение целевая функция двойственной задачи принимает в точке Е рис. Таким образом, при любом плане исходной задачи значение целевой функции не превосходит значения целевой функции двойственной задачи при ее произвольном плане. Как исходная, так и двойственная задача содержат по две переменные.

Поэтому их решение находим, используя геометрическую интерпретацию задачи линейного программирования рис. Это означает, что если исходная задача двойственной пары не имеет оптимального плана из-за неограниченности на множестве допустимых решений ее целевой функции, то двойственная задача также не имеет планов. Нахождение решения двойственных задач. Рассмотрим пару двойственных задач — основную задачу линейного программирования 43 — 45 и двойственную к ней задачу 46 , Обозначим через вектор-строку, составленную из коэффициентов при неизвестных в целевой функции 43 задачи 43 — 45 , а через — матрицу, обратную матрице Р , составленной из компонент векторов базиса.

Тогда имеет место следующее утверждение. Таким образом, если найти симплексным методом оптимальный план задачи 43 — 45 , то, используя последнюю симплекс—таблицу , можно определить и и с помощью соотношения найти оптимальный план двойственной задачи 46 , В том случае, когда среди векторов , составленных из коэффициентов при неизвестных в системе уравнений 44 , имеется т единичных, указанную матрицу образуют числа первых т строк последней симплекс—таблицы, стоящие в столбцах данных векторов.

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

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

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

Для производства трех видов изделий А , В и С используется три различных вида сырья. Каждый из видов сырья может быть использован в количестве, соответственно не большем , и кг. Нормы затрат каждого из видов сырья на единицу продукции данного вида и цена единицы продукции каждого вида приведены в таблице Определить план выпуска продукции, при котором обеспечивается ее максимальная стоимость, и оценить каждый из видов сырья, используемых для производства продукции.

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

Нормы затрат сырья кг на единицу продукции. Предположим, что производится x 1 изделий А , изделий В и изделий С. Для определения оптимального плана производства нужно решить задачу, состоящую в максимизации целевой функции. Припишем каждому из видов сырья, используемых для производства продукции, двойственную оценку, соответственно равную и у 3.

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

Как видно, задачи 48 — 50 и 51 — 53 образуют симметричную пару двойственных задач. Решение прямой задачи дает оптимальный план производства изделий A , В и С , а решение двойственной — оптимальную систему оценок сырья, используемого для производства этих изделий.

Чтобы найти решение этих задач, следует сначала отыскать решение какой—либо одной из них. Ее решение приведено в таблице Из этой таблицы видно, что оптимальным планом производства изделий является такой, при котором изготовляется 82 изделия В и 16 изделий С. При данном плане производства остается неиспользованным 80 кг сырья II вида, а общая стоимость изделий равна руб.

Из таблицы 14 также видно, что оптимальным решением двойственной задачи является. Переменные и обозначают условные двойственные оценки единицы сырья, соответственно I и III видов. Эти оценки отличны от нуля, а сырье 1 и III видов полностью используется при оптимальном плане производства продукции. Двойственная оценка единицы сырья II вида равна нулю.

Этот вид сырья не полностью используется при оптимальном плане производства продукции. Таким образом, положительную двойственную оценку имеют лишь те виды сырья, которые полностью используются при оптимальном плане производства изделий. Поэтому двойственные оценки определяют дефицитность используемого предприятием сырья. Более того, величина данной двойственной оценки показывает, на сколько возрастает максимальное значение целевой функции прямой задачи при увеличении количества сырья соответствующего вида на 1 кг.

Так, увеличение количества сырья I вида на 1 кг приведет к тому, что появится возможность найти новый оптимальный план производства изделий, при котором общая стоимость изготовляемой продукции возрастет на 5,75 руб. Точно так же увеличение на 1 кг сырья III вида позволит найти новый оптимальный план производства изделий, при котором общая стоимость изготовляемой продукции возрастет на 1,25 руб.

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

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

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

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

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

К рассмотрению этого мы сейчас и перейдем. В ысшая математика Решение контрольных Оплата контрольных Вопросы по Skype Редактор формул Лекции Видео-лекции Учебники on-line Скачать учебники Решатели задач О математике Карта сайта. Вид сырья Нормы затрат сырья кг на единицу продукции А В С I II III 4 3 1 2 1 2 1 3 5 Цена единицы продукции руб.

МЕНЮ В ысшая математика Решение контрольных Оплата контрольных Вопросы по Skype Редактор формул Лекции Видео-лекции Учебники on-line Скачать учебники Решатели задач О математике Карта сайта.

Опубликовано в рубрике Realtek pcie gbe
Twitter Delicious Facebook Digg Stumbleupon Favorites More
  • Прикрепленное видео

Все права защищены. © 2001 toozza.ru