Метод, которым мы нашли оптимальное решение, можно назвать методом перебора угловых точек

Вершины многогранника называются угловыми точками.

Множество решений системы (1) является выпуклым многогранником (напомним, что выпуклое множество вместе с любыми двумя точками содержит все точки соединяющего их отрезка).

3. Оптимальное решение достигается хотя бы в одной угловой точке. Отсюда, принципиальный путь поиска оптимального решения: перебрать все угловые точки (их конечное число!) и среди них выбрать ту в которой целевая функция достигает максимума.

Остановимся подробнее на последнем пункте.

Прежде всего, как искать угловые точки?

а) найти базисные переменные, т.е. те m переменных, которым соответствует не равный 0 определитель. Остальные переменные- свободные.

б) выразить базисные переменные через свободные

в) свободные переменные приравнять к нулю и подсчитать значения базисных переменных.

г) отобрать только наборы переменных с неотрицательными компонентами (опорные решения)- это и будут угловые точки!

Пример 1: решить задачу линейного программирования в каноническом виде.

х₁ – х₂ + 4х₃ - 2х₄ = 2

3х₁ + 2х₂ - х₃ + 4х₄ = 3

х_i ≥ 0, i = 1,4

F= - 4x₁- 2x₂ + x₃ - x₄ → max

а) базисные переменные х₁, х₂

х₁-х₂ = 2 - 4х₃- 2х₄

3х₁+2х₂ =3 + х₃- 4х₄

х₁-х₂ = 2

3х₁+2х₂ =3 → x₁=7/5, x₂ = -3/5→ x =(7/5,-3/5,0,0) -базисное решение, но не опорное!

б) базисные переменные х₁,х₃

х₁+4х₃ = 2 + х₂ + 2х₄

3х₁- х₃ = 3 - 2х₄ - 4х₄

х₁+4х₃ = 2

3х₁- х₃ = 3 → x₁=14/13, x₂ = 3/13→ x =(14/13, 0, 3/13,0) -базисное решение, опорное!

в) базисные переменные х₁,х₄

х₁-2х₄ = 2 + х₂ - 4х₃

3х₁+4х₄ =3 - 2х₂+ х₃

х₁-2х₄ = 2

3х₁+4х₄ =3 → x₁=7/5, x₄ = -3/5→ x =(7/5, 0, 0, -3/5) -базисное решение, но не опорное!

г) базисные переменные х₂, х₃

- х₂+ 4х₃ = 2 – х₁ + 2х₄

2х₂-х₃ =3 - 3х₁-4 х₄

- х₂+ 4х₃ = 2

2х₂ - х₃ = 3 → x₂ =2, x₃ = 1→ x =(0, 2, 1, 0) -базисное решение, опорное!

д) базисные переменные х₃, х₄

4 х₃- 2х₄ = 2 – х₁ + х₂

-х₃+4х₄ =3 - 3х₁-2 х₂

4 х₃- 2х₄ = 2

- х₃+4х₄ =3 → x₃ =1, x₄ = 1→ x =(0, 0, 1, 1) -базисное решение, опорное!

Вычисляем критерий F в каждой из угловых точек:

F₂= -50/13, F₄= -3, F₅= 0

Оптимальное решение х = (0, 0, 1, 1) → F_max=0

Недостатки метода очевидны: даже при небольшом числе ограничений, число угловых точек велико, да и сам способ их нахождения весьма трудоемок.

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

а₁₁х₁ + а₁₂х₂+……а_1nх_n ≤ в₁

а₂₁х₁ + а₂₂х₂+……а_2nх_n ≤ в₂ (2)

……………………………

а_m1х₁ + а_m2х₂+……а_mnх_n ≤в_m

x_i ≥ 0, i = 1,n

F = c₁х₁ + c₂х₂+……c_nх_n → max

Геометрический смысл тот же, что и в п.1 (для задачи в каноническом виде).

Пример 2:

Участок цеха выпускает изделия двух видов. Исходные данные указаны в таблице стандартного вида:

Ресурсы	Запасы	Расх. коэфф.
1 2
Медь		5 3
Алюминий		1 2
Прибыль		2 3

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

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

Пусть х₁, х₂ количество изделий каждого вида, соответственно.

5х₁ + 3х₂ ≤ 45 (α)

х₁ + 2х₂ ≤ 16 (β)

х₁, х₂ ≥ 0

F = 2x₁ + 3x₂ → max

Далее эту задачу с двумя переменными можно решать двумя способами:

1. Привести к каноническому виду:

5х₁ + 3х₂+ х₃ = 45

х₁ + 2х₂ + х₄ = 16

х₁, х₂, х₃, х₄ ≥ 0

F = 2x₁ + 3x₂ → max

(х₃, х₄ – балансовые переменные)

Далее можно решать перебором угловых точек (см. выше).

Результат: х_опт.= (2, 7, 0, 0), F_max = 25

2. Мы, однако, воспользуемся другим методом - графоаналитическим.

Систему ограничений в стандартной форме перепишем так:

Рис. 1

Множество допустимых решений (многоугольник) заштриховано на рис 1. Среди точек этого многоугольника и нужно выбрать оптимальную.

Выше мы отметили, что оптимальная точка совпадет с угловой точкой (О, А, В, С). Чтобы их не перебирать поступим так:

Изобразим линию уровня F= 0 и отметим в точке О вектор- градиент. Из курса высшей математики мы знаем, что он ортогонален линии уровня и указывает направление возрастания целевой функции F. (нам это и нужно - прибыль).

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

Чтобы найти ее координаты заметим, что она лежит на прямых (α) и (β):

5х₁ + 3х₂ = 45

х₁ + 2х₂ =16

х_опт = (2,7) F_max = 25

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

Пример 3:

Предприниматель, обладая капиталом 30000 у.е. хочет сформировать пакет акций двух компаний (их цены 6 и 4, соответственно) исходя из следующих требований:

- общее число акций не превышает 6000

- число акций каждого вида не превышает 5000.

Ожидаемая прибыль 1,2 и 1 у.е. на каждую акцию, соответственно.

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

х₁, х₂ – количество акций каждого вида.

х₁ + х₂ ≤ 6000 (α)

х₁ ≤ 5000 (β)

х₂ ≤ 5000 (γ)

6х₁ + 4х₂ ≤ 30000 (δ)

х₁, х₂ ≥ 0

F = 1,2х₁ + х₂ →max

Воспользуемся графоаналитическим методом:

Рис.2

Оптимальная точка лежит на пересечении прямых (α) и (δ).

х₁ + х₂ = 6000

6х₁ + 4х₂ = 30000

х_опт = (3000, 3000) F_max = 6600

Дата добавления: 2014-12-27