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

Контрольная работа - Математика и статистика

Другие контрольные работы по предмету Математика и статистика

Завдання 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.

 

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

 

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