Графический метод решения задач линейного программирования

иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку.

Поскольку и должны быть неотрицательными, то их допустимые значения всегда будут находиться выше оси и правее оси , т.е. в I-м квадранте.

Ограничения-равенства разрешают только те точки, которые лежат на соответствующей прямой. Поэтому необходимо выделить на графике такие прямые.

3. Определить ОДР как часть плоскости, принадлежащую одновременно всем разрешенным областям, и выделить ее. При отсутствии ОДР задача не имеет решений.
4. Если ОДР – не пустое множество, то нужно построить целевую прямую, т.е. любую из линий уровня    (где L – произвольное число, например, кратное и , т.е. удобное для проведения расчетов). Способ построения аналогичен построению прямых ограничений.
5. Построить вектор , который начинается в точке (0;0) и заканчивается в точке . Если целевая прямая и вектор построены верно, то они будут перпендикулярны.
6. При поиске максимума ЦФ необходимо передвигать целевую прямую в направлении вектора , при поиске минимума ЦФ – против направления вектора . Последняя по ходу движения вершина ОДР будет точкой максимума или минимума ЦФ. Если такой точки (точек) не существует, то можно сделать вывод о неограниченности ЦФ на множестве планов сверху (при поиске максимума) или снизу (при поиске минимум).
7. Определить координаты точки max (min) ЦФ и вычислить значение ЦФ . Для вычисления координат оптимальной точки необходимо решить систему уравнений прямых, на пересечении которых находится .

 

2 ПРИМЕНЕНИЕ ГРАФИЧЕСКОГО  МЕТОДА РЕШЕНИЯ ЗАДАЧИ  ЛИНЕЙНОГО  ПРОГРАММИРОВАНИЯ НА ПРАКТИКЕ

 

2.1 Решение обычной задачи ЛП графическим методом

Пример1.

     

 

Решение.

Построим систему координат. По горизонтальной оси откладывают значения переменной , а по вертикальной – значения переменной .

Этап 1. Строим прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств.

Границей полуплоскости является прямая . Рассмотрим первое уравнение , обозначим его цифрой (I) и выразим переменную через переменную .  В результате преобразований получим следующее уравнение прямой . Данная прямая проходит через точки с координатами (0;5) и (6;3). Построим прямую на графике (рис. 9).

Для второго уравнения , обозначенного цифрой (II), выражение переменной через переменную примет следующий вид .  Прямая (II) проходит через точки с координатами (3;4) и (4;1). Эту прямую также построим на графике (рисунок 7).

Этап 2. Находим полуплоскости, определяемые каждым из ограничений задачи.

Рассмотрим неравенство . Прямая (I) делит всю плоскость на две части и рассматриваемое неравенство определяет только одну из них. Для определения полуплоскости, заданной неравенством возьмем контрольную точку, не принадлежащую прямой (I), с известными координатами, например точку О(0;0). Координаты контрольной точки подставим в неравенство и получим выражение вида . Неравенство выполняется, координаты контрольной точки удовлетворяют ему, следовательно, полуплоскость, которой принадлежит точка О, и определяется исследуемым неравенством . На рисунке полуплоскость, заданную неравенством , отмечаем короткими штрихами.

 

Рисунок 7 – Многоугольник допустимых решений, исходная линия уровня и вектор

задачи

 

Аналогично, для исследования неравенства выберем, в качестве контрольной точке, вновь точку О(0;0). После подстановке координат указанной точки, получаем верное неравенство . Неравенство задает ту полуплоскость, которой принадлежит контрольная точка О(0;0). Отметим короткими штрихами допустимую полуплоскость.

Условие неотрицательности переменных требует рассмотрения той части многоугольника решений, которая находится в первой координатной четверти, т.е. выше оси и правее оси .

Этап 3. Находим многоугольник решений как часть плоскости, которая одновременно удовлетворяет требованиям первого,  второму неравенства и условию неотрицательности. В нашем случае, это выпуклый многоугольник ОАВС – область допустимых решений данной системы неравенств.

Этап 4. Строим исходную линию уровня . Прямая примет вид . Выразим переменную через переменную и получим равенство . Эта прямая проходит через точки с координатами (0;0) и (3;-2).

Этап 5. Строим  вектор . Вектор =(2;3) перпендикулярен исходной линии уровня и указывает направление, в котором эта функция возрастает с наибольшей скоростью.

Этап 6. Определяем точку, в которой целевая функция z принимает максимальное значение. Для этого исходную линию уровня передвигаем в направлении вектора . При движении в этом направлении последней общей точкой прямой с многоугольником решений является точка В. В этой точке целевая функция принимает максимальное значение.

Этап 7. Определяем координаты точки B и вычисляем значение целевой функции в этой точке. Точка B лежит на пересечении прямых (I) и (II). Для нахождения координат точки В решим систему уравнений

В результате решения системы уравнений найдены координаты точки В(3;4). Подставим координаты этой точки в выражения для целевой функции и получим максимальное её значение  .

Ответ: при х1=3, х2=4.

2.2 Экономическая постановка задачи линейного программирования

Предприятие электронной промышленности выпускает две модели радиоприемников, причем каждая модель производится на отдельной технологической линии. Суточный объем первой линии - 60 изделий, второй линии - 80 изделий. На радиоприемник первой модели расходуется 15 однотипных элементов электронных схем, на радиоприемник второй модели - 10 таких же элементов. Максимальный суточный запас используемых элементов равен 950 единиц. Прибыли от реализации одного радиоприемника первой и второй моделей равны 40$ и 20$ соответственно. Определите оптимальные суточные объемы производства первой и второй моделей на основе графического решения задачи.

Переменные задачи

В задаче  требуется установить, сколько радиоприемников первой и второй модели надо производить. Поэтому искомыми величинами, а значит, и переменными задачи являются суточные объемы производства каждого типа радиоприемников:

 – суточный объем производства радиоприемников первой модели, [шт/сутки];

 – суточный объем производства радиоприемников второй модели, [шт/сутки];

Целевая функция

Цель задачи  – добиться максимального дохода от реализации продукции. Т.е. критерием эффективности служит параметр суточного дохода, который должен стремиться к максимуму. Чтобы рассчитать величину суточного дохода от продажи радиоприемников обоих моделей, необходимо знать:

• их объемы производства, т.е. и радиоприемников в сутки;
• прибыль от их реализации  – согласно условию, соответственно 40 и 20 $.

Таким образом, доход от продажи суточного объема производства радиоприемников первой модели равен $ в сутки, а от продажи радиоприемников второй модели – $  в сутки. Поэтому запишем ЦФ в виде суммы дохода от продажи радиоприемников первой и второй модели:

[$/сутки]

Ограничения

Возможные объемы производства радиоприемников и ограничиваются следующими условиями:

• количество элементов электронных схем, израсходованное в течении суток на производство радиоприемников обоих моделей, не может превышать суточного запаса этих элементов на складе;
• суточный объем первой технологической линии (производство радиоприемников первой модели) не может превышать 60 шт в сутки, второй (производство радиоприемников второй модели) – 80 шт;
• объемы производства радиоприемников не могут быть отрицательными.

Таким образом, все ограничения задачи делятся на 3 группы, обусловленные:

1) расходом элементов электронных схем;

2) суточным объемом технологических линий;

3)неотрицательностью объемов производства.

Запишем эти ограничения в математической форме:

1. Т.к. из условия на радиоприемники первой и второй модели необходимо 15 и 20 элементов соответственно, то данное ограничение имеет вид:

[шт/сутки]

2. Ограничения по суточному объему первой и второй технологических линий имеют вид:

 [шт/сутки]

3. Неотрицательность объемов производства задается как

.

Таким образом, математическая модель этой задачи имеет вид:

 

 

Построим прямые ограничений, для чего вычислим координаты точек пересечения этих прямых с осями координат (рис.8).

прямая (2.1) – точки (0;95) и (63,(3);0), прямая (2.2) проходит через точку параллельно оси , прямая (2.3) проходит через точку параллельно оси .

Рисунок 8 – Графическое решение задачи о производстве радиоприемников

 

Определим ОДР. Например, подставим точку (0;0) в исходное ограничение (1), получим , что является истинным неравенством, поэтому стрелкой обозначим полуплоскость, содержащую точку (0;0), т.е. расположенную правее и ниже прямой (2.1). Аналогично определим допустимые полуплоскости для остальных ограничений и укажем их стрелками у соответствующих прямых ограничений (см. рис.8). Общей областью, разрешенной всеми ограничениями, т.е. ОДР является многоугольник ABCDE.

Целевую прямую можно построить по уравнению

Точки пересечения с осями – (0;75) и (37,5;0)

Строим вектор из точки (0;0) в точку (40;20). Точка D – это последняя вершина многоугольника допустимых решений ABCDE, через которую проходит целевая прямая, двигаясь по направлению вектора . Поэтому D – это точка максимума ЦФ. Определим координаты точки D из системы уравнений прямых ограничений (1) и (2)

Получили точку D(60;5) [шт/сутки].

Максимальное значение ЦФ равно [$/сутки].

Таким образом, наилучшим режимом работы предприятия является ежесуточное производство радиоприемников первой модели в количестве 60 штук и радиоприемников второй модели в количестве 5 штук. Доход от продажи составит  2500$ в сутки.

2.3 Решение задачи ЛП средствами  программного продукта Gsimplex

Программа сама приводит задачу к каноническому виду, и производить ее графическое решение, отображая на графике прямые ограничений, область допустимых решений, и направляющий вектор. Решение получается очень наглядным и понятным. Можно отключать/включать отображение на графике некоторые элементы решения, например - координатную сетку или закраску ОДР ну и т.д. Также можно масштабировать график, что делает изучение решения задачи еще более наглядным и удобным.

После решения задачи, можно посмотреть и изучить соответствующую теорию, которая встроена в саму программу! Достаточно лишь нажать кнопку "Теория".

Рассмотрим наглядно шаги, которые необходимо пройти для решения задачи в данном продукте Gsimplex:

1. Необходимо задать количество ограничений нашей задачи.

 

Рисунок 9 – Ввод количества ограничений задачи

2. Необходимо ввести коэффициенты целевой функции, системы ограничений, свободные члены,  а также указать задачу на максимум или на минимум мы решаем:

Рисунок 10 – Форма ввода основных коэффициентов

3. Остается нажать кнопку «ОК». Решение представляется в виде графика и текстового решения.

 Рисунок 11 – Вывод готового решения

 

Заключение

В ходе выполнения курсовой работы мы ознакомились с таким разделом математического программирования как линейное программирование. Также рассмотрены методы решения данного рода задач, а  подробнее рассмотрен  графический метод решения задач такого рода.

Во второй части курсовой работы рассмотрены примеры решения задач линейного программирования графическим методом. Первый пример не несет никакой смысловой нагрузки; второй же несет строго экономический смысл. Следует также выделить основные достоинства и недостатки графического метода. Данный метод достаточно прост и нагляден, решение задачи отображается на одном чертеже. Недостатком данного метода является его ограниченность, т.е. так можно решить задачи содержащие в прямой или двойственной форме две переменные. А большинство экономических задач содержит гораздо больше переменных, поэтому применение графического метода ограничено.

Во втором разделе описан программный продукт Gsimplex, который достаточно быстро решает данную задачу. Решение можно продемонстрировать как в графическом виде так и аналитически.