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

Построение двойственной задачи и ее решение графическим методом

Читайте также:
  1. I. ГИМНАСТИКА, ЕЕ ЗАДАЧИ И МЕТОДИЧЕСКИЕ ОСОБЕННОСТИ
  2. I. ЗАДАЧИ ПЕДАГОГИЧЕСКОЙ ПРАКТИКИ
  3. I. Решение логических задач средствами алгебры логики
  4. I. Ситуационные задачи и тестовые задания.
  5. II. Основные задачи и функции
  6. II. Решение логических задач табличным способом
  7. II. ЦЕЛИ, ЗАДАЧИ И ПРИНЦИПЫ ДЕЯТЕЛЬНОСТИ ВОИ
  8. II. Цель и задачи государственной политики в области развития инновационной системы
  9. III. Разрешение споров в международных организациях.
  10. III. Решение логических задач с помощью рассуждений
  11. III. Цели и задачи социально-экономического развития Республики Карелия на среднесрочную перспективу (2012-2017 годы)
  12. MFG/PRO – лучшее решение для крупных и средних промышленных предприятий с дискретным типом производства

Пусть u1 – двойственная оценка ограничения по сырью, а u2 – двойственная оценка ограничения по труду.

u1 ↔ 8х1 + 9х2 + 13х3 585,

u2 ↔ 17х1 + 15х2 + 9х3 703,

Тогда двойственная задача к прямой (исходной) задаче будет иметь вид:

W = 585u1 + 703u2 min

x1 ↔ 8u1 + 17u2 670 (1)

x2 ↔ 9u1 + 15u2 504 (2)

x3 ↔ 13u1 + 9u2 530 (3)

u1 0, u2 0

Решим эту задачу графическим методом. Для этого построим граничные прямые полуплоскостей, задаваемых ее ограничениями (1) – (3):

1) 8u1+17u2 = 670
u1   83,75
u2 39,4  

 
2) 9u1 + 15u2 = 504
u1    
u2 33,6  

 
3) 13u1 + 9u2 = 530
u1   40,76
u2 58,8  

 

  

u2

 

 

 

А

58,8

 


39,4

В

33,6

 

 


7,03

С

5,85 40,76 56 83,75 u1

(3) (1)

(2)

Рис. 1. Графическое решение двойственной задачи

 

Ни одно из неравенств (1) – (3) не содержит начала координат – точки (0, 0). Поэтому область допустимых решений (ОДР) лежит справа от ломаной линии, образованной граничными прямыми (1), (2), (3) и осями координат. Опа представляет собой бесконечный многоугольник с вершинами A, B и C.

Чтобы градиент целевой функции можно было представить на графике, уменьшим его компоненты в 100 раз, т.е. построим вектор = (5,85; 7,03). Проведем перпендикулярно градиенту линию нулевого уровня целевой функции, проходящую через начало координат. Затем переместим ее параллельно самой себе в направлении возрастания градиента .

Так как решается задача на минимум, то первая точка, в которой перемещаемая линия уровня коснется ОДР, будет точкой оптимума. Этой точкой, как видно из чертежа, является точка В. Она находится на пересечении 1-й и 3-й граничной прямой. Поэтому для нахождения ее координат нужно решить следующую систему уравнений

8u1+17u2 = 670

13u1+9u2 = 530

Решив эту систему, получим оптимальное решение двойственной задачи:

u = 20, u = 30, W* = 585×20 + 70×30 = 32790.

Это решение задает оптимальные двойственные оценки ресурсов для фирмы, т.е. стоимостная оценка 1 кг сырья составит 20 руб., а 1 чел.-час. трудовых ресурсов – 30 руб. Общая стоимостная оценка затрат на ресурсы составит 32790 руб.

3. Нахождение оптимального плана выпуска продукции

Для определения оптимального решения исходной задачи х* = (х , х , х ). используем условия «дополняющей нежесткости»:

х (8u +17u – 670) = 0,

х (9u +15u – 504) = 0,

х (13u +9u – 530) = 0,

u (585 – 8х – 9х – 13х ) = 0,

u (703 – 17х – 15х – 9х ) = 0.

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

8u + 17u = 670

9u + 15u = 630 > 504

13u + 9u = 530

Таким образом, второе ограничение в точке оптимума является строгим неравенством (630 > 504). Поэтому из второго соотношения дополняющей нежесткости следует, что х (630 – 504) = 0 и значит х = 0.

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

.

Так как , то для нахождения оптимальных значений оставшихся переменных прямой задачи достаточно решить систему уравнений:

Ее решение: х1 = 26, х3 = 29 и следовательно, оптимальное решение прямой задачи таково: х* = (26; 0; 29), а Z* = 670×26 + 530×29 = 32790.

Так как оптимальные значения целевых функций обеих задач равны (Z* = W*), это означает, что обе задачи решены правильно.

Таким образом, в оптимальный план вошли первый и третий вид продукции. Должно быть выпущено 26 изделий первого вида и 29 изделий третьего вида. Суммарный доход от их продажи составит 32790 руб.


1 | 2 | 3 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.199 сек.)