|
||||||||||||||||||||||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Построение двойственной задачи и ее решение графическим методомПусть 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):
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 руб. Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.006 сек.) |