Елементи інформаційних технологій в математичному програмуванн
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.
Список використаних джерел
1. Бурий В.В., Шевченко І.В. Математичне програмування. -- К.: НАУ, 2007. -- 168с.
2. Єгоршин О.О., Малярець Л.М. Математичне програмування. -- Х.: ВД "ІНЖЕК", 2006. -- 383с.
3. Жильцов О.Б., Кулян В.Р., Юнькова О.О. Математичне програмування (з елементами інформаційних технологій) / Міжрегіональна академія управління персоналом / Олена Олександрівна Юнькова (ред.). -- К.: МАУП, 2006. -- 184с.
4. Зеленський К.Х. Математичне програмування. -- К.: Університет "Україна", 2007. -- 241c.
5. Івченко І.Ю. Математичне програмування. -- К.: Центр учбової літератури, 2007. -- 232с.
6. Лебідь М.Т., Синявіна Ю.В. Математичне програмування. -- Х., 2007. -- 72с.
