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

Решение и анализ задач ЛП графическим методом

Читайте также:
  1. I Цели и задачи изучения дисциплины
  2. I. Характеристика проблемы, на решение которой направлена подпрограмма
  3. I. Характеристика проблемы, на решение которой направлена Программа
  4. I. Характеристика проблемы, на решение которой направлена Программа
  5. I.9.1.Хемилюминесцентный метод анализа активных форм кислорода
  6. II Разрешение космологической идеи о целокупности деления данного целого в созерцании
  7. II этап – анализ финансовой устойчивости организации.

Графический метод применяется для решения задач линейного программирования с двумя переменными. Он основан на геометрическом представлении допустимых решений и целевой функции задачи.

(4.1)

Отметим, что, если в задаче линейного программирования имеется более двух переменных x1, x2,…,xn,но (n-2) ограничений имеют вид равенства, а остальные вид неравенства, то и такая задача может быть сведена к двум переменным за счет исключения переменных с помощью системы равенств. Следовательно, графический метод может быть применен и к таким задачам.

Для геометрической интерпретации решения задачи задается координатная плоскость Оx1,x2, на которой каждая точка с координатами (x1,x2) представляет решение (допустимое или недопустимое) задачи с такими значениями переменных.

Каждое из неравенств задачи (4.1) моделируется на координатной плоскости Оx1,x2 некоторой полуплоскостью (рис. 4.1), а система неравенств в целом – общей частью соответствующих полуплоскостей, то есть пересечением их как множеств точек. Множество точек пересечения данных множеств (полуплоскостей) образует область допустимых решений. ОДР является выпуклой областью, т.е. если две точки А и В принадлежат этой ОДР, то и все точки отрезка АВ принадлежат ей. В зависимости от сочетания и видов ограничений ОДР графически может выглядеть выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучом, единственной точкой. Если ограничения задачи (4.1) несовместны, то ОДР - пустое множество.

Функция при заданном значении z(x)=z0 моделируется на плоскости прямой линией, задаваемой уравнением . В каждой точке плоскости, принадлежащей данной прямой целевая функция имеет одно и то же значение равное z0. При различных значениях правой части равенства, получаются параллельные прямые. соответствующие различным значениям правой части (уровням целевой функции) и называемые линиями уровня (Рис. 4.1).

 

 

Рис. 4.1. Геометрические интерпретации ограничений и ЦФ

Вектор C =(c1,c2), координатами которого являются коэффициенты функции , называется градиентом функции z(x). Градиент указывает направление наискорейшего возрастания функции и перпендикулярен к каждой из линий уровня (Рис. 4.1). Направление наискорейшего убывания ЦФ противоположно направлению вектораC.

Суть графического метода заключается в том, что в ОДР производится поиск оптимальной точки xопт=(x1опт, x2опт). Оптимальной считается точка, через которую проходит линия уровня, соответствующая наибольшему (наименьшему) значению уровня ЦФ. Оптимальное решение всегда находится на границе ОДР, например, в вершине многоугольника ОДР, оказавшейся последней через которую пройдет линия уровня, при её параллельном перемещении, моделирующем возрастание уровня ЦФ (Рис.4.1). При этом значение уровня будет равно zmax. Если сторона многоугольника ОДР, на которой расположена точка соответствующая оптимальному решению, параллельна линиям уровня, то оптимальное решение может находиться в любой точке этой стороны многоугольника ОДР.

При решении задачи ЛП возможны следующие множества решений.

Таблица 4.1.1


Дата добавления: 2015-07-15; просмотров: 123 | Нарушение авторских прав


Читайте в этой же книге: Введение | Математическое моделирование как методологии научных исследований | Классификация математических моделей | Терминология | Процесс исследования операций | Моделирование на основе системного подхода | Терминология | Этапы системного анализа-синтеза | Классификация систем и инструментов аналитической деятельности | Пример решения |
<== предыдущая страница | следующая страница ==>
Терминология| Укрупненный алгоритм решения графическим методом

mybiblioteka.su - 2015-2024 год. (0.005 сек.)