Если неравенство истинное,
то надо заштриховать полуплоскость, содержащую данную точку;
иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку.
Поскольку и должны быть неотрицательными, то их допустимые значения всегда будут находиться выше оси и правее оси , т.е. в I-м квадранте.
Ограничения-равенства разрешают только те точки, которые лежат на соответствующей прямой. Поэтому необходимо выделить на графике такие прямые.
III. Определить ОДР как часть плоскости, принадлежащую одновременно всем разрешенным областям, и выделить ее. При отсутствии ОДР задача не имеет решений.
IV. Если ОДР – не пустое множество, то нужно построить целевую прямую, т.е. любую из линий уровня (где L – произвольное число, например, кратное и , т.е. удобное для проведения расчетов). Способ построения аналогичен построению прямых ограничений.
V. Построить вектор , который начинается в точке (0;0) и заканчивается в точке . Если целевая прямая и вектор построены верно, то они будут перпендикулярны.
VI. При поиске максимума ЦФ необходимо передвигать целевую прямую в направлении вектора , при поиске минимума ЦФ – против направления вектора . Последняя по ходу движения вершина ОДР будет точкой максимума или минимума ЦФ. Если такой точки (точек) не существует, то можно сделать вывод о неограниченности ЦФ на множестве планов сверху (при поиске максимума) или снизу (при поиске минимум).
VII. Определить координаты точки max (min) ЦФ и вычислить значение ЦФ . Для вычисления координат оптимальной точки необходимо решить систему уравнений прямых, на пересечении которых находится .
3. ПРИМЕНЕНИЕ ГРАФИЧЕСКОГО МЕТОДА РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ НА ПРАКТИКЕ.
3.1 Экономическая постановка задачи линейного программирования
Предприятие электронной промышленности выпускает две модели радиоприемников, причем каждая модель производится на отдельной технологической линии. Суточный объем первой линии - 60 изделий, второй линии - 80 изделий. На радиоприемник первой модели расходуется 15 однотипных элементов электронных схем, на радиоприемник второй модели - 10 таких же элементов. Максимальный суточный запас используемых элементов равен 950 единиц. Прибыли от реализации одного радиоприемника первой и второй моделей равны 40$ и 20$ соответственно. Определите оптимальные суточные объемы производства первой и второй моделей на основе графического решения задачи.
3.2 Построение математической модели.
Переменные задачи
В задаче требуется установить, сколько радиоприемников первой и второй модели надо производить. Поэтому искомыми величинами, а значит, и переменными задачи являются суточные объемы производства каждого типа радиоприемников:
– суточный объем производства радиоприемников первой модели, [шт/сутки];
– суточный объем производства радиоприемников второй модели, [шт/сутки];
Целевая функция
Цель задачи – добиться максимального дохода от реализации продукции. Т.е. критерием эффективности служит параметр суточного дохода, который должен стремиться к максимуму. Чтобы рассчитать величину суточного дохода от продажи радиоприемников обоих моделей, необходимо знать:
· их объемы производства, т.е. и радиоприемников в сутки;
· прибыль от их реализации – согласно условию, соответственно 40 и 20 $.
Таким образом, доход от продажи суточного объема производства радиоприемников первой модели равен $ в сутки, а от продажи радиоприемников второй модели – $ в сутки. Поэтому запишем ЦФ в виде суммы дохода от продажи радиоприемников первой и второй модели:
[$/сутки]
Ограничения
Возможные объемы производства радиоприемников и ограничиваются следующими условиями:
· количество элементов электронных схем, израсходованное в течении суток на производство радиоприемников обоих моделей, не может превышать суточного запаса этих элементов на складе;
· суточный объем первой технологической линии (производство радиоприемников первой модели) не может превышать 60 шт в сутки, второй (производство радиоприемников второй модели) – 80 шт;
· объемы производства радиоприемников не могут быть отрицательными.
Таким образом, все ограничения задачи делятся на 3 группы, обусловленные:
1) расходом элементов электронных схем;
2) суточным объемом технологических линий;
3)неотрицательностью объемов производства.
Запишем эти ограничения в математической форме:
1) Т.к. из условия на радиоприемники первой и второй модели необходимо 15 и 20 элементов соответственно, то данное ограничение имеет вид:
[шт/сутки]
2) Ограничения по суточному объему первой и второй технологических линий имеют вид:
3) Неотрицательность объемов производства задается как
.
Таким образом, математическая модель этой задачи имеет вид
3.3 Нахождение оптимального решения задачи с помощью линейного метода.
Математическую модель задачи о радиоприёмниках мы нашли на предыдущем шаге:
Построим прямые ограничений, для чего вычислим координаты точек пересечения этих прямых с осями координат (рис.3.1).
прямая (1) – точки (0;95) и (63,(3);0), прямая (2) проходит через точку параллельно оси , прямая (3) проходит через точку параллельно оси .
Рис.3.1. Графическое решение задачи о производстве радиоприемников.
Определим ОДР. Например, подставим точку (0;0) в исходное ограничение (1), получим , что является истинным неравенством, поэтому стрелкой обозначим полуплоскость, содержащую точку (0;0), т.е. расположенную правее и ниже прямой (1). Аналогично определим допустимые полуплоскости для остальных ограничений и укажем их стрелками у соответствующих прямых ограничений (см. рис.3.1). Общей областью, разрешенной всеми ограничениями, т.е. ОДР является многоугольник ABCDE.
Целевую прямую можно построить по уравнению
Точки пересечения с осями – (0;75) и (37,5;0)
Строим вектор из точки (0;0) в точку (40;20). Точка D – это последняя вершина многоугольника допустимых решений ABCDE, через которую проходит целевая прямая, двигаясь по направлению вектора . Поэтому D – это точка максимума ЦФ. Определим координаты точки D из системы уравнений прямых ограничений (1) и (2)
Получили точку D(60;5) [шт/сутки].
Максимальное значение ЦФ равно [$/сутки].
Таким образом, наилучшим режимом работы предприятия является ежесуточное производство радиоприемников первой модели в количестве 60 штук и радиоприемников второй модели в количестве 5 штук. Доход от продажи составит 2500$ в сутки.
4. АНАЛИЗ ЧУВСТВИТЕЛЬНОСТИ ОПТИМАЛЬНОГО РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Неизбежное колебание значений таких экономических параметров, как цены на продукцию и сырье, запасы сырья, спрос на рынке и т.д. может привести к неоптимальности или непригодности прежнего режима работы. Для учета подобных ситуаций проводится анализ чувствительности, т.е. анализ того, как возможные изменения параметров исходной модели повлияют на полученное ранее оптимальное решение задачи ЛП.
Для решения задач анализа чувствительности ограничения линейной модели классифицируются следующим образом. Связывающие ограничения проходят через оптимальную точку. Несвязывающие ограничения не проходят через оптимальную точку. Аналогично ресурс, представляемый связывающим ограничением, называют дефицитным, а ресурс, представляемый несвязывающим ограничением – недефицитным. Ограничение называют избыточным в том случае, если его исключение не влияет на ОДР и, следовательно, на оптимальное решение. Выделяют следующие три задачи анализа на чувствительность.
1. Анализ сокращения или увеличения ресурсов:
· на сколько можно увеличить (ограничения типа ) запас дефицитного ресурса для улучшения оптимального значения ЦФ?
· на сколько можно уменьшить (ограничения типа ) запас недефицитного ресурса при сохранении оптимального значения ЦФ?
2. Увеличение (ограничения типа ) запаса какого из ресурсов наиболее выгодно?
3. Анализ изменения коэффициентов ЦФ: каков диапазон изменения коэффициентов ЦФ, при котором не меняется оптимальное решение?
4.2. Методика графического анализа чувствительности оптимального решения.
Проанализируем чувствительность оптимального решения задачи о производстве радиоприемников. ОДР задачи (рис.3.1) – многоугольник ABCDE. В оптимальной точке D пересекаются прямые (1) и (2). Поэтому ограничения (1) и (2) являются связывающими, а соответствующие им ресурсы (суточный объем элементов электронных схем и производительность первой технологической линии) – дефицитными.
Страницы: 1, 2, 3, 4
