Завдання 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 /> /> /> 25 /> /> 15 9 - 3 + 4 /> 6 />
5 /> 10 /> /> 5 /> 35 8 /> 5 /> 9 /> 3 /> 2
/> /> /> /> 35 /> 20 2 + 1 - 7 /> 4 /> -2
/> 20 /> /> /> 4 3 2 1 295 /> />
Сформуємо оціночну матрицю з елементів />:Оціночна матриця 4 4
-5 -3 2 5 7 5
План не є оптимальним, адже є від’ємні елементи.
Переміщуємо по циклу вантаж величиною 10 одиниць, додаючи
цювеличину у клітинах зі знаком «+», та віднімаючи її від клітин зі
знаком «- ».
Маємо,А/В 10 20 25 40 U /> /> 25 4 - 7 /> 2 /> 5 +
/> /> 25 /> /> 15 9 /> 3 + 4 /> 6 - /> />
10 /> 5 /> 35 8 /> 5 /> 9 /> 3 /> -3 /> />
/> /> 35 /> 20 2 + 1 - 7 /> 4 /> -2 /> 10 10
/> /> /> V 4 3 2 6 245 /> /> Оціночна матриця 4 -1 5
2 7 5 10 7
План не є оптимальним, адже є від’ємні елементи.
Переміщуємо по циклу вантаж величиною 0 одиниць, додаючи цювеличину
у клітинах зі знаком «+», та віднімаючи її від клітин зі знаком «-
».
Отримаємо,А/В 10 20 25 40 U /> /> 25 4 /> 7 /> 2 />
5 /> /> /> /> 25 /> 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
/> 5 1
/> 7 5 9
/> 6
/> /> /> /> /> /> /> /> /> />
/> /> /> />
Як бачимо усі />. Адже отриманий план єоптимальним.
При цьому загальна вартість перевезень складає 245 і
ємінімальною.
Завдання 3
Розв'язати задачу ЛП симплекс-методом:
/>
Розв'язування
Запишемо в канонічному виді:
/>
Вирішимо задачу симплекс методом.Базис БП x 1 x 2 x 3 x 4 x 5 x4 6
1 3 -3 1 x5 4 -2 1 1 1 ИС 3 -2 -1 Обрано ключовий елемент (1,2)
Базис БП x 1 x 2 x 3 x 4 x 5 x2 2 1/3 1 -1 1/3 x5 2 -7/3 2 -1/3 1
ИС 4 11/3 -3 2/3 Обрано ключовий елемент (2,3) Базис БП x 1 x 2 x 3
x 4 x 5 x2 3 -5/6 1 1/6 1/2 x3 1 -7/6 1 -1/6 1/2 ИС 7 1/6 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с.