|
|||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Этап решения моделиЗадача сформулирована, теперь встает вопрос о нахождении оптимального допустимого решения, доставляющего максимум целевой функции. Можно сделать вывод, что задача имеет много (фактически, бесконечно много) допустимых решений. По этой причине невозможна подстановка значений переменных для поиска оптимума, т.е. нельзя применить простой перебор всех допустимых решений. Следовательно, необходима эффективная процедура отбора допустимых решений для поиска оптимального. Существуют два наиболее распространенных способа решения задач линейного программирования (ЗЛП): графический метод и симплекс-метод. Графический метод существенно нагляднее и обычно проще для понимания и решения (хотя занимает много времени, так как требует тщательного построения чертежа). Замечание. Графический̆ метод применим в случае двух переменных. Практических приложений у этого метода немного, но он важен для наглядности и понимания происходящего. Сначала необходимо построить пространство решений, то есть получить область, точки которой удовлетворяют всем ограничениям. Каждое ограничение задает полуплоскость ограниченную некоторой̆ прямой, пересечение этих полуплоскостей̆ есть пространство решений. Далее, необходимо максимизировать z = 5x1+4x2. Рассмотрим семейство соответствующих прямых.
Направление возрастания функции z = 5х1+4х2 есть перпендикуляр к прямым соответствующего семейства. В следствии чего, мы можем увеличивать значение целевой функции, пока соответствующая ей прямая имеет хотя бы одну общую точку с пространством решений. ..\Book1.xls В нашем случае оптимальное решение соответствует точке пересечения прямых x1 + 2х2 ≤ 6 и x1 + 2х2 ≤ 6, то есть в точке С(3; 1,5), а значение целевой функции 21. Значит лучшим решением будет выпускать 3т и 1,5т, получая при этом прибыль в 21 тис. ден. ед. Замечание (Об угловой точке) Очевидно, что если область задана произвольным многоугольником, а максимизируемая функция имеет общий̆ вид z = ax + by, то решение (оптимум) все равно будет достигаться в угловой̆ точке. Если мы изменим угол наклона, то есть коэффициенты целевой функции, то увидим, что решение достигается в любом случае в одной из угловых точек (или в нескольких). Решение задачи линейного программирования графическим методом включает следующие этапы: 1. На плоскости X10X2 строят прямые. 2. Определяются полуплоскости. 3. Определяют многоугольник решений; 4. Строят вектор N(c1; c2), который указывает направление целевой функции; 5. Передвигают прямую целевую функцию c1x2 + c2x2 = z в направлении вектора N до крайней точки многоугольника решений. 6. Вычисляют координаты точки и значение целевой функции в этой точке. Приведем основные свойства задачи ЛП.
Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.) |