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

     Все вышесказанное относится и к  случаю, когда система ограничений (1.2) включает равенства, поскольку любое равенство

     

     можно представить в виде системы двух неравенств

     

     ЦФ  при фиксированном значении определяет на плоскости прямую линию . Изменяя значения L, мы получим семейство параллельных прямых, называемых линиями уровня.

     Это связано с тем, что изменение  значения L повлечет изменение лишь длины отрезка, отсекаемого линией уровня на оси (начальная ордината), а угловой коэффициент прямой останется постоянным. Поэтому для решения будет достаточно построить одну из линий уровня, произвольно выбрав значение L.

     Вектор  с координатами из коэффициентов ЦФ при и перпендикулярен к каждой из линий уровня (см. рис.2.1). Направление вектора совпадает с направлением возрастания ЦФ, что является важным моментом для решения задач. Направление убывания ЦФ противоположно направлению вектора .

     Суть  графического метода заключается в  следующем. По направлению (против направления) вектора  в ОДР производится поиск оптимальной точки . Оптимальной считается точка, через которую проходит линия уровня , соответствующая наибольшему (наименьшему) значению функции . Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне.

     При поиске оптимального решения задач  линейного программирования возможны следующие ситуации: существует единственное решение задачи; существует бесконечное  множество решений (альтернативный оптиум); ЦФ не ограничена; область допустимых решений – единственная точка; задача не имеет решений. 

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

     

1. В ограничениях задачи (1.2) заменить знаки неравенств знаками точных равенств и построить соответствующие прямые.
2. Найти и заштриховать полуплоскости, разрешенные каждым из ограничений-неравенств задачи (1.2). Для этого нужно подставить в конкретное неравенство координаты какой-либо точки [например, (0;0)], и проверить истинность полученного неравенства.

           Если  неравенство истинное,

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

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

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

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

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

 

5. Линейное программирование в электронной таблице Excel.

Поиск решения.

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

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

1. Целевая ячейка – это ячейка в модели вычисления, значения в которой должно быть максимизировано, минимизировано или же равняться определенному указанному значению. Она должна содержать формулу, которая прямо или косвенно ссылается на изменяемые ячейки, или же самой быть изменяемой.
2. Значения в изменяемых ячейках будут последовательно (методом итераций) изменяться до тех пор, пока  не будет получено нужное значение в целевой ячейке. Эти ячейки, следовательно, прямо или косвенно  должны влиять на значение целевой ячейки.
3. Вы можете задать как для целевой, так и для изменяемых ячеек, ограничения и граничные условия. Можно задать также ограничения для других ячеек. Прямо или косвенно присутствующих в модели. 

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

      Ограничения – это условия, которые должны быть выполнены аппаратом поиска решения при оптимизации модели. 

Вывод по главе I:

Изучение литературы показало, что:

     1. Линейное программирование - это один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование».

     Линейное  программирование представляет собой  наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:

• рационального использования сырья и материалов; задачи оптимизации раскроя;
• оптимизации производственной программы предприятий;
• оптимального размещения и концентрации производства;
• составления оптимального плана перевозок, работы транспорта;
• управления производственными запасами;
• и многие другие, принадлежащие сфере оптимального планирования.

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

     Суть  графического метода заключается в  следующем. По направлению (против направления) вектора  в ОДР производится поиск оптимальной точки  . Оптимальной считается точка, через которую проходит линия уровня , соответствующая наибольшему (наименьшему) значению функции . Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне. 

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

1. Построение математической модели 

        Обозначим оптимальное количество издаваемых журналов «Автомеханик» и «Инструмент»  х₁ и х₂ тысяч экземпляров, соответственно:

        На печать х₁ тысяч экземпляров журнала «Автомеханик» в типографии «Алмаз-Пресс» должно расходоваться 2х₁ ч, т. к на печать одной тысячи экземпляров расходуется 2ч. Аналогично на печать х₂ тысяч экземпляров журнала «Инструмент» в типографии «Алмаз-Пресс» должно расходоваться 14х₂ ч, т. к на печать одной тысячи экземпляров расходуется 14ч. Следовательно, на печать всех журналов в типографии «Алмаз-Пресс» расходуется (2х₁+14х₂)ч, ресурс времени которого равен 112ч. Поэтому должно выполняться следующее действие: 2х₁+14х₂≤112

         На печать Х₁ тысяч экземпляров журнала «Автомеханик» в типографии «Корелия-Принт»  должно расходоваться 4х₁ ч, т. к на печать одной тысячи экземпляров расходуется 4ч. Аналогично на печать х₂ тысяч экземпляров журналов «Инструмент» в типографии «Корелия-Принт» должно расходоваться 6х₂ч, т. к на печать одной тысячи экземпляров расходуется 6ч. Следовательно, на печать всех журналов в типографии «Корелия-Принт» расходуется (4х₁=6х₂)ч, ресурс времени которого равен 70ч. Поэтому должно выполняться следующее неравенство: 4х₁+6х₂≤70

         На печать х₁ тысяч экземпляров журнала «Автомеханик» в типографии «Hansaprint» должно расходоваться 6х₁ч, т. к на печать одной тысячи экземпляров расходуется 6ч. На печать х₂ тысяч экземпляров журнала «Инструмент» в типографии «Hansaprint» должно расходоваться 4х₂ , т. к на печать одной тысячи экземпляров расходуется 4ч. Следовательно, на печать всех журналов в типографии «Hansaprint» расходуется (6х₁+4х₂)ч, ресурс времени которого равен 80ч. Поэтому должно выполняться неравенство: 6х₁+4х₂≤80

        Спрос на журнал «Автомеханик» составляет не более 12 тысяч экземпляров, а спрос на журнал «Инструмент» составляет не более 7,5 тысяч экземпляров. Поэтому можно записать неравенство: х₁≤12, х₂≤7,5

        Объем печати и соответственно продажа журналов не может принимать отрицательных значений. В связи с этим необходимо записать условие неотрицательности переменных: х₁≥0, х₂≥0

        Критерием, по которому определяется степень достижения поставленной цели, является выручка от продажи журналов. Поэтому целевую функцию можно записать таким образом: Z(х) =16х₁+12х₂→max

      Таким образом, математическую модель задачи можно представить в следующем виде:

   2х₁+14х₂≤112

   4х₁+6х₂≤70

   6х₁+4х₂≤80

   х₁≤12

   х₂≤7,5 

Обеспечиваем  максимальную выручку от продажи  журналов в соответствии с целевой  функцией: Z(х) =16х₁+12х₂→max 
 
 
 
 
 

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

         Построим множество возможных  решений.

Рис 1. Множество возможных решений. 

          Каждое неравенство на плоскости  задает прямую и полуплоскость  относительно этой прямой. Изобразим в системе координат первое неравенство 2х₁+14х₂≤112. Сначала построим границу искомой плоскости, то есть прямую 2х₁+14₂=112

 

         Изобразим в системе координат  второе неравенство 6х₁+4х₂≤70. Построим прямую 4х₁₊6х₂=70