Контрольні роботи з математичних дисциплін
українська русский  
Авторизація
 
Логін
Пароль
Приклади задач
Вища математика
Теорія ймовірностей
Матпрограмування
Економетрія
Теорія статистики
ЕMM і М, ДО
Вибране
Готові роботи
Рейтинг задач
Задачі on-line
Довідка
Ціни та оплата
Інші ресурси
Мапа сайту
Контакти
Є запитання?
Курси валют
 
Курсы валют на PROext     
Задача про оптимальне призначення угорським методом
Знайдено 90 розв'язаних задач даної теми. Детальніше ...

Умова задачі
Розв'язати задачу про оптимальне призначення угорським методом:

$ C = \left( \begin{array}{rrrr} 1&4&6&3\\ 9&7&10&9\\ 4&5&11&7\\ 8&7&8&5 \end{array} \right) $

Розв'язання

Дана задача є окремим випадком транспортної задачі, математична постановка якої буде наступною:
визначити мінімальне значення функції:

$ F = \sum\limits_{i=1}^m \sum\limits_{j=1}^n c_{ij} x_{ij} $

при умовах:

$ \sum\limits_{i=1}^n x_{ij} = 1 (j=1..n),\; \sum\limits_{j=1}^n x_{ij} = 1 (i=1..n)$,

xij > 0, xij є Z.

Отже, задача лінійного програмування запишеться так:

F = x11 + 4x12 + 6x13 + 3x14 + 9x21 + 7x22 + 10x23 + 9x24 + 4x31 + 5x32 + 11x33 + 7x34 + 8x41 + 7x42 + 8x43 + 5x44 → min

при умовах:

x11 + x12 + x13 + x14 = 1,
x21 + x22 + x23 + x24 = 1,
x31 + x32 + x33 + x34 = 1,
x41 + x42 + x43 + x44 = 1,
x11 + x21 + x31 + x41 = 1,
x12 + x22 + x32 + x42 = 1,
x13 + x23 + x33 + x43 = 1,
x14 + x24 + x34 + x44 = 1,

xij > 0, xij є Z.

Маємо початкову таблицю.

C0 = 1 4 6 3
9 7 10 9
4 5 11 7
8 7 8 5

Застосуємо угорський метод розв'язання задачі про оптимальне призначення. Для цього виконаємо попереднє перетворення матриці, яке полягає у зменшенні елементів рядків та стовпців матриці на мінімальні значення відповідних рядків та стовпців.

1 4 6 3 1
9 7 10 9 7
4 5 11 7 4
8 7 8 5 5

Мінімальні значення рядків записані в останній колонці таблиці. Віднявши ці значення (їх сума рівна 17) від відповідних елементів рядків, одержимо наступну матрицю:

0 3 5 2
2 0 3 2
0 1 7 3
3 2 3 0
0 0 3 0

Мінімальні значення стовпців записані в останньому рядку таблиці. Віднявши ці значення (їх сума рівна 3) від відповідних елементів стовпців, одержимо наступну матрицю:

C1 = 0 3 2 2
2 0 0 2
0 1 4 3
3 2 0 0

В результаті цих перетворень кожен рядок і стовпець містить принаймні один нуль.
Далі позначаємо нулі матриці. Проглядаємо послідовно рядки. Якщо в рядку міститься один непозначений нуль, то підкреслюємо його, а всі нулі цього стовпця закреслюємо. Аналогічно переглядаємо стовпці.


Зареєструйтесь і Ви зможете переглянути задачу повністю!


Знайдено 90 розв'язаних задач даної теми. Детальніше ...

Переглядів: 73

  
  
Нові роботи

01.01.17
2500
Економетрія
КНЕУ

09.12.16
2488
Теорія ймовірностей та математична статистика
ЗНТУ

23.11.16
2475
Вища математика
УнУкр

05.10.16
2436
Теорія ймовірностей та математична статистика
РДГУ

03.11.16
2433
Економетрія
ОНЕУ

08.04.16
2393
Теорія статистики
ІПКСЗ

05.03.16
2380
Вища математика
НГА

22.02.16
2375
Математичне програмування
ОНЕУ

21.01.16
2360
Теорія ймовірностей та математична статистика
АОСА

Design:
ru.AnVisionWebTemplates.com

©2005-16 MatComUA

 
Головна || Реєстрація || Замовлення || Реферати || Запитання || Відгуки || Мапа || Про нас UKR | RUS