Елементи інформаційних технологій в математичному програмуванні Завдання 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с.