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

↑

▷ Содержание

⇐ ПредыдущаяСтр 6 из 15Следующая ⇒

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

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

Х = (х₁; х₂), max Z = c₁x₁ + c₂x₂,

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

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

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

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

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

Рис. 8

б) перейдем к геометрической интерпретации целевой функции. Пусть ОДР – не пустое множество, например, многоугольник А₁А₂А₃А₄А₅А₆.(рис. 8).

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

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

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

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

2) строим ;

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

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

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

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

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

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

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

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

Решение.

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

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

  L₁: 2x₁ + 5x₂ = 20, (0; 4) (10; 0);

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

    L₃: 5x₁ + 6х₂ = 30, (0; 5) (6; 0).

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

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

Z = 50x₁ + 40x₂ = 0 => x₁ = –  = – 0,8x₂, (0, 0), (– 4, 5)

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

 = 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,7 единиц продукции Р₂.

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

 если 

Решение.

1. Строим ОДР Þ для этого в системе координат X₁ ОХ₂ изобразим граничные прямые (рис. 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) Þ Z_min = 4 ∙ 2 + 6 ∙ 3 = 26.

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

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

Пример 6.

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

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

Решение.

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

»

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

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

– 4x + 5x   +x = 20

7x + 10x + x = 70

x – 3x + x    = 6

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

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

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

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

Рис. 14

L₁: – 4x₄ + 5x₅ = 20,    (0; 4) (– 5; 0),

L₂: 7x₄ + 10х₅ = 70,     (0; 7) (10; 0),

L₃: x₄ – 3х₅ = 6,          (0; – 2) (6; 0);

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

в) Z_o = – 38 Þ 6x₄ + 15x₅ = 0,

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

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

 Þ

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

д) Для отыскания оптимального плана подставим значения х₄ и х₅ в x₁, х₂, х₃, получим : х₁ = ; х₂ = 0; х₃ = 0; х₄ = 2; х₅ = ;

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

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

Задание 1. Решите графическим методом задачу линейного программирования (x ₁ ≥ 0, x ₂ ≥ 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.

Познавательные статьи:



Организация работы процедурного кабинета

Статус республик в составе РФ

Понятие финансов, их функции и особенности

Сущность демографической политии