Материал: УП - Методы оптимальных решений

Пример 3. Даны точки А₁(3; – 2; 5) и A₂(– 1; 6; 1). Найти точку А (х₁; х₂; x₃), являющуюся линейной комбинацией точек А₁ и A₂. Так как точка А является линейной комбинацией точек А₁ и A₂, то Ā = = ₁Ā₁ + ₂Ā₂, ₁  0, ₁ + ₂ = 1.

_{Пусть, например, 1 = , тогда 2 =  (х1; х2; x3) = (3; –2; 5) + + (-1; 6; 1) = ( ; ; ), отсюда х1 = ; х2 = ; х3 =} .

Теорема 2

Если система векторов , , …, содержит m линейно незави­симых векторов , , , то допустимый план

= (х₁, х₂, …, x_m, 0, 0…0), n – является угловой точкой мно-

( )

гоугольника планов.

Теорема 3

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

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

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

_{Пусть дана задача:}

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

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

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

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

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

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

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

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

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

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

2) строим ;

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

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

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

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

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

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) => удобно строить не вектор , а  , где . Строим _,(5; 4).

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

Z

Рис. 12

и перемещаем ее в направлении . Эта прямая станет опорной в точке С. Функция 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. Решим систему методом полного исключения: