Файл: 5.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 19.03.2024

Просмотров: 89

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

Навчальний посібник для студентів вищих навчальних закладів

21

 

 

 

+ 20x2 = 10; x1 = 0, x2 = 40; x2 = 0, x1 = 80. Зростання цільової функції означає паралельне зміщення графіка функції вгору, доки остання крапка не вийде на границю багатокутника розв’язків.

x2

 

x2

Z

Z

x1 x1

0

Рис. 2. Необмежені багатокутники розв’язків задачі лінійного програмування

Ця точка відповідає перетину прямих.

x2

x1

0

Рис. 3. Багатокутник розв’язків несумісної системи обмежень задачі лінійного програмування

22 Дослідження операцій

x1

3,5x2

350;

 

l1

x

x

2

150;

 

l

2

1

 

 

 

 

 

x1 = 70, x2 = 80;

zmax(x) = 10x1 + 20x2 = 10 ∙ 70 + 20 ∙ 80 = 2300 грн.

Для знаходження мінімального значення цільової функції лінію рівняння потрібно зміщувати вниз, доки остання точка не вийде на границю багатокутника розв’язків – це l5, усі точки якої є розв’язком задачі – нескінченна множина рішень.

Урозглянутому випадку багатокутник розв’язків не тільки опуклий, а ще є і замкнутим. Можливі варіанти опуклого багатокутника розв’язків, який є необмеженим (рис. 2).

Упершому випадку можливо знайти максимальне значення цільової функції, а у другому – мінімальне значення. На рис. 3 наведений приклад багатокутника розв’язків несумісної системи обмежень – роз- в’язок задачі математичного програмування відсутній.

Геометричну інтерпретацію множини припустимих розв’язків задачі лінійного програмування та графічний метод її розв’язання з трьома невідомими змінними приведено у прикладі 7.

Приклад 7

Розглянемо задачу лінійного програмування у формі стандартної задачі. Знайдемо найбільше значення функції трьох невідомих змінних

z (x) = 3x1 – 6x2 + 2x3, z max;

при обмеженнях:

3x1 3x2 2x3 6; x1 4x2 8x3 8; x1 0; x2 0; x3 0.

Побудуємо область припустимих рішень системи лінійних нерівностей, прийнявши до уваги рівняння площин

3x1 + 3x2 + 3x3 = 6;

(1)

Навчальний посібник для студентів вищих навчальних закладів

 

 

 

 

23

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

x3

 

 

 

 

 

 

 

 

 

x3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

C

 

 

 

 

 

 

 

 

 

 

 

 

( )P (0; 0; 1).

 

 

 

 

 

 

( )N (0; 2; 0);

3

 

 

 

 

 

 

 

3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

( )C (0; 0; 3).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2

 

 

 

 

 

 

 

 

 

 

2

 

 

 

 

3x2 + 2x3 = 6

P

4x2 + 2x3 = 6

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

 

 

 

 

 

 

 

 

 

1

 

 

 

 

 

 

N

 

x2

 

 

 

 

 

 

N

 

x2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

 

 

 

 

1

 

2

 

3

 

 

 

 

1

 

2

 

3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 4. Слід площини (1)

 

 

 

 

Рис. 5. Слід площини (2)

8

7

6

5

4

3

2

1

0

x1

( )M (2; 0; 0).

x1 + 4x2 = 8

M

3x1 + 3x2 = 6

N

x2

Рис. 6. Сліди площин (1) та (2)

1 2 3

24

Дослідження операцій

x3

3 C

3x1 + 2x3 = 6

2

1 R

M

 

 

 

 

0

1

 

2

 

 

 

 

( )M(2; 0; 0); ( )R(16/11; 0; 9/11); ( )S(8; 0; 0).

x1 + 8x3 = 8

S

x1

3

 

4

 

5

 

6

 

7

 

8

Рис. 7. Сліди площин (1) та (2)

x1 + 4x2 + 8x3 = 8;

(2)

x1 = 0; x2 = 0; x3 = 0.

Побудуємо сліди перетину площини

3x1 3x2 2x3 6

з кожною із площин x1 = 0; потім x2 = 0, x3 = 0. Як x1 = 0, то рівняння (1) набуває вигляду

3x2 2x3 6

і у системі координат x2, x3 гранична пряма набуває вигляду (рис. 4). Відповідно рівняння (2) набуває вигляду

4x2 8x3 8

і гранична пряма у координатах x2 та x3 набуває вигляду (рис. 5). Аналогічно побудуємо сліди перетину площин (1) та (2) з площи-

ною x3 = 0; 3x1 + 3x2 = 6; x1 + 4x2 = 8 (рис. 6).

Побудуємо сліди перетину площин (1) та (2) з площиною x2 = 0; 3x1 + 2x3 = 6; x1 + 8x3 = 8 (рис. 7).

Знайдемо точку перетину R слідів площин (1) та (2) на координат-

Навчальний посібник для студентів вищих навчальних закладів

25

 

 

 

ній площині x10x3.

x3

 

 

 

 

3

 

 

C(0; 0; 3)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2

 

 

P(0; 0; 1)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Z (3; -6; 2)

 

1

 

 

 

 

N(0; 2; 0)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

R(16/11; 0; 9/11)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

x2

 

 

 

 

1

 

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2

 

 

 

1

 

 

2

 

 

 

 

 

 

 

 

 

3

 

M(2; 0; 0)

 

 

 

 

 

 

 

4

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5

 

 

 

 

 

 

 

 

 

 

 

 

6

 

 

 

 

 

 

 

 

 

 

 

 

 

 

7

 

 

 

 

 

 

 

 

 

 

 

 

 

 

8

 

 

 

Рис. 8. Область припустимих рішень:

 

 

 

 

S(8; 0; 0)

 

 

 

 

 

MN0PR

 

 

 

x1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

9

 

 

 

 

 

 

 

3x1

2x3 6;

x3

 

 

;

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

11

 

 

 

 

 

 

 

 

 

 

 

16

 

 

 

 

 

 

x 8x 8;

 

x

.

 

 

 

 

 

 

 

 

 

 

 

 

 

1

3

 

 

1

11

 

 

 

Смотрите также файлы