Пример графического метода решения задачи линейного программирования. Поиск оптимального решения графического метода lpm
жүктеу/скачать 74,92 Kb.
|
Пример графического метода решения задачи линейного программирования
|
Пример графического метода решения задачи линейного программирования. 1.Поиск оптимального решения графического метода LPM. Поскольку модель, обсуждаемая в теме 1, содержит только две переменные, проблема может быть решена графически. В случае трех переменных графическое решение становится менее визуальным, а при большем количестве омелы оно становится невозможным вообще. Несмотря на это, рассмотрение графического метода позволит сделать выводы, которые послужат основой для разработки общего метода решения задач ЛП. Первым шагом при использовании графического метода является представление области приемлемых решений, в которой одновременно удовлетворяются все ограничения модели. Желаемая площадь (пространство) решений задачи примера 1.1. показано на рисунке 2. 2.1. Условия неотчуждаемости переменных ограничивают площадь их допустимых значений первым квадрантом координатной плоскости (часть плоскости над осью х1 и справа от оси х2). Другие границы пространства решений изображаются прямыми линиями, построенными на уравнениях, полученных путем замены знака «£» знаком «=» в ограничениях. Области, в которых соответствующие ограничения выполняются как неравенства (в нашем случае неравенства со знаком «<»), обозначаются стрелками, направленными в сторону допустимых значений переменных. Результирующим пространством для решения задачи красок является многоугольник ABCDЕF (рис. 2.1). В каждой точке, относящейся к внутренней области или границам полигона решения ABCDEF, выполняются все ограничения, поэтому решения, соответствующие этим точкам, допустимы. Среди бесконечного числа таких точек можно найти точку оптимального решения, если выяснить, в каком направлении растет целевая функция. Рис. 2.1. Пространство допустимых решений задачи «о красках». На рисунке 2. 2.2 Показывает, как выполняется такая операция. На рисунке 2. 2.2 Показывает, как выполняется такая операция. Рис. 2.2. Поиск оптимального решения THELP графическим методом. График применяется к линии уровня целевой функции c1×x1+c2×x2=z0, где z0 — произвольное значение z. Построить вектор N (c1, c2), который является нормальным для линий уровня целевой функции и определяет направление оптимизации z. Последняя точка в этой области будет оптимальной точкой. Очевидно, что оптимальное решение соответствует точке С-точки пересечения линий (1) и (2). Значения x1 и x2 в точке C определяются решением системы уравнений: Решение этой системы x1=3 ; x2 = 1 . Полученная в этом случае прибыль составит: z=3x1+2x2 =3×3 +2×1 =12 (тыс. г.о.) Заметим, что в случае, когда линии уровня z имеют тот же наклон, что и линия ограничения привязки (то есть проходящие через оптимальную точку), у нас будет много оптимумов на отрезке. жүктеу/скачать 74,92 Kb. Достарыңызбен бөлісу:
|