[ Симплекс метод рішення задачі лінійного програмування ]! | 48 | |||||||||
3 | 0 |
| 108 |
|
| 0 | 0 | - | 1 | 72 |
Δ j | 384 | 3 | -2 | 0 | 0 | 2 | 0 | |||
Zj | 384 | 12 | 8 | 0 | 0 | 2 | 0 |
Змінюється базис в позиції направляючої рядка. Базисним стає вектор, що відповідає направляючому стовпцю, т. е.
Стовпець стає базисним, тобто одиничним.
Нові значення в направляючої рядку отримуємо розподілом елементів цього рядка на направляючий елемент.
Інші елементи в небазисних шпальтах і в стовпці обчислюємо за правилом трикутника.
Вибираємо мінімальну негативну оцінку. Вона визначає направляючий стовпець.
Заповнюємо стовпець «θ»
За мінімальним значенням визначаємо напрямну рядок.
На перетині направляючої рядка і стовпця знаходиться направляючий елемент.
Заповнення другої таблиці здійснюється за аналогією з попередньою.
Таблиця 2.
0 | 9 | 10 | 16 | 0 | 0 | 0 | Відношення, θ | |||
i |
| Базис |
|
|
|
|
|
|
| |
1 | 10 |
| 8 | 1 | 1 | 0 |
| - | 0 | ______ |
2 | 16 |
| 20 |
| 0 | 1 | - |
| 0 | ______ |
3 | 0 |
| 96 |
| 0 | 0 |
| - | 1 | ______ |
Δ j | 400 | 5 | 0 | 0 |
|
| 0 | |||
Zj | 400 | 14 | 10 | 16 |
|
| 0 |
Так як немає негативних оцінок Δj, отже виконується ознака оптимальності і не вводилися штучні змінні, то отримано оптимальне рішення.
Відповідь:
Максимальне значення функції F max = 400 досягається в точці з координатами:
= 0
= 8
= 20
= 0
= 0
= 96
Завдання № 2 (Метод Літтла)
Знайти найкоротший шлях у графі, заданому графічно у вигляді креслення, методом Літтла.
З креслення запишемо матрицю відстаней. (Відстань від т.1 до т.2 одно:
, І т.д.)
1 | 2 | 3 | 4 | 5 | 6 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
1 | ∞ | 18,87
Припустимо що найкоротший шлях буде таким: т.1 → т.2 → т.3 → т.4 → т.5 → т.6 → т.1 і складе Рішення: Перший етап. Крок 1. Наведемо матрицю відстаней по рядках і стовпцях (У рядку віднімаємо з кожного елемента мінімальний, потім у стовпцях)
↓
↓
Крок 2. Визначимо оцінки нульових клітин:
Крок 3. Викреслюємо клітку з максимальною оцінкою. Включаємо дану клітку в шлях обходу. (5 - 6) Крок 4. Переписуємо матрицю відстаней, накладаючи заборону на одну з кліток для виключення передчасного замикання контуру (в клітку 6-5 ставимо ∞).
Далі повторюємо кроки 1 - 4, поки не дійдемо до однієї клітини. Другий етап. Крок 1. Наведемо матрицю відстаней по рядках і стовпцях.
↓
Крок 2. Визначимо оцінки нульових клітин:
Крок 3. Викреслюємо клітку з максимальною оцінкою. Включаємо дану клітку в шлях обходу. (1 - 2) Крок 4. Переписуємо матрицю відстаней, накладаючи заборону на одну з кліток для виключення передчасного замикання контуру (в клітку 2 - 1 ставимо ∞).
Третій етап. Крок 1. Наведемо матрицю відстаней по рядках і стовпцях.
↓
↓
Крок 2. Визначимо оцінки нульових клітин:
Крок 3. Викреслюємо клітку з максимальною оцінкою. Включаємо дану клітку в шлях обходу. (4 - 5) Крок 4. Переписуємо матрицю відстаней, накладаючи заборону на одну з кліток для виключення передчасного замикання контуру (в клітку 6 - 4 ставимо ∞).
Четвертий етап. Крок 1. Наведемо матрицю відстаней по рядках і стовпцях.
↓
Крок 2. Визначимо оцінки нульових клітин:
Крок 3. Викреслюємо клітку з максимальною оцінкою. Включаємо дану клітку в шлях обходу. (3 - 4) Крок 4. Переписуємо матрицю відстаней, накладаючи заборону на одну з кліток для виключення передчасного замикання контуру (в клітку 6 - 3 ставимо ∞).
П'ятий етап. Залишилися не задіяними зв'язку 2 - 3 і 6 - 1. У результаті отримуємо наступний ланцюжок: 1 → 2 → 3 → 4 → 5 → 6 → 1 Довжина шляху становить: L = 18, 87 +32,06 +31,76 +32,14 +22,14 +97,42 = 234,39 це і є найкоротший шлях. Будь ласка, не зберігайте тестовий текст. |