Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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




 

Теория двойственности находит широкое практическое применение. Сформулированные теоремы двойственности позволяют получить решение одной задачи, процесс решения которой по той или иной причине затруднителен, по оптимальному решению двойственной к ней. К такой причине относится значительное превышение числа ограничений над числом переменных задачи, так как объем вычислений при решении задач линейного программирования симплекс-методом определяется, в основном, числом ограничений. Также при необходимости решения задачи с ограничениями вида «>=» можно перейти к решению двойственной, которая будет иметь ограничения вида «<=», что позволяет избежать ввода искусственных переменных .

Рассмотрим процесс получения решения двойственной задачи на основании оптимального решения исходной. Подставим в ограничения исходной задачи значения переменных x1* = 2, x2* = 4 в оптимальном плане:

 

6*2 +6*4 <= 36

4*2 + 8*4 <= 40

4*2 + 2*4<= 20

 

На основании второй основной теоремы двойственности переменная двойственной задачи y2, соответствующая второму ограничению исходной, которое обратилось при подстановки оптимального плана в строгое неравенство, равна нулю (y2* = 0).

Поскольку переменные x1, x2 в оптимальном плане имеют положительные значения, то соответствующие им ограничения двойственной задачи при подстановке в них ее оптимального плана обращаются в равенство. Учитывая, что y2* = 0, получим

6y1 + 4y3 = 12,

6y1 + 8y3 = 15.

 

Решив полученную систему двух линейных уравнений с двумя переменными, найдем оптимальный план двойственной задачи: y1* = 3/2, y2* = 0, y3* = ¾. Согласно первой основной теореме двойственности fmax = zmin = 84.

 

Контрольные вопросы и упражнения

1. Какая задача называется двойственной?

2. Сформулируйте правило построения двойственной задачи.

3. В чем отличие симметричных задач двойственной пары от несимметричных?

4. Как по решению исходной задачи можно найти решение двойственной?

5. Постройте задачи, двойственные к данным:

 

а) f = x1 – 2x2 + 3x3 – xi → max;

 

2x1 – x2 + 2x3 – 3x4 ≤ 5,

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 – x2 ≤ 2,

x1 – 3x2 ≤ 3,

 

x1 ≥ 0, x2 ≤ 0;

 

г) f = x1 – 2x2 → min;

 
 


x1 – x2 ≥ 5,

-x1 + x2 ≥ 1,

 

x1 ≥ 0, x2 ≥ 0.



 


.

mylektsii.ru - Мои Лекции - 2015-2019 год. (0.005 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал