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

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

  • автор:

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

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

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

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

Понравилось? Добавьте в закладки

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

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

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

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

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

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

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

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

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

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

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

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

Пусть мы имеем симметричную пару двойственных задач (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

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

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

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

Симметричная двойственная задача

Рассмотрим задачу линейного программирования с неотрицательными переменными и неравенствами системы ограничений следующего вида:
(1.1) ;
(1.2)
Здесь , , есть некоторые числа. Все строки системы (1.2) являются неравенствами со знаками .

Двойственная задача имеет вид:
(2.1) ;
(2.2)
Здесь все строки системы (2.2) являются неравенствами со знаками . Матрица коэффициентов системы ограничений (2.2) является транспонированной матрицей системы (1.2). Она содержит строк и столбцов. Двойственная задача имеет переменных . Все переменные неотрицательные.

Исходную задачу (1) часто называют прямой задачей, а задачу (2) – двойственной. Если за исходную взять задачу (2), то задача (2) будет прямой задачей, а задача (1) – двойственной. Задачи (1) и (2) называются симметричными двойственными задачами.

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

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

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

Составить двойственную задачу.

Исходная задача является задачей на нахождение минимума. Поэтому все неравенства должны иметь знаки . Первое и третье неравенства содержат знак . Умножим их на –1 :

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

Матрица коэффициентов системы ограничений имеет вид:

Транспонируем эту матрицу. То есть первую строку запишем как первый столбец, вторую строку запишем как второй столбец, третью строку запишем как третий столбец.

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

Несимметричная двойственная задача

Задача на максимум

Рассмотрим каноническую задачу линейного программирования на максимум с неотрицательными переменными и равенствами системы ограничений:
(3.1) ;
(3.2)
Здесь , , есть некоторые числа. Все строки системы (3.2) являются равенствами. Все переменные являются неотрицательными.

Двойственная задача имеет вид:
(4.1) ;
(4.2)
Здесь все строки системы (4.2) являются неравенствами со знаками . Матрица коэффициентов системы ограничений (4.2) является транспонированной матрицей системы (3.2). Двойственная задача имеет переменных . Переменные могут быть как положительными, так и отрицательными.

Отличие несимметричной пары задач (3) и (4) от симметричной пары (1) и (2) в том, что система ограничений (3.2) содержит только равенства, а в системе (4.2) отсутствуют условия неотрицательности переменных.

Задача на минимум

Теперь рассмотрим каноническую задачу линейного программирования на минимум:
(5.1) ;
(5.2)

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

Система ограничений (6.2) отличается от (4.2) тем, что неравенства имеют знаки .

Связь с симметричной парой двойственных задач

Покажем, что несимметричную пару задач (3)-(4) можно получить из симметричной пары (1)-(2).

\left\< \begin</p> <p>Итак, пусть мы имеем прямую задачу с целевой функцией <br /><b>(3.1)</b> <br />и системой ограничений <br /><b>(3.2)</b> <br />Каждое равенство можно представить двумя неравенствами: </p> <p>Неравенства со знаками умножим на –1 : <br /> a_ x_1 + a_ x_2 + \, . \, + a_ x_n \leqslant b_1 \\ -a_ x_1 — a_ x_2 — \, . \, — a_ x_n \leqslant -b_1 \\ a_ x_1 + a_ x_2 + \, . \, + a_ x_n \leqslant b_2 \\ -a_ x_1 — a_ x_2 — \, . \, — a_ x_n \leqslant -b_2 \\ . \\ a_ x_1 + a_ x_2 + \, . \, + a_ x_n \leqslant b_m \\ -a_ x_1 — a_ x_2 — \, . \, — a_ x_n \leqslant -b_m \\ x_1 \geqslant 0; \; x_2 \geqslant 0; \; . \; ; x_n \geqslant 0 \end \right.» width=»342″ height=»186″ /> <br />Система ограничений имеет неравенств.</p> <p><img decoding=

Если мы за исходную задачу возьмем (4), то, выполняя все действия в обратном порядке, получим двойственную задачу (3).

Тем же способом можно из задачи (5) получить двойственную задачу (6) и из задачи (6) получить двойственную задачу (5).

Смешанная задача

Теперь рассмотрим смешанную задачу.

Пусть мы имеем прямую задачу (1) на максимум, в системе ограничений которой -я строка является равенством. Тогда двойственная задача имеет вид (2) за одним исключением – переменная может быть как положительной, так и отрицательной. То есть отсутствует ограничение .

То же самое произойдет, если мы имеем прямую задачу (2) на минимум, в системе ограничений которой -я строка является равенством. Двойственная задача имеет вид (1) за одним исключением – переменная может быть любого знака.

Теперь пусть мы имеем прямую задачу (1) на максимум, но отсутствует ограничение . То есть переменная может быть как положительной, так и отрицательной. Тогда двойственная задача имеет вид (2) за одним исключением – -я строка системы ограничений является равенством.

И наконец, пусть мы имеем прямую задачу (2) на минимум, но отсутствует ограничение . Тогда двойственная задача имеет вид (1) за одним исключением – -я строка системы ограничений является равенством.

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

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

1. Для исходной задачи на максимум, все неравенства системы ограничений приводим к виду:
.
Для исходной задачи на минимум, все неравенства приводим к виду:
.
Если требуется поменять знак, то умножаем обе части неравенств на –1 .
2. Составляем двойственную задачу тем же способом, как для симметричной пары задач.
3. Если в исходной задаче, –я строка системы ограничений является равенством, то вычеркиваем условие неотрицательности –й переменной двойственной задачи.
4. Если в исходной задаче, отсутствует условие неотрицательности для –й переменной, , то в –й строке двойственной задачи меняем знак неравенства на знак равенства.

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

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

Составить двойственную задачу.

Целевая функция имеет свободный член 5. Чтобы привести ее к виду (2.1), введем переменную и добавим равенство . Тогда задача примет вид:

Эта задача является задачей на нахождение минимума. Поэтому все неравенства должны иметь знаки . Третье неравенства содержат знак . Поэтому умножим его на –1 :

\left\< \begin</p> <p>Перепишем систему ограничений, явно указывая коэффициенты при переменных: <br /> 1 \cdot x_1 + 2 \cdot x_2 — 3 \cdot x_3 + 0 \cdot x_4 = 4 \\ 4 \cdot x_1 — 1 \cdot x_2 + 0 \cdot x_3 + 0 \cdot x_4 = 7 \\ — 2 \cdot x_1 + 3 \cdot x_2 — 1 \cdot x_3 + 0 \cdot x_4 \geqslant — 5 \\ 0 \cdot x_1 + 0 \cdot x_2 + 0 \cdot x_3 + 1 \cdot x_4 = 1 \\ x_1 \geqslant 0; \; x_2 \geqslant 0 \end \right.» width=»333″ height=»115″ /> <br />Матрица коэффициентов системы ограничений имеет вид: </p> <p>Транспонируем эту матрицу. То есть первую строку запишем как первый столбец, вторую строку запишем как второй столбец, и так далее. </p><div class='code-block code-block-10' style='margin: 8px 0; clear: both;'> <!-- 10seostattya --> <script src=

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

Поскольку в исходной задаче 1, 2 и 4-я строка системы ограничений являются равенствами, то в двойственной задаче переменные , и могут иметь любой знак. Неотрицательной переменной является только . Поэтому условия неотрицательности переменных имеют вид:
.

Поскольку в исходной задаче переменные и могут иметь произвольные знаки, то 3-я и 4-я строки системы ограничений двойственной задачи являются равенствами.

Таким образом, двойственная задача имеет вид:
;

Из четвертого уравнения . Заменим переменную ее значением и умножим третью строку на –1 .

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

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

Прочие статьи цикла

  1. Исследование операций
  2. Метод ветвей и границ. Задача коммивояжера
  3. Симплексный метод решения задач линейного программирования
  4. Симплексный метод решения ЗЛП. Пример
  5. Двойственная задача линейного программирования
  6. Транспортная задача линейного программирования
  7. Задача выбора (назначения). Венгерский метод решения
  8. Управление запасами

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

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

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

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

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

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

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

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

  1. Если (xQ , xL) – оптимальное решение прямой задачи, а (yQ, yL) – решение двойственной задачи, то (xQ , xL, yQ , yL) – решение задачи Лагранжа. В частности, в этом случае удовлетворяются соотношения между переменными прямой и двойственной задач и условия дополняющей нежесткости.
  2. Оптимальное решение прямой задачи программирования получается только при одном значении 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 (в противном случае предприятию выгоднее не продавать сырье, а использовать его для нужд производства, выпуска продукции).

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

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

  1. Если первая задача сформулирована на поиск максимума, то вторая формулируется на поиск минимума линейной функции.
  2. Коэффициенты ЦФ первой задачи являются свободными членами системы ограничений второй.
  3. Свободные члены системы ограничений первой задачи являются коэффициентами линейной системы во второй задаче.
  4. Матрица коэффициентов второй задачи является транспонированной к матрице коэффициентов ограничений первой задачи.
  5. Знаки неравенств в ограничениях второй задачи противоположны знакам неравенств в ограничениях первой задачи.

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

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

Эти условия называют принципом дополняющей нежесткости. Если исходная (прямая) задача задана в канонической форме, то двойственная к ней называется несимметричной. Для несимметричной двойственной задачи соблюдается условие 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 не является оптимальным, ЦФ можно уменьшить, увеличивая значения соответствующих свободных переменных.

Находим γ = maxi> =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 единицы. Это значение с противоположным знаком записано в той же таблице.

  1. Ваулин А. Е. Методы цифровой обработки данных.– СПб.: ВИККИ им. А. Ф. Можайского, 1993.– 106 с.
  2. Гэри М., Джонсон Д. Вычислительные машины и трудно решаемые задачи. М.: Мир, 1982.
  3. Квейд Э. Методы системного анализа // Новое в теории и практике управления производством в США.–М.: Прогресс, 1971.– с.78-99. .
  4. Корбут А.А., Финкельштейн Ю. Ю. Дискретное программирование М. Наука. Гл. ред. физ.-мат. лит. 1969.
  5. Макаров И. М. и др. Теория выбора и принятия решений.– М.: Наука, 1982.– 328 с.
  6. Пфанцагль И. Теория измерений. – М.: Наука, 1988.–384 с.
  7. Таха Х. А. Введение в исследование операций. 7-е изд. М.: Изд. дом «Вильямс», 2005.
  8. Фишберн П. С. Теория полезности для принятия решений. – М.: Наука,1978. –352 с.
  • Информационная безопасность
  • Криптография
  • Алгоритмы
  • Математика
  • Научно-популярное
Похожие публикации:
  1. Internal graphics что это в биосе
  2. Webex как включить звук
  3. Как выйти в дос при загрузке
  4. Как отключить strict trans tables в phpmyadmin

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *