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

                                

Рис.1. Оптимум функции Z достижим      Рис.2. Оптимум функции Z достигается в                  в точке А                                                                     любой точке |АB|                                                    

                                      

Рис.3. Оптимум функции Z недостижим.        Рис.4. Область допустимых решений –                                                                                                           

                                                                         пустая область.

          Для практического решения задачи линейного программирования (1.10) – (1.11) на основе ее геометрической интерпретации необходимо следующее: 
 
1. Построить прямые, уравнения которых получаются в результате замены в ограничениях (1.10) – (1.11) знаков неравенств на знаки равенств. 
2. Найти полуплоскости, определяемые каждым из ограничений. 
3. Определить многоугольник решений. 
4. Построить вектор  . 
5. Построить прямую  , проходящую через начало координат и перпендикулярную вектору  . 
6. Передвигать прямую Z в направлении вектора  , в результате чего либо находят точку (точки), в которой функция принимает максимальное значение, либо устанавливают неограниченность функции сверху на множестве планов. 
7. Определить точки координаты максимума функции и вычислить значение целевой функции в этой точке.

 

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

1) В ограничениях задачи заменить знаки неравенств знаками точных равенств и построить соответствующие прямые.

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

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

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

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

3) Определить ОДР как часть плоскости, принадлежащую одновременно всем разрешенным областям, и выделить ее. При отсутствии ОДР задача не имеет решений.

4) Если ОДР – не пустое множество, то нужно построить целевую прямую, т.е. любую из линий уровня    (где L – произвольное число, например, кратное и , т.е. удобное для проведения расчетов). Способ построения аналогичен построению прямых ограничений.

5) Построить вектор, который начинается в точке (0;0) и заканчивается в точке. Если целевая прямая и вектор построены верно, то они будут перпендикулярны.

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

7) Определить координаты точки max (min) ЦФ и вычислить значение ЦФ. Для вычисления координат оптимальной точки необходимо решить систему уравнений прямых, на пересечении которых находится. 

 

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

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

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

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

Целевая ячейка – это ячейка в модели вычисления, значения в которой должно быть максимизировано, минимизировано или же равняться определенному указанному значению. Она должна содержать формулу, которая прямо или косвенно ссылается на изменяемые ячейки, или же самой быть изменяемой.

Значения в изменяемых ячейках будут последовательно (методом итераций) изменяться до тех пор, пока  не будет получено нужное значение в целевой ячейке. Эти ячейки, следовательно, прямо или косвенно  должны влиять на значение целевой ячейки.

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

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

Предприятие выпускает два вида продукции: Изделие 1 (кирпичи) и Изделие 2 (блоки). На изготовление единицы Изделия 1 (кирпича) требуется затратить a11 кг сырья первого типа, a21 кг сырья второго типа, a31 кг сырья третьего типа.

На изготовление единицы Изделия 2 (блоков) требуется затратить a12 кг сырья первого типа, a22 кг сырья второго типа, a32 кг сырья третьего типа.

Производство обеспечено сырьем каждого типа в количестве b1 кг, b2 кг, b3 кг соответственно.

Рыночная цена единицы Изделия 1(кирпича) составляет c1 тыс. руб., а единицы Изделия 2 (блоков) - c 2 тыс.руб.

Требуется:

1) построить экономико  – математическую модель задачи;

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

3) составить план производства изделий, обеспечивающий максимальную выручку от их реализации, используя надстройку «Поиск решения» в среде MS EXCEL

А11=2	А12=7	В1=560	С1=55
А21=3	А22=3	В2=300	С2=35
А31=5	А32=1	В3=332

 

1) Математическая модель  задачи.

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

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

x1 – количество изделий вида 1;

x2 – количество изделий вида 2.

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

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

изделий, необходимо знать:

• выпускаемое количество изделий каждого вида, т.е. х1 и х2;

• прибыль от их реализации – согласно условию, соответственно 55 и 35 тыс. руб.

Таким образом, прибыль от реализации выпускаемых изделий вида 1 равна 55х1тыс.руб., а от реализации изделий вида 2 – 35х2 тыс.руб. Поэтому запишем ЦФ в виде суммы прибыли от продажи каждого из видов изделий:

Z( Х) = 55x1 + 35x2 → max

Ограничения

Возможное оптимальное количество изделий каждого вида х1 и х2 ограничивается следующими условиями:

• Заданными ресурсами - 1,2 и 3, которые используются на выпуск каждого вида изделия, не могут превышать общего запаса ресурсов;

• количество каждого вида изделия не может быть отрицательным.

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

по расходу ресурса 1: 2x1 + 7x2 ≤ 560 ,

по расходу ресурса 2: 3x1 + 3x2 ≤ 300,

по расходу ресурса 3: 5x1 + x2 ≤ 332

не отрицательность количества выпускаемых изделий задаётся так:

х1≥0, x2≥0.

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

Z x)( = 55x1 + 35x2 → max

2х1+7х2≤560;

3х1+3х2≤300;

5х1+х2≤332;

х1≥0;

х2≥0.

 

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

методoм

Так как переменные задачи x1 и x2 входят в целевую линейную функцию и

ограничения задачи линейны, то соответствующая задача оптимизации – задача

линейного программирования.

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

(1): 2x1 + 7x2 ≤ 560 . Сначала строится  разделяющая прямая 2x1 + 7x2 = 560 . Для

этого находим две точки, через которые она проходит:

Х1	0	280
Х2	80	0

 

Подставим точку (0;0) в неравенство (1): 0 ≤ 560 - верно, поэтому стрелки указывают на полуплоскость к нулю.

(2): 3x1 + 3x2 ≤ 300. Разделяющая  прямая 3x1 + 3x2 = 300, найдём точки:

Х1	0	100
Х2	100	0

 

Подставим точку (0;0) в неравенство (2): 0 ≤ 300 - верно, поэтому стрелки указывают на полуплоскость к нулю.

(3): 5x1 + x2 ≤ 332. Разделяющая  прямая 5x1 + x2 = 332, найдём точки:

Х1	0	66,4
Х2	332	0

 

Подставим точку (0;0) в неравенство (3): 0 ≤ 332 - верно, поэтому стрелки указывают на полуплоскость к нулю. Находим многоугольник, в котором пересекаются, накладываются друг на друга все построенные полуплоскости. Многоугольник допустимых решений заштриховывается.

Построим градиент и линию уровня функции цели:

Z(X )= 55x1+ 35x2⇒ g (55;35). Градиент всегда изображается с началом в т.(0;0).

Любая линия уровня перпендикулярна градиенту. Удобно построить линию

уровня Z = 0 , также проходящую через начало координат: 55x1 + 35x2 = 0.

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

3x1+3x2=300;

5x1+x2=332.

Второе уравнение умножим на (-3):

 

3x1+3x2=300;

-15x1-3x2=-996.

сложим уравнения

-12x1=-696; x1=58; x2=332-5x1=332-5*58=42.

Следовательно, Amax(58;42) , Zmax(58;42= 55* 58+ 35* 42= 4660.

Ответ: изделия вида 1 необходимо выпускать в количестве 58 единиц, а изделия вида 2 в количестве 42 единицы. При этом прибыль от их реализации максимальная и составит 4660 тыс. руб.

 

2. 3 Решение задачи с помощью электронной таблицы  Excel

          Для решения рассмотренной задачи в среде Excel заполним ячейки исходными данными (в виде таблицы) и формулами математической модели. Excel позволяет получить оптимальное решение без ограничения размерности системы неравенств и целевой функции.

Таблица в режиме чисел

Таблица в режиме формул

Здесь: В9:С9 – результат (оптимальное количество изделий каждого вида);

В6:С6 – коэффициенты целевой функции;