Симплекс-метод та транспортна задача

РОЗРАХУНКОВО-ГРАФІЧНА РОБОТА з дисципліни “Дослідження операцій” Дані варіанту 1) Розрахувати задачу графічно і симплекс-методом. F(x) = -7x1 + x2  max 9x1 + 4x2  110 11x1 - 3x2  24 2x1 - 7x2  15 xj  0. 2) Побудувати математичну модель і розрахувати транспортну задачу.

На 3 бази А1, А2, А3 потрапив однорідний вантаж у кількості, відповідно рівній 70, 50 і 80 од. Цей вантаж потрібно перевезти в 3 пункти призначення В1, В2, В3 відповідно у кількості 90, 50 і 60 од. Тарифи перевезень, одиниць вантажу кожного з пунктів відправлення та призначення виставляються студентом самостійно. 1) Вирахуємо задачу графічним методом: F(x) = -7x1 + x2  max 9x1 + 4x2  110 11x1

- 3x2  24 2x1 - 7x2  15 xj  0. Побудуємо на графіку обмеження: 9x1 + 4x2  110 11x1 - 3x2  24 2x1 - 7x2  15 xj  0 Знайдемо область допустимих рішень (ОДР). Рішення задачі повинно лежати на границях ОДР. Тепер підставимо точки (вершини) ОДР у функцію

і знайдемо максимальне значення: F(0;-8) = -7*0 - 8 = -8 F(1,9;-1,6) = -7*1,9 - 1,6 = -14,9 F(0;-2,1) = -7*0 – 2,1 = -2,1 Таким чином, ми бачимо, що значення функції у цих точках від’ємні, отже, задача не має розв’язку. Симплекс-метод F(x) = -7x1 + x2  max 9x1 + 4x2  110 11x1 - 3x2  24 2x1 - 7x2  15 xj  0.

Приведемо систему обмежень до розширеного вигляду: 9x1 + 4x2 + x3= 110 11x1 - 3x2 + x4 = 24 -2x1 + 7x2 + x5= -15 xj  0 Симплекс-таблиця: Базисні елементи F XX5 Рядок коеф. цільової ф-ї Коеф. при базисних елементах 0 -7 1 0 0 0 X3 0 110 9 4 1 0 0 X4 0 24 11 -3 0 1 0 X5 0 -15 -2 7 0 0 1 Δ

Рядок оцінок 0 7 -1 0 0 0 :7(3)(-4) Дивлячись на рядок оцінок, ми вибираємо направляючий стовпець, тобто той, в якому Δ мінімальна. В цьому стовпці вибираємо найбільший невід’ємний елемент. Якщо таких невід’ємних чисел декілька, то ми ділимо їх на вільні члени і дивимось, який з них найбільший. А потім потрібно рядок, де був знайдений найбільший невід’ємний елемент додати до

інших рядків так, щоб у цьому направляючому стовпці отримати нулі. Дивимось, що отримали в результаті: Базисні елементи F X5 Рядок коеф. цільової ф-ї Коеф. при базисних невідомих 0 -7 1 0 0 0 X3 0 118,4 10,12 0 1 0 -0,56 X4 0 17,7 10,16 0 0 1 0,42 X2 1 -2,1 -0,28 1 0 0 0,14 Δ Рядок оцінок -2,1 6,72 0 0 0 0,14

Як бачимо, і симплекс-метод теж показав, що задача не має розв’язку, так як значення функції від’ємне. 2.Транспортна задача На 3 бази А1, А2, А3 потрапив однорідний вантаж у кількості, відповідно рівній 70, 50 і 80 од. Цей вантаж потрібно перевезти в 3 пункти призначення В1, В2, В3 відповідно у кількості 90, 50 і 60 од. Тарифи перевезень, одиниць вантажу кожного з пунктів відправлення та призначення виставляються студентом самостійно.

Дані у вигляді таблиці: В1 В2 В3 Запаси А1 6 2 1 70 А2 4 8 2 50 А80 Заявки 60 Математична модель транспортної задачі буде мати вигляд: F=i=1m j=1n cijхij Де Хij – це кількість товару, який перевозиться із Аi в Вj, Сij – ціна перевезення. Задачу потрібно перевірити, чи є вона збалансованою. i=1m хij = bj (j=1, n ) = 90 + 50 + 60 = 200 j=1n хij = ai (i=1, m ) = 70 + 50

+80 = 200 де аi - запаси продукції, bj – заявки на продукцію. Ми бачимо, що задача є збалансованою. Складемо початковий план за методом Фогеля. Для цього визначимо штрафи по всіх рядках і стовпцях (різниця між двома мінімальними цінами рядка або стовпця). Потім вибираємо найбільший штраф і в рядку або стовпчику з максимальним штрафом вибираємо найменшу ціну

і заповнюємо клітину максимально можливим перевезенням. При цьому вибуває з розгляду або постачальник або споживач. Заповнивши всі перевезення, треба перевірити, щоб кількість базових клітин була m + n – 1 (кількість постачальників + кількість споживачів - 1). В1 В2 В3 Запаси А1 6 — 2 50 1 20 70 1 1 5 - А2 4 10 8 — 2 40 50 2 2 2 2

А3 1 80 5 — 4 — 80 3 - - - Заявки 90 50 60 3 3 1 2 6 1 2 - 1 4 - 2 Підрахуємо базові клітини: m + n –1 = 3 + 3 – 1 = 5 Все вірно. Значення функції, яку ми мінімізували: F = 10*4 + 80*1 + 50*2 + 20*1 + 40*2 = 320 Тепер перевіримо, чи оптимальний план за допомогою методу потенціалів. Потенціали – це числа Ui і Vj, що приписуються кожному постачальнику

і кожному споживачу. Потенціали розставляються за базисними клітинами так, щоб виконувалась рівність: Ui + Vj = Cij Один з потенціалів можна вибрати довільно. Найчастіше покладають U1 =0. Для всіх порожніх клітин має виконуватись нерівність Ui + Vj ≤ Cij Якщо ця нерівність не виконується для порожніх клітин, то ці клітини називаються “поганими” і вони вимагають перевезення. В1 В2 В3 Запаси аi

А1 6 — 2 50 1 20 70 0 А2 4 10 8 — 2 40 50 1 А3 1 80 5 — 4 — 80 -2 Заявки 90 50 60 βj 1 Поганих клітин немає, отже, початковий план і буде оптимальним. Fмін = 320 Список використаної літератури: 1. Конспект