Задача про призначення.

Задача про призначення у загальному вигляді формулюється так:

Нехай є n робіт і n працівників, які можуть призначатися на ці роботи. Відома ефективність c_ij виконання кожним і-тим спеціалістом кожної j-ої роботи. Кожний спеціаліст може виконувати будь-яку роботу, але тільки одну. Необхідно знайти такий розподіл спеціалістів на роботи, щоб сумарна ефективність виконання всіх робіт була максимальною.

Для того, щоб скласти економіко-математичну модель задачі про призначення вводяться булеві змінні , які можуть приймати тільки два значення 0 або 1

Задача про призначення може розв’язуватися за допомогою методу потенціалів так як і транспортна задача. Але так як задача про призначення є задачею на максимум, то критерій оптимальності змінить знак на протилежний. Тобто розподіл спеціалістів на роботи буде оптимальним, якщо оцінки всіх незаповнених клітинок будуть невідємними . Задача про призначення в порівнянні з транспортною задачею буде мати такі відмінності:

• Буде виродженою, так як заповнення клітин можуть приймати значення 0 або 1;

• За циклом будуть передаватися тільки 0 та 1.

Приклад.

Розподілити чотирьох робітників за чотирма видами обладнання так, щоб загальна продуктивність праці була максимальною. Дані відносно продуктивності праці кожного робітника наведено у таблиці 1.

Таблиця 1.

Початковий розподіл можна виконувати довільним способом. Оптимальний розподіл призначень має вигляд

.

2. Содержание

   • Предмет математичного моделювання.
   • Моделювання в економіці.
   • 3. Класификація економіко – математичних моделей. Формальна класіфикація моделей.
   • 4. Задачі планування та організації виробництва.
   • 4.1. Задача про максимальну рентабельність підприємства.
   • 4.2. Задача про завантаження обладнання.
   • Питання для самоконтролю.
   • Тема 1. Предмет, методи і завдання дисципліни. Класифікація задач. Лекція 2
   • Задачі математичного програмування.
   • 2. Класифікація методів математичного програмування.
   • 3. Модель міжгалузевого балансу „Витрати - випуск”.
   • Коефіціети прямих та побічних витрат.
   • Питання для самоконтролю.
   • Тема 2.Загальна задача лінійного програмування та деякі з методів її розв’язування Лекція 3 Тема лекції: Основні теореми та властивості задач лінійного програмування (лп).
   • 1. Загальна форма задачі лінійного програмування (лп).
   • 2. Форми запису загальної задачі лп.
   • 3. Основні теореми та властивості задачі лп.
   • Питання для самоконтролю.
   • Тема 2.Загальна задача лінійного програмування та деякі зметодів її розв’язування Лекція 4 Тема лекції: Графічний метод розв’язування задач лп.
   • 2. Графічний метод розв’язування задач лп з
   • 3. Приклади розв’язування задач лп графічним методом.
   • Питання для самоконтролю.
   • Тема 2. Загальна задача лінійного програмування та деякі з методів її розв’язання Лекція 5 Тема лекції: Розв’язання задач лп симплекс-методом.
   • 1. Симплекс-метод із стандартним базисом.
   • 2. Теоретичні основи симплекс-метода.
   • 3. Поняття виродженності задач лп.
   • Тема 2. Загальна задача лінійного програмування та деякі з методів її розв’язування Лекція 6 Тема лекції: Розв’язання задач лп симплекс-методом (продовження)
   • 4. Правило уникнення зациклювання при застосуванні симплекс-методу.
   • 5. Метод штучної базиси розв’язування задач лп.
   • 6. Приклад вирішення задачі лп методом штучної бази.
   • Питання для самоконтролю.
   • Тема 3. Транспортна задача. Лекція 7 Тема лекції: Транспортна задача
   • 1 Економічна та математична моделі транспортної задачі.
   • 2 Основні теореми транспортної задачі.
   • 3. Метод північно-західного кута (діагональний.)
   • Тема 3. Транспортна задача. Лекція 8 Тема лекції: Транспортна задача (продовження)
   • 5. Метод потенціалів.
   • 6. Приклад вирішення транспортної задачі.
   • 7. Ускладнені задачі транспортного типу.
   • Тема 3. Транспортна задача. Лекція 9 Тема лекції: Транспортна задача (продовження)
   • Задача про призначення.
   • Розподільчи задачі загального типу.
   • Модель розподільчої задачі
   • Етапи розв’язання розподільчої задачі
   • Приклад вирішення задачі типу тз.
   • Питання для самоконтролю.
   • Тема 4. Теорія двоїстості та аналіз лінійних моделей оптимізаційних задач. Лекція 10. Тема лекції: Двоїста задача лінійного програмування
   • 1 Математичні моделі двоїстих задач.
   • 3 Взаємозв’язок розв’язків прямої та двоїстої задач.
   • Питання для самоконтролю.
   • Тема 5. Цілочислові та параметричні задачі лінійного програмування
   • Тема лекції: Узагальнення задачі лінійного програмування.
   • Задачі цілочислового програмування.
   • 2. Метод Гоморі.
   • 3. Параметричне лінійне програмування.
   • Питання для самоконтролю.
   • Тема 6. Елементи теорії ігор
   • Тема лекції: Матричні ігри
   • 1. Постановка задач теорії парних ігор з нульовою сумою.
   • Задачі з сідловою точкою. Задачі в чистих стратегіях.
   • Ігри в мішаних стратегіях. Основна теорема теорії ігор.
   • Тема 6. Елементи теорії ігор
   • Тема лекції: Матричні ігри (продовження)
   • 4. Графічний метод розв’язання теорії ігор.
   • 5. Зведення задач теорії ігор до задач лп.
   • Зведення задачі лп до матричної гри.
   • Питання для самоконтролю.
   • Тема 7. Нелінійні оптимізаційні моделі економічних систем
   • Тема лекції: Задача дробово-лінійного програмування
   • Постановка задачі дробово-лінійного програмування.
   • 2. Приведення задачі дробово-лінійного програмування до задачі лінійного програмування.
   • 3. Розв’янання задач дробово-лінійного програмування.
   • 4. Графічне розв’язання задачі дробово-лінійного програмування.
   • Питання для самоконтролю.
   • Тема 7. Нелінійні оптимізаційні моделі економічних систем.
   • Тема лекції: Задачі нелінійного програмування
   • 1. Класичні методи розв’язання задач нелінійного програмування.
   • 2. Метод множників Лагранжа.
   • 3. Задачі опуклого програмування.
   • Задачі опуклого програмування.
   • Питання для самоконтролю.
   • Тема 7. Нелінійні оптимізаційні моделі економічних систем.
   • Тема лекції: Основні поняття теорії варіаційного числення
   • Поняття про функціонал.
   • 2. Екстремум функціоналу.
   • 3. Класичні задачі варіаційного числення.
   • 4. Варіація функції та приріст функціоналу.
   • 5. Перша та друга варіації функціоналу.
   • Питання для самоконтролю.