![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Решение двойственных задач
Теория двойственности находит широкое практическое применение. Сформулированные теоремы двойственности позволяют получить решение одной задачи, процесс решения которой по той или иной причине затруднителен, по оптимальному решению двойственной к ней. К такой причине относится значительное превышение числа ограничений над числом переменных задачи, так как объем вычислений при решении задач линейного программирования симплекс-методом определяется, в основном, числом ограничений. Также при необходимости решения задачи с ограничениями вида «> =» можно перейти к решению двойственной, которая будет иметь ограничения вида «< =», что позволяет избежать ввода искусственных переменных. Рассмотрим процесс получения решения двойственной задачи на основании оптимального решения исходной. Подставим в ограничения исходной задачи значения переменных x1* = 2, x2* = 4 в оптимальном плане:
4*2 + 8*4 < = 40 4*2 + 2*4< = 20
На основании второй основной теоремы двойственности переменная двойственной задачи y2, соответствующая второму ограничению исходной, которое обратилось при подстановки оптимального плана в строгое неравенство, равна нулю (y2* = 0). Поскольку переменные x1, x2 в оптимальном плане имеют положительные значения, то соответствующие им ограничения двойственной задачи при подстановке в них ее оптимального плана обращаются в равенство. Учитывая, что y2* = 0, получим
6y1 + 8y3 = 15.
Решив полученную систему двух линейных уравнений с двумя переменными, найдем оптимальный план двойственной задачи: y1* = 3/2, y2* = 0, y3* = ¾. Согласно первой основной теореме двойственности fmax = zmin = 84.
Контрольные вопросы и упражнения 1. Какая задача называется двойственной? 2. Сформулируйте правило построения двойственной задачи. 3. В чем отличие симметричных задач двойственной пары от несимметричных? 4. Как по решению исходной задачи можно найти решение двойственной? 5. Постройте задачи, двойственные к данным:
а) f = x1 – 2x2 + 3x3 – xi → max;
x1 + 2x2 – x3 + x4 ≤ 3, __ xj ≥ 0 (j = 1, 4);
б) f = 3x2 – x4 → max;
x1 - 2x2 + x4 = 8, x2 + x3 – 3x4 = 6, __ xj ≥ 0 (j = 1, 4);
в) f = 5x1 + x2 → max;
x1 – 3x2 ≤ 3,
x1 ≥ 0, x2 ≤ 0;
г) f = x1 – 2x2 → min;
x1 – x2 ≥ 5, -x1 + x2 ≥ 1,
x1 ≥ 0, x2 ≥ 0.
|