Елементи інформаційних технологій в математичному програмуванні
Контрольная работа - Математика и статистика
Другие контрольные работы по предмету Математика и статистика
Завдання 1
Розвязати графічним способом при умовах:
Розвязування
Зобразимо розвязок системи нерівностей та вектор F (1;2):
Максимум функції досягається в точці А:
Мінімум функції досягається в точці В:
Завдання 2
Розвязати транспортну задачу методом потенціалів.
Розвязування
Спочатку перевіримо задачу на замкненість:
.
Задача є замкненою.
Вихідна таблиця:
А/В10202540254 7 2 5 159 3 4 6 358 5 9 3 202 1 7 4
Складемо початковий план методом мінімального елементу:
А/В10202540254 7 2 5 25 159 3 4 6 10 5358 5 9 3 35202 1 7 4 20
Опорний план є виродженим, адже число зайнятих клітинок менше ніж m+n-1=8. Зробимо його невиродженим, розміщуючи базисні нулі в клітину з координатами (i,j)=(1,1) та (4,1). Вирішимо задачу методом потенціалів:
А/В10202540U254 7 2 5 00 25 159- 3 +4 6 510 5358 5 9 3 2 35202+ 1 -7 4 -2020 4321295
Сформуємо оціночну матрицю з елементів :
Оціночна матриця04040-5-3020500075
План не є оптимальним, адже є відємні елементи.
Переміщуємо по циклу вантаж величиною 10 одиниць, додаючи цю величину у клітинах зі знаком +, та віднімаючи її від клітин зі знаком - .
Маємо,
А/В10202540U254 -7 2 5 +00 25 159 3 +4 6- 0 10 5358 5 9 3 -3 35202 +1- 7 4 -21010 V4326245
Оціночна матриця040-15020751000070
План не є оптимальним, адже є відємні елементи.
Переміщуємо по циклу вантаж величиною 0 одиниць, додаючи цю величину у клітинах зі знаком +, та віднімаючи її від клітин зі знаком - .
Отримаємо,
А/В10202540U254 7 2 5 0 250159 3 4 6 1 10 5358 5 9 3 -2 35202 1 7 4 -11010 V3225245Оціночна матриця1500501075900060
Як бачимо усі . Адже отриманий план є оптимальним.
При цьому загальна вартість перевезень складає 245 і є мінімальною.
Завдання 3
Розвязати задачу ЛП симплекс-методом:
Розвязування
Запишемо в канонічному виді:
Вирішимо задачу симплекс методом.
БазисБПx 1x 2x 3x 4x 5x4613-310x54-21101ИС03-2-100Обрано ключовий елемент (1,2) БазисБПx 1x 2x 3x 4x 5x221/31-11/30x52-7/302-1/31ИС411/30-32/30 Обрано ключовий елемент (2,3)БазисБПx 1x 2x 3x 4x 5x23-5/6101/61/2x31-7/601-1/61/2ИС71/6001/63/2
Отримано оптимальний план x* = (0, 3, 1). За нього fmin = (x*) = -7.
Список використаних джерел
- Бурий В.В., Шевченко І.В. Математичне програмування. К.: НАУ, 2007. 168с.
- Єгоршин О.О., Малярець Л.М. Математичне програмування. Х.: ВД "ІНЖЕК", 2006. 383с.
- Жильцов О.Б., Кулян В.Р., Юнькова О.О. Математичне програмування (з елементами інформаційних технологій) / Міжрегіональна академія управління персоналом / Олена Олександрівна Юнькова (ред.). К.: МАУП, 2006. 184с.
- Зеленський К.Х. Математичне програмування. К.: Університет "Україна", 2007. 241c.
- Івченко І.Ю. Математичне програмування. К.: Центр учбової літератури, 2007. 232с.
- Лебідь М.Т., Синявіна Ю.В. Математичне програмування. Х., 2007. 72с.