Файл: Говар В.М. Математическое программирование учеб. пособие.pdf

Ö 3. ГРАФИЧЕСКИЙ МЕТОД

Графическим методом можно решать задачи

только в двумерном и

в трехмерном пространствах. Наиболее наглядным

является решение

Сформулируем

задачу для этого случая.

Необходимо

найти

экстремальное

(минимальное

или максимальное)

значение функции

цели

(3.1).

L ( X )

= сj Xj + с 2

х 2

при' следующих

ограничениях:

3JJXJ

+ 3j2^2

"== " I '

2

(3.2)

а ШІх І + a m2x 2

-

Из курса линейной алгебры известно, что множество решений

системы линейных неравенств с двумя неизвестными

(3.2) геометри­

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

Из этого множества

рать

из них искомые.

Пример: найти

(3.3)

L

( X )

= 7Xj >

4 х 2 - - > т і П

при

следующих

ограничениях:

.

_

Х І

+ 2х2

k,

I

t3.4)

^ 3Xj * 2x2

^

6,

П

I

X-,

•=»

0.

Ш

чений

(3.4)

; решением

неравенства I Xj + 2

х 2 ^=

4 геометрически

будет

являться

одна

из

полуплоскостей, на которые

граничная пря­

мая х т

+ 2

х ?

= 4

разделяет координатную

плоскость.

Рис. 3.1

Для того, чтобы узнать точки какой полуплоскости удовлетворя­

ют неравенству

I

,

л него подставляем координаты любой

точки, ко­

ординатной плоскости. Если граничная прямая

не

проходит

через на­

чало координат,

то для проверки

удобнее всего

подставлять в

иссле­

дуемое неравенство координаты (0;0).

Еро-ерим, будут ли удовлетворять координаты начала координат

неравенству 1 :

0

+ 2 * О ,

4

Следовательно,

решением неравенства Т будет являться множест­

во точек

полуплоскости,

содержащей начало координат.

На рис.

3.1

полуплоскость решения неравенства Т отмечена стрелками.

Аналогично строим на графике граничные

прямые 3Xj + 2 х 2

= 6

и * 2 = 0

(уравнение

оси

Ох^) соответственно

для неравенств

И и _•,

к находим

искомые

полуплоскости

для каждого

из

этих

неравенств.

(3.4)

ѳделом. Такоиым л рассматриваемом примере будет треуголь­

ник

A B C (рис.3.2)

" X j

+

2 х 2

=

4

,

3Xj

+

2 х 2

=

6

,

2 х І = 2 или Xj = I .

•

•

цели (3.3) в этих

точках:

L a

«

7«

I

+

4

•

1,5

=

13",

с

7*

4

+

4

*

О

= 28

,

[_с

= Т 2 + 4 * О

=

14 .

Сравнивая полученные

значения,

делаем

вывод, что функция цели

'

-

•

Прямую из этого семейства

(3.1),

проходящую

через

начало

координат

(при L= 0),

будем называть начальной прямой

Предположим,

что решением системы ограничений

(3.2)

будет

являться выпуклый многоугольник

А Б С Д Е

и начальной

прямой

функции цели

(3.1)

будет

Ь 0

точке А.функция цели получает

минимальное

значение, то в точке Д

она принимает

максимальное значение.

Б соответствии с изложенным выше можно

сформулировать следую­

щий алгоритм для решения задач

графическим

способом в двумерном

пространстве.

1.

Строим многоугольник решений системы ограничений (3.2);

2.

Проводим начальную прямую и 0 из семейства прямых ( 3 . 1 ) ;

3.

Перемещаем начальную прямую параллельно

самой себе до тех

пор,пока она не займет

положения

опорных

прямых.

4.

Для отыскания искомых

оптимальных

значений подставляем в

( З Л )

координаты вершин многоугольника решений, через ко-

юрые проходят

опорные прямые.

Пример.

Найти

(3 . 5)

L

( X ) = І2х т + 6xp^md<

при следующих

ограничениях:

4£j + х 2

^ 12

, J .

(3.6)

х т

+ 2х.

10

,

Д

2? о

,

ж

Строим прямоугольник

системы ограничений

(3.6)

.

Получаем

многоугольник

О А Б С. Затем проводим начальную прямую

і_0

»

то есть

L 0 =

12Xj + 6х2

= 0. Это уравнение

прямой, проходя-

щей через начало координат. Для ее построения

необходимо

знать

координаты хотя бы еще одной точки. Придадим Xj какое-нибудь

произвольное значение,

например, X j = I ,

тогда

12*I

•

6х 2

=

0.

Откуда х 2

=-2.

Следовательно, начальная

прямая

L 0

проходит

через точки (0; 0) и ( I ; -2).

После построения

і_0

мы видим, что начальная прямая

совпа