Елементи інформаційних технологій в математичному програмуванні

6



Завдання 1



Розв'язати графічним способом при умовах:







Розв'язування

Зобразимо розв’язок системи нерівностей та вектор F (1;2):







Максимум функції досягається в точці А:







Мінімум функції досягається в точці В:






Завдання 2



Розв'язати транспортну задачу методом потенціалів. 

Розв'язування

Спочатку перевіримо задачу на замкненість:



.



Задача є замкненою.



Вихідна таблиця:

А/В

10

20

25

40











25

4

 

7

 

2

 

5

 







 

 

15

9

 

3

 

4

 

6

 



 

 





35

8

 

5

 

9

 

3

 



 

 



 

20

2

 

1

 

7

 

4

 



 



 





 

 

 

 



Складемо початковий план методом мінімального елементу:

А/В

10

20

25

40











25

4

 

7

 

2

 

5

 



 

 

25

 

15

9

 

3

 

4

 

6

 



10

 

 

5

35

8

 

5

 

9

 

3

 



 

 

 

35

20

2

 

1

 

7

 

4

 



 

20

 

 



Опорний план є виродженим, адже число зайнятих клітинок менше ніж m+n-1=8. Зробимо його невиродженим, розміщуючи базисні нулі в клітину з координатами (i,j)=(1,1) та (4,1). Вирішимо задачу методом потенціалів:



А/В

10

20

25

40

U













25

4

 

7

 

2

 

5

 

0



0

 

25

 



15

9

- 

3

 +

4

 

6

 

5



10

 

 

5



35

8

 

5

 

9

 

3

 

2



 

 

 

35



20

2

+ 

1

 -

7

 

4

 

-2



0

20

 

 





4

3

2

1

295















Сформуємо оціночну матрицю з елементів :



Оціночна матриця

0

4

0

4

0

-5

-3

0

2

0

5

0

0

0

7

5



План не є оптимальним, адже є від’ємні елементи.

Переміщуємо по циклу вантаж величиною 10 одиниць, додаючи цю величину у клітинах зі знаком «+», та віднімаючи її від клітин зі знаком «- ».


Маємо,

А/В

10

20

25

40

U













25

4

 -

7

 

2

 

5

 +

0



0

 

25

 



15

9

 

3

 +

4

 

6

- 

0



 

10

 

5



35

8

 

5

 

9

 

3

 

-3



 

 

 

35



20

2

 +

1

- 

7

 

4

 

-2



10

10

 

 



V

4

3

2

6

245















Оціночна матриця

0

4

0

-1

5

0

2

0

7

5

10

0

0

0

7

0



План не є оптимальним, адже є від’ємні елементи.

Переміщуємо по циклу вантаж величиною 0 одиниць, додаючи цю величину у клітинах зі знаком «+», та віднімаючи її від клітин зі знаком «- ».



Отримаємо,

А/В

10

20

25

40

U













25

4

 

7

 

2

 

5

 

0



 

 

25

0



15

9

 

3

 

4

 

6

 

1



 

10

 

5



35

8

 

5

 

9

 

3

 

-2



 

 

 

35



20

2

 

1

 

7

 

4

 

-1



10

10

 

 



V

3

2

2

5

245














Оціночна матриця

1

5

0

0

5

0

1

0

7

5

9

0

0

0

6

0



Як бачимо усі . Адже отриманий план є оптимальним. 

При цьому загальна вартість перевезень складає 245 і є мінімальною.



Завдання 3



Розв'язати задачу ЛП симплекс-методом:







Розв'язування

Запишемо в канонічному виді:







Вирішимо задачу симплекс методом.

Базис

БП

x 1

x 2

x 3

x 4

x 5

x4

6

1

3

-3

1

0

x5

4

-2

1

1

0

1

ИС

0

3

-2

-1

0

0

Обрано ключовий елемент (1,2) 

Базис

БП

x 1

x 2

x 3

x 4

x 5

x2

2

1/3

1

-1

1/3

0

x5

2

-7/3

0

2

-1/3

1

ИС

4

11/3

0

-3

2/3

0

 Обрано ключовий елемент (2,3)

Базис

БП

x 1

x 2

x 3

x 4

x 5

x2

3

-5/6

1

0

1/6

1/2

x3

1

-7/6

0

1

-1/6

1/2

ИС

7

1/6

0

0

1/6

3/2



Отримано оптимальний план x* = (0, 3, 1). За нього fmin = (x*) = -7.




Список використаних джерел



	Бурий В.В., Шевченко І.В. Математичне програмування. — К.: НАУ, 2007. — 168с.

	Єгоршин О.О., Малярець Л.М. Математичне програмування. — Х.: ВД "ІНЖЕК", 2006. — 383с.

	Жильцов О.Б., Кулян В.Р., Юнькова О.О. Математичне програмування (з елементами інформаційних технологій) / Міжрегіональна академія управління персоналом / Олена Олександрівна Юнькова (ред.). — К.: МАУП, 2006. — 184с.

	Зеленський К.Х. Математичне програмування. — К.: Університет "Україна", 2007. — 241c. 

	Івченко І.Ю. Математичне програмування. — К.: Центр учбової літератури, 2007. — 232с. 

	Лебідь М.Т., Синявіна Ю.В. Математичне програмування. — Х., 2007. — 72с.