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

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

110 г пава 24

ТО

искомая полуплоскость лежит выше прямой

a^pc-^a^^2'^^i~^^

если второе, то ниже этой прямой. Если

а^2

О,

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

приводится к виду Xj>b или

Xj<

Ьи полуплоскость лежит справа

или слева от прямой Xj = b. Полуплоскость, которая является

решением данного неравенства, можно определить

другим спо-

собом. А именно, достаточно подставить в неравенство коор-

динаты одной какой-либо точки,

не

лежаш;ей на граничной пря-

мой. Если неравенство удовлетворяется, то полуплоскость, в

которой лежит данная точка, является искомой, а если не удов-

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

Область решений системы неравенств (1) представляет пе-

ресечение конечного числа полуплоскостей, образующих выпук-

лую многоугольную область S. Область решений может быть ог-

раниченной, неограниченной

даже

пустой.

последнем случае

система неравенств (1) противоречива. Если неравенства, вхо-

дяпдие в систему (1), не имеют с областью S общих точек, то их

можно исключить как лишние. Если неравенство представлено

прямой, имеющей одну общую точку с областью S, причем, вся

область лежит по одну сторону от этой прямой, то такая точка, а

соответственно, и прямая, называется

опорной^

а решение в этой

точке -

опорным

решением.

2°.

Область решения Fсистемы линейных неравенств

тре-

мя переменными

a^^x^+a^j^^

+^23-^3

+^2 -^'*

(2)

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

которые разбивается

все

пространство соответствующими плос-

костями.

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

111

1.1. Найти полуплоскость, определяемую неравенством

а) Зх^ + 4x2 - 12 > 0; Зх^ - Зх^ > 0.

Решение, а) Заменяя знак неравенства на знак равенства,

запишем уравнение прямой 3x^+4x^-12=0 и представим ее на

рис.

24.1.

Рис. 24.1

Исходное неравенство приведем к виду ^2

—Xj

отку-

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

мой Зх^ +

Ах2

-12 = 0.

б) Уравнение прямой (рис. 24.2) примет вид Зху - Зх^ = 0.

Рис. 24.2

Из решения неравенства относительно переменной х^ на-

ходим

Х2 <

— X,. Следовательно, искомая полуплоскость распо-

ложена ниже прямой Зху -

Зх^

= 0.

112

Гпава 24

1.2. Найти область решений системы неравенств:

а)х^-х^+

>0;

х^-6х^-2<

0; 4х^ + 5х^ - 20 < 0;

б)

х^

- 2х^ + 4 <

2х^ -

х^

- 2 > 0; 4х^ +

Зх^

- 12 < 0;

в) х^ - Зх^ + 6 > 0; х^ + х^ - 4 > 0; 5х^ + 2х^ - 10 > 0; х^ > 0;

г) х^ > 0;

Ху

- х^ + 2 > 0; 5х^ + х^ - 5 < 0; х^ - х^ - 4 > 0;

д) 4х^ + 5х^ - 20 < 0; 16х^ - 5х^ > 0; х^ - 4х^ < 0; х^ > 1;

4х^ + 5х^ + 2 > 0.

Решение, а) Заменяя знаки неравенств на

знаки

равенств,

запи-

шем

уравнения

прямых:

Ху-х^+1=0; Ху-6х2-2=

0;4ху

+5x^-20=0.

Построим эти прямые

(рис.

24.3 ).

Рис. 24.3

Исходные равенства приведем к

виду:

х^

х^;

х^ >

6х^

^2 - ""T-^i

"""^ •

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

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

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

ниченный соответствующими прямыми.

б) Заменяя знаки неравенств на знаки равенств, запишем

уравнения прямых:

Х;-2х^ + 4 = 0; 2x^^x^-2 = 0; 4x^ + 3x^-12 = 0.

Построим эти прямые

(рис.

24.4).

ПИНЕЙНОЕ

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

113

Рис,

24.4

Исходные неравенства приведем

виду:

х^^

—^i

+ 4

;

Х2

2ху

Х2

< —

Xj + 4 .

Обозначим штриховкой полуплоскос-

ти,

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

равенств. Из рассмотрения

рис.

24.4 видно, что общих точек для

всех трех полуплоскостей

нет.

Следовательно, область решений

пустая и исходная система неравенств несовместна.

в) Заменяя знаки неравенств на знаки равенств, строим пря-

мые:

Xj -

3x2

+ 6 = 0; Xj +

Х2

- 4 =

5xj +

2x^

-10 = 0;

X2 =0(рис. 24.5

-ъ

^^^<^^^

^..rf^^^^^^^^

^^^^//У/////У//////^

-V,

Рис,

24,5

Неравенства запишем

виде:

< -^+2;

д:^ >

-Ху

+ 4;

^2 >

—JC,

л:^

> 0.

Обозначая штриховку, из

рис.

24.5 видно.

114

Гпава 24

ЧТО

областью решения системы неравенств является неограни-

ченная фигура.

г) Приведем исходные равенства к виду: х^ >

х^<

Ху

+ 2;

х^

-5ху + 5;

х^ < Ху

- 4 и построим область решений каждого

неравенства

(рис.

24.6).

Рис. 24.6

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

видно,

что

не

существует ни одной

точки, координаты которой удовлетворяли

бы всем

неравенствам.

Следовательно, данная система неравенств

не

имеет решений.

д) Приведем исходные равенства к виду:

4 16 1 4 2

X. <—х+4- X. <—X,; X. >—X,; X, >1; X. >—х

2 5 1 ,2 5 м 2 4 Р 1 > 2 5^5

и построим область решения каждого неравенства

(рис.

24.7).

Рис. 24.7

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

115

Из рассмотренного рисунка видно, что исходным неравен-

ствам соответствует множество точек плоскости, образующих

треугольник ABC, Неравенства 4ху+ Зх^^ 2>

и \Ьх^ - 5х^ > О

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

прямую, не имеющую с треугольником ABC общих точек, а

второе имеет одну общую точку с треугольником, т. е. являет-

ся опорным.

1.3. Найти область решений системы неравенств:

а)х^

>0;х^<1;

х^ >0; х^ ч-х^ + х^-З <0; б)х^+x^ +;Сз-6<0;

Ъх^

+ 2х^ - 12 < 0; Зх^ + х^ - 6 > 0; х^ >

О,

х^ > 0.

Решение, а) Заменяя знаки неравенств на знаки равенств,

строим систему плоскостей (рис. 24.8 ).

Рис. 24.8

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

следовательно, область решений исходной системы представляет

множество точек, заключенных

усеченном тетраэдре

(рис.

24.8 ).

б) Заменяя знаки неравенств на знаки равенств, строим сис-

тему плоскостей (рис. 24.9).

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

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

ограниченное сверху плоскостью

х^

+ х^ = 6. Область реше-

ний исходной системы неравенств представляет множество то-

чек, заключенных внутри показанного на

рис.

24.9 тела.

116

Гпава 24

Рис. 24,9

24.2.

Основная задача линейного

программирования и геометрическая

реализация ее в случае двух и трех

переменных

1°.

Основная задача линейного программирования заклю-

чается

отыскании наибольшего или наименьшего значений ли-

нейной функции L при наличии линейных ограничений (линей-

ных равенств или неравенств).

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

х^, ... , х^.Требуется найти такие неотрицательные значения

этих переменных, которые удовлетворяли бы совместной

системе т линейных неравенств с п переменными

t Ап1 1 т2 2 тп п т'

а линейная (целевая функция)

(1)

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

L =

CjXj+c^x^-^

... +

с^х^

(2)

принимала бы наибольшее (наименьшее) значение.

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

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

ляет оптимальный план (2). Любая же другая совокупность пе-

ременных

Ху >

О,

х^

О,..., х^>0, удовлетворяющая системе (1),

называется допустимым решением,

2°.

Рассмотрим решение основной задачи линейного про-

граммирования геометрическим методом. Пусть дано

ajjXj + aj^x, < bj;

Требуется среди множества точек из области решений со-

вместной системы неравенств найти

такие,

координаты которых

придают целевой функции наибольшее (наименьшее) значение.

Функция L принимает во всех точках прямой

CjXj

+ с-^2 ~

а, перпендикулярной вектору 0(0^X2)-, выходящему из начала

координат, одно и то же значение а, где а — некоторый пара-

метр.

Присваивая

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

ных прямых, называемых линиями уровня функции L. Если пря-

мую

CjXj

с>рс2 =

а перемещать параллельно самой себе в поло-

жительном направлении вектора с , то линейная функция L бу-

дет возрастать, если перемещать в противоположном направле-

нии, то L будет

убывать.

Пересечение области решений

линией

уровня присваивает линейной функции L некоторое фиксирован-

ное

значение.

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

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

точке

выхода из области решений (рис.

24.10 ) функция L принимает наибольшее значение среди мно-

жества значений L, принимаемых на многоугольнике решений.

118

гпава 24

При движении

обратном направлении

точке А функция L при-

нимает наименьшее значение. Если линия уровня совпадает со

стороной многоугольника, то имеется множество точек, в кото-

рых функция L принимает наибольшее (наименьшее) значение.

Рис. 24.10

3°.

В случае трех переменных линейная функция L =

J Xj-^C2

х^+

с^

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

перпендикулярной вектору с(с^,с^,с^), Наибольшее и наимень-

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

входа плоскости СуХу+С2Х^+ CjX^ -а при движении в положи-

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

многогранник решений, опре-

деляемый системой неравенств

^m7^7+^m2^2+^mi^i^*m^

Если плоскость уровня совпадает

гранью или ребром мно-

гогранника, то имеется множество точек, в которых целевая

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

4°.

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

больше числа уравнений

m,T.Q.n-m

= 2. Пусть это будут Xj и

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

х^. Поскольку Xj,

Х2

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

то они называются

свободными

переменными.

Остальные т пе-

ременных, которые могут быть выражены через свободные, на-

зываются базисными:

Х^ 41 1 42 2 РА*

х,=а^Л+а^,х,+р^.

По осям Oxj, 0X2 будем откладывать переменные х^, х^,

которые больше

нуля.

Остальные переменные должны быть не-

отрицательными: х^ >

О,

х^ >

О,

... , х^ > 0.

Представим хотя бы первое условие геометрически

х^

= а^^х^+а^2^2'^ Рз-^ • Приравниваем его нулю

«31X1 +0^32-^2 "^

А ~ ^

•

Это уравнение прямой х^ =

. Аналогич-

ным образом строятся остальные прямые х^ =

, ... , х^ =

Часть плоскости

ОхуХ^,

принадлежащая одновременно всем по-

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

Выразим теперь функцию L = СуХ^+с^х^^ ... + с^х^ через

свободные переменные, тогда L = /о + 7i^i +

72-^2 ?

^Д^ 7о — ^^^'

бодный член. Введем функцию L'

L-yQ. Очевидно, что L' и

L имеют один и тот же экстремум, отличающийся на постоянное

число

7о •

Пусть /jXj +

72^2

~ а -уравнение

прямой.

Возьмем век-

тор с(у^.

Л перпендикулярный прямой а, и будем перемещать

прямую параллельно самой себе в направлении вектора с

При

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

принимает min значение, при выходе max.

5°.

Если

А2

- m =

то число свободных переменных равно 3,

остальные т переменных — базисные. Задача решается анало-

гичным образом, только в пространстве.