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


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

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



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

 

 

Пусть дана задача:

Х = (х1; х2), max Z = c1x1 + c2x2,

Дадим геометрическую интерпретацию этой задачи:

а) построим плоскость Х1ОХ2. На этой плоскости каждое из линейных ограничений-неравенств задает некоторую полуплоскость. Полуплоскость – выпуклое множество, а пересечение выпуклых множеств – есть также выпуклое множество, значит область допустимых решений – есть выпуклое множество.

При построении области допустимых решений (ОДР) возможны следующие ситуации (рис. 3 – 8).

 

а б
Рис. 3 Рис. 4
ОДР – выпуклый многоугольник ОДР – неограниченная выпуклая многоугольная область
М
в

г
Рис. 5 ОДР – единственная точка Рис. 6 ОДР – прямая линия

 

Рис. 7 ОДР – пустое множество Рис. 8

б) перейдем к геометрической интерпретации целевой функции. Пусть ОДР – не пустое множество, например, многоугольник А1А2А3А4А5А6.(рис. 8).

Выберем произвольное значение целевой функции: Z = Zо = > c1х1 + + с2х2 = Zо – это уравнение прямой линии (обычно берут Zо = 0), ее называют линией уровня целевой функции. Чтобы установить направление возрастания (убывания) целевой функции, найдем ее частные производные ; .

Вектор  = g ra d z  – показывает направление наискорейшего возрастания целевой функции, вектор (- ) указы­вает направление наискорейшего убывания целевой функции, его назы­вают антиградиентом. Вектор  всегда перпендикулярен к линиям уровня

Правило решения задачи линейного программирования:

1) строим область допустимых решений;

2) строим ;

3) проводим произвольную линию уровня Z = Zо (для контроля убеждаемся, что прямая z = zo );

4) при решении задачи на mах перемещаем линию уровня Z = Zo параллельно самой себе в направлении вектора  до тех пор пока она не коснулась области ДР в ее угловой точке (до т. А4), пока она не станет опорной. В случае решения задачи на min линию уровня Z = Zo перемещают в антиградиентном направлении (до т. А1);

5) определяем оптимальный план * = (х1*; х2*), то есть координаты угловой точки касания и экстремальное значение целевой функции Z*=Z(x* ).

Возможны следующие случаи:

1) оптимальный план единственный: опорная линия и ОДР имеют одну общую точку (этот случай уже рассмотрен);

Рис. 9 2) оптимальных планов большое множество: в разрешающем положении опорная линия уровня совпадает со стороной ОДР (рис. 9);
Рис. 10 3) целевая функция не ограничена, линия уровня, сколько бы ее не продолжали, не может занять опорного положения (рис. 10);  
Рис. 11 4) ОДР – состоит из единственной точки, где целевая функция достигает одновременно и max и min (рис. 11);

5) задача не имеет решений, т. к. ОДР .

Пример 4. Задача использования сырья: найти max Z = 50х1 + 40х2, если

Решение.

Обозначим  Тогда:

1. Построим ОДР (рис. 12): для этого в системе координат Х1ОХ2 изобразим граничные прямые

  L1: 2x1 + 5x2 = 20, (0; 4) (10; 0);

L2: 8x1 + 5х2 = 40, (0; 8) (5; 0) (ОДР – многоугольник АВСДО);

    L3: 5x1 + 6х2 = 30, (0; 5) (6; 0).

2. = (50; 40) => удобно строить не вектор , а l , где . Строим ,(5; 4).

3. Строим линию уровня:

Z = 50x1 + 40x2 = 0 => x1 = –  = – 0,8x2, (0, 0), (– 4, 5)

и перемещаем ее в направлении . Эта прямая станет опорной в точке С. Функция Z принимает max значение в этой точке. Найдем точку С как точку пересечения прямых L2 и L3:

 = 48 – 25 = 23;  = 240 – 150 = 90;  = 240 – 200 = 40; оптимальный план: ,

Z max = 50 · 3,9 + 40 · 1,7 ≈ 260,3. Таким образом, чтобы получить max прибыль в размере 260,3 руб. надо запланировать производство 3,9 единиц продукции Р1 и 1,7 единиц продукции Р2.

Пример 5. Задача составления рациона: найти min Z = 4х1 + 6х2

 если 

Решение.

1. Строим ОДР Þ для этого в системе координат X1 ОХ2 изобразим граничные прямые (рис. 13):

L1: 3x1 + x2 = 9,   (0; 9) (3; 0); L2: x1 + 2х2 = 8,   (0; 4) (8; 0); L3: x1 + 6х2 = 12, (0; 2) (12; 0). 2.  = (4; 6). 3. Zo = 4x1 + 6x2- линия уровня.  Если 4x1 + 6x2 = 0,
Рис. 15.
  х1 = – х2, (6; – 4) (0; 0).

Рис. 13

4. Линия уровня станет опорной в точке В, найдем ее, решив систему:

 Þ Þ (·) В (2, 3).

Оптимальный план (2,3) Þ Zmin = 4 ∙ 2 + 6 ∙ 3 = 26.

Итак, чтобы обеспечить min затраты в день 26 руб. необходимо дневной рацион составить из 2 кг корма 1 и 3 кг корма 2.

Замечание. С помощью графического метода может быть решена задача линейного программирования, система ограничений которой содержит m-линейно независимых уравнений и если n – m = 2.

Пример 6.

Графическим методом найти оптимальный план задачи линейного программирования, при котором целевая функция Z = 2х1 – х2 + х3 – 3х4 + 4х5 достигает max значения при ограничениях:

то есть n = 5, m = 3 и n – m = 2

Решение.

1.  Решим систему методом полного исключения:

»

     

2. Подставляя эти значения в целевую функцию и в сис­тему ограничений, получаем задачу линейного программирования с двумя переменными и и Z = 12 – 2x4 + 6x5 – 70 + 7x4 + 10x5 + 20 + 4x4 – 5x5 – 3x4 + 4x5 = – 38 + 6x4 + 15x5.

Итак, найти max Z = – 38 + 6х4 + 15х5, если

– 4x + 5x   +x = 20

7x + 10x + x = 70

x – 3x + x    = 6

x (j = 1, 2, 3, 4, 5).

Отбрасывая в системе уравнений базисные переменные, приходим к системе неравенств:

3. Решаем полученную задачу графическим методом.

а) Построим ОДР в плоскости Х4ОХ5 (рис. 14).

Рис. 14

L1: – 4x4 + 5x5 = 20,    (0; 4) (– 5; 0),

L2: 7x4 + 10х5 = 70,     (0; 7) (10; 0),

L3: x4 – 3х5 = 6,          (0; – 2) (6; 0);

б)  = (6; 15) Þ l  = (2; 5),

в) Zo = – 38 Þ 6x4 + 15x5 = 0,

 (0; 0) (5; – 2).

г) Целевая функция принимает max значение в точке В, найдем ее

 Þ

max Z = – 38 + 12 + 84 = 58.

д) Для отыскания оптимального плана подставим значения х4 и х5 в x1, х2, х3, получим : х1 = ; х2 = 0; х3 = 0; х4 = 2; х5 = ;

Ответ:  = (; 0; 0; 2; ), max Z = 58.

 

Задания для самостоятельной работы

Задание 1. Решите графическим методом задачу линейного программирования (x 1 ≥ 0, x 2 ≥ 0):

 

1.

6.

11.

2.

7.

12.

3.

8.

13.

4.

9.

14.

5.

10.

15.

16.

21.

26.

17.

22.

27.

18.

23.

28.

19.

24.

29.

20.

25.

30.

                     

Задание 2. Найти графическим методом оптимальный план задач линейного программирования j ³ 0).

1. 8.
2. 9.
3. 10.
4. 11.
5. 12.
6. 13.
7. 14.

 

15. 23.
16. 24.
17. 25.
18. 26.
19. 27.
20 28.
21 29.
22. 30.

 



Поделиться:


Последнее изменение этой страницы: 2020-11-11; просмотров: 80; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.191.166.122 (0.067 с.)