Черненко В.Д. Высшая математика в примерах и задачах (том 3)

Подождите немного. Документ загружается.

120

Гпава 24

6°.

Отметим некоторые общие свойства решений ОЗЛП.

Решение ОЗЛП, если оно существует, не может лежать

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

Решение может быть и не единственным. Так, если прямая

уровня совпадает со

стороной,

то решений бесчисленное множество.

ОЗЛП может не иметь решений, даже когда существует

ОДР.

Это бывает, когда ОДР неограничена.

Для того, чтобы найти оптимальное

решение,

достаточно

перебрать все вершины ОДР и выбрать из них

ту,

где функция L

достигает максимума.

Решением всегда является одна из вершин многоугольни-

ка. Решение, лежащее в одной из вершин, называется опорным,

а сама вершина —

опорной

точкой,

2.1.

Найти наибольшее и наименьшее значение функции

L = Xy+2jc^ при ограничениях Xj - Зх^ < 0; 6xj + х^ - 12 > 0;

Xj + 5x^-25 < 0.

Решение. Обозначим штриховкой полуплоскости, которые

являются областями решений соответствующих неравенств.

Областью решения системы неравенств будет треугольник ABC

(рис.

24.

И).

л%

Рис. 24.11

Построим вектор с=(\;2) ипроведем линию уровняХу+2л-^=

через точку

(0,0).

Будем теперь перемещать линию уровня па-

раллельно самой

себе в

положительном направлении вектора с

•

ПИНЕИНОЕ и аИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

121

Опорная прямая проходит через точку А(—;—) — это первая

точка пересечения треугольника решений с линией

уровня.

точ-

ке А целевая функция L будет иметь наименьшее значение

_36

— - —

Опорная прямая при выходе из треугольника решений бу-

0/75 25. ^

дет проходить через точку

В(—;—),

следовательно в точке В

о о

целевая функция L принимает наибольшее значение

125

8 •

2.2.

Найти наибольшее и наименьшее значение функции

L= =

?>Xj-^2x2

при ограничениях х^ + 1 > 0; л:^ - х^ - 1 < 0;

^Xj - Ах^ + 12 > 0; х^ + 2х^- 8 < 0.

Решение. Обозначив штриховкой полуплоскости, которые

являются областями решений соответствующих неравенств, на-

ходим, что областью решения системы неравенств является че-

тырехугольник ABCD (рис. 24.12).

^75 50

Рис. 24.12

Строим вектор с-(Ъ;2) и проводим линию уровня

3xj-^2x2 =

через начало координат. Поскольку нас интере-

суют только положительные решения, то область допусти-

122 Гпава 24

МЫХ решений ограничена неравенствами х^ > О, х^ >

наименьшее значение целевой функции будет в точке О (0,0)

L . =30

20 = 0.

mm ^ ^ ' '^ ^ ^ •

Перемещая линию уровня параллельно самой себе в поло-

жительном направлении вектора с

нетрудно заметить, что точ-

кой выхода из области будет точка В. Из совместного решения

уравнений Xj-X2=

х^ + 2х^

=8,

координаты точки В будут

ЛО 7 .

(—,'—). Таким образом, наибольшее значение целевой функции

о 10 ^ 7 44

PaBH0L_=3 —+ 2.- = у.

2.3.

Найти минимальное

максимальное значение функции

L = Зху - х^ при ограничениях Xj > 0; х^ > 0; Xj - х^ + 2 > 0;

Xj -2x^-2 <0.

Решение. Построим допустимую область решений системы

неравенств, вектор с =(3,-1) и через начало координат прове-

дем линию уровня

Зх^

х^=

(рис. 24.13 )

Будем теперь перемещать линию уровня параллельно самой

себе в направлении, противоположном вектору с

•

Точкой вы-

хода линии уровня из области допустимых решений будет точка

М с координатами (О, 2). Таким образом, целевая функция L

примет минимальное значение в точке М, равное

Г =3-0-2 = -2.

Рис. 24.13

ПИНЕЙНОЕ И аИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

123

Перемещая линию уровня в положительном направлении

вектора с

нетрудно заметить, что она будет иметь непустое пе-

ресечение

допустимой областью решений, как долго бы мы ее

ни перемещали. Следовательно, целевая функция L на допусти-

мой области решений сверху

не

ограничена

может иметь сколь

угодно большое наперед заданное значение,

т.

е. максимума дан-

ной функции не существует.

2.4.

Найти минимальное

максимальное значение функции

L = л:у4- х^ + 2х^ при ограничениях Xj > 0; х^ - х^ > 0;

х^-

> 0; х^ - 3 < 0; Xj + 2х^ < 3; jc^ > 0.

Решение. Допустимая область решения системы неравенств

представляет призматическое тело (рис. 24.14 ).

Рис. 24J4

Построим вектор с =(1,1,2) и проведем перпендикулярно

ему, мысленно, через начало координат плоскость уровня

Xj+

Х2 +

2xj = 0. При перемещении плоскости уровня в направ-

лении, обратном вектору с точка F будет точкой выхода плос-

кости из области решений. Следовательно, целевая функция L в

точке F(0,1,0) принимает наименьшее значение

При перемещении плоскости уровня в положительном на-

правлении вектора с

нетрудно заметить, что плоскость уровня

124 Гпава 24

выйдет из многогранника решений

ABCDEFB

точках ребра CD,

Таким образом, на множестве точек ребра CD целевая функция

L принимает наиболынее

значение.

Чтобы убедиться

этом, под-

ставим координаты точек С (3,3,0) и £)

О,

3,—

в целевую фун-

кцию.

Тогда получим L =

3 + 3

+ 0 = 6 и L =

3H-2

—=

24.3.

Симплекс - метод

1°.

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

переменных и т независимых уравнений. Требуется найти min

функции L. Оптимальное решение, если оно существует, дости-

гается в одной из опорных точек, где по крайней мере к-п-т

переменных равны нулю. Выберем первые k переменных в

качестве свободных и выразим через них остальные т — ба-

зисных:

^k+2

^^k+2.{^\

'^^к+г.Л

'^••''^^k-\-2.k'^k

Pk+2*'

(1)

Пусть все свободные переменные равны нулю Xj = 0;

О' ••' Ч = о, тогда х,^,

=13,,,,

^k^2=Pk^2>

->К =Рп' Реше-

ние может быть допустимым или недопустимым. Решение до-

пустимо, если все J3y5.^.p

р,^,2>"-*

^п—неотрицательны. В этом

случае имеет место опорное решение. Чтобы проверить, явля-

ется ли оно оптимальным, выразим функцию L через свобод-

ные переменные

ПИНЕЙНОЕ И аИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ 125

Очевидно, что при х^ = х^ = ...= х^ =

функция L = /о

•

Если все 7р 72'

•••' Ук

положительны, то уменьшить L мы не мо-

жем, т.к. Ху, х^ и т. д. >

. То есть решение оптимальное.

Если есть 7 < О, т. е. отрицательное, то увеличивая х.

мы уменьшаем функцию L . Пусть, например, 7, отрицате-

лен, тогда имеет смысл увеличивать х^. Однако, увеличивать

Ху следует осторожно, так, чтобы не стали другие перемен-

ные х^^^ , х^^2 ' •••

^w отрицательными в формулах (I). Это

возможно, если коэффициенты при х^ отрицательны. Если ко-

эффициенты при Xj положительны, то увеличивая Xj функция

L не ограничена снизу и оптимального решения не существует.

Пусть при Xj коэффициент отрицателен и в /-ом уравнении

Ху

может стать отрицательным

Здесь Д >

О.

Если х^ =

О,

... , х^ =

О,

то увеличивать

Ху

мы

б.

можем до величины , иначе х, будет отрицательна.

В этом случае опорное решение примет вид

х^ = х^ = ...= х^, -

= 0; х^^О

Базисные переменные будут

•^У ' -^k+J ' ^к+2 ' ••• '-^/-7 '^/+7 ' -^п

Выражаем через новые свободные переменные базисные

и функцию L , приравниваем свободные переменные нулю и

ищем значение L . Если все коэффициенты при переменных

положительны, то нашли оптимум. Если нет, то процедура по-

вторяется.

2°.

Аналогично находится максимум функции L . Примем

k переменных за свободные и выразим оставшиеся перемен-

ные через них (1). Функция L примет вид (2). Пусть хотя бы

126 Г пава 24

ОДИН

коэффициент

у^

при переменной

х.

положительный. Тогда

увеличение

л:,

ведет к увеличению L и следует только следить

за тем, чтобы х^^^, ..., х^ не были отрицательны.

3°.

Если ограничительные условия заданы неравенства-

ми,

то их следует преобразовать в равенства путем введения

новых неотрицательных переменных. Например, в неравен-

стве

ДуХу

а2X2

+ ... + а^х^

b достаточно добавить к левой

части некоторую величину х^^^ >

и мы получим равенство

flyXy +

й^^+...+а^х^+х^^У

=Ь.

Если исходное неравенство имеет знак >

Z?,

то от левой ча-

сти следует отнять некоторую величину x^^j

Ограничительные условия могут задаваться и смешанным

образом, т. е. неравенствами и уравнениями, тогда указанным

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

3.1.

Найти максимум функции L = -х^+

х^

при ограничени-

ЯХ X

' X

Z,X

с 1, X у Z,X

* X г ^, Хт" DX

"i X с J.

Решение. При х^ = х^= О, L-

— опорное решение. По-

скольку коэффициент в L при

х^

положителен, то увеличиваем

х^ . Из второго уравнения следует, что увеличивать х^ можно

только до 2, а из третьего следует, что только до 3. Следова-

тельно, за разрешающее уравнение принимает второе. Разре-

шаем его относительно х^ и подставляем в первое, третье и фун-

кцию L. Тогда получим

л с ~~ ^~ л

-у

1^ ^^

' Х>,

~'~

"У

^л

"^ 1,

При х^ = х^= 0; L = 2 ,

Т.

е. ближе к максимуму. Поскольку

в L при переменной

х^

коэффициент положительный, то увели-

чиваем переменную х^.

ПИНЕЙНОЕ и аИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ 127

Из последнего уравнения увеличение

х^

возможно до

-г.

Под-

ставляя х^ в оставшиеся выражения, будем иметь

'5'5'5 ' 5'5'5

__3 _2 У2^ / _il_i -1

' 5 ' 5 ' 5 5 5 ' 5 '

Поскольку переменные х^ и Хз обе отрицательны, то наи-

большее значение L достигается при Х2=Хз=0 и равно

L =^.

""" 5

24*4* Табличный алгоритм отыскания

оптимального решения

1°.

Пусть равенства-ограничители имеют вид

(1)

«™1^1+«т2^2+-

аш,Л

=*m•

Bвeдeм базисные переменные

У1,У2,-;Ут ПО

числу уравне-

ний

системе (1)

г/2=^2-('«21^1+«22^2+- + «2«^«Л"

(2)

i/m =&m -r«ml^l + «m2^2 + - + «m^^J-

Линейную функцию представим в виде

Представим выражения (2), (3) в виде таблицы

128 Глава 24

Базисные

переменные

У^

Уг

Ут

Свободные

члены

Ьг

Ьт

Го

«И

«21

«ml

Г,

Хг

«12

0^22

«.2

...

Хп

«,«

«2«

«mn

г„

2°.

Перевод базисной переменной у. в разряд свободной х.

переменной

Ху

^/.

сводится к преобразованию коэффициентов

в таблице по схеме:

В таблице выделяется разрешающий элемент a-j и его

величина меняется на обратную

l/a^j.

Элементы разрешающей строки умножаются на Я.

Элементы разрешающего столбца умножаются на

берутся со знаком минус.

К остальным элементам прибавляется произведение эле-

ментов на старой разрешающей строке на элементы в новом

разрешающем столбце.

Таблица переписывается, заменяя Xj

<г^

у..

Процедура перевода базисной переменной у2 в разряд х^

переменной ^2 <-^

^/2,

где за разрешающий элемент принят «22»

показана в таблице

г.

Ут

ь.

^.-г^з

А.

«22

К-^ь^

«1.

«ml

«22

«21

«22

«m2«2l

«22

Уг

«22

__L.

«22

«т2

«22

...

^п

гу «12«2п

^\П «22

«2п

«22

^^тп «22

ПИНЕЙНОЕ и аИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ 1^

3°.

В каждой вершине ОДР ( в опорной вершине) п пере-

менных обрапдаются в ноль, т. е. jc^ = х^ = ...= х^ =

. Тогда

Если среди

/?.

нет отрицательных величин, то это опорное

решение. Если есть, то решение недопустимо и надо шаг за ша-

гом искать опорное решение или доказать, что решение

не

суще-

ствует, т. е. система уравнений ограничений несовместна

нера-

венствами

х^,...,

х^ > о,

j^;

,...,

у^^

Пусть одно из уравнений с отрицательным свободным чле-

ном. Ищем в этой строке отрицательный элемент Цу. Если тако-

вого нет

—

это значит, что система уравнений несовместна

не-

равенствами. Действительно, если отрицательных элементов нет,

то левая часть отрицательна всегда. Пусть отрицательный эле-

мент есть, тогда в качестве разрешающего столбца выбираем

столбец с этим элементом.

Далее рассмотрим все элементы столбца, имеющие оди-

наковый знак со свободным членом. В качестве разрешаю-

щего примем элемент, у которого наименьшее отношение со

свободным членом и воспользуемся алгоритмом преобразо-

вания коэффициентов. Если в столбце из свободных членов

остались отрицательные, то процесс преобразования следу-

ет повторить.

Отыскание оптимального решения, которое обращает в

минимум линейную функцию L, рассмотрим на примере.

4.1.

Найти опорное решение безотносительно к виду линей-

ной функции.

yj^\ -i-Xj-lx^-^x^))

-5-{-2xj-^ X2-Xj);

y^=2-(xj

X2);

l-(-X2

x^);

Решение. Составим таблицу