Математические методи у створенні транспортного процесса

1. Завдання № 2…3.

2. Завдання № 3…7.

3.

Список литературы

…12.

ЗАВДАННЯ 2 Варіант — 18.

1. Умова задачи.

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

[pic].

2. Побудова математичної модели.

Нехай X ij — кількість деталей, відправлених зі складу і до магазину j, а З ij — вартість перевезення однієї деталі зі складу і до магазину j. Вочевидь, що X ij > 0 і З ij > 0.

З огляду на обмежень до можливості поставок товарів зі складу і попит у магазинах величина X ij має відповідати наступним условиям:

X 11 + X 12 + X 13 + X 14 = 25 X 21 + X 22 + X 23 + X 24 = 45 (1) X 31 + X 32 + X 33 + X 34 = 30.

X 11 + X 21 + X 31 = 30 X 12 + X 22 + X 32 = 10 (2) X 13 + X 23 + X 33 = 30 X 14 + X 24 + X 34 = 30.

Общая вартість перевезень равна:

Z = З ij X ij = 21* X 11 + 36* X 12 + 28* X 13 + 21* X 14 + 25* X 21 +.

35* X 22 + 26* X 23 + 25* X 24 + 23* X 31 + 21* X 32 + 27* X 33 + 21* X 34,.

тобто. Z = З ij X ij. (3).

Необхідно визначити такі неотрицательные значення змінних X ij, які задовольняють обмеженням (1) і (2) і звертають в мінімум цільову функцію Z (3). У такій постановці завдання є транспортної завданням лінійного программирования.

Необхідною і достатня умова разрешимости транспортної завдання є умова баланса:

P.S і = M j.

Где, P. S і = X ij — cуммарное кількість деталей на складах;

M j = X ij — сумарне кількість деталей, необхідну в магазинах.

В даної завданню P. S і = M j = 100,.

Следовательно, завдання з балансом.

3. Рішення задачи.

Решение завдання і двох етапів: 1. Визначення припустимого рішення. 2. Визначення оптимального рішення шляхом послідовного поліпшення припустимого рішення методом потенциалов.

Визначення припустимого рішення методом найменшої стоимости.

За підсумками вихідної таблиці побудуємо допоміжну таблицю (в верхньому правом розі кожної клітини будемо записувати вартості перевезення). Введём в таблицю допоміжну рядок і стовпець для записи остатков.

[pic].

Определим найменшу вартість перевезення: X 14 = min (25, 30) = 25 X 32 = min (30, 10) = 10 X 34 = min (20, 5) = 5 X 31 = min (15, 15) = 15 X 21 = min (45, 15) = 15 X 23 = min (30, 30) = 30.

Стоимость перевезення Z = 25*21 + 25*15 + 30*26 + 15*23 + 10*21 + 5*21 = 2340 ум. ед.

Послідовне поліпшення припустимого рішення методом потенциалов.

Виберемо вспомагательные перемінні U і і V j, обертаючі в нулі коефіцієнти при базисних змінних, то есть.

З ij — U і - V j = 0 (4) Такі перемінні називаються потенціалами. Виконаємо такі дії: 1. Всім X ij > 0 (т. е. всім зайнятих клітин) складемо потенційні уравнения:

З 14 — U 1 — V 4 = 0 21 — U 1 — V 4 = 0.

З 21 — U 2 — V 1 = 0 25 — U 2 — V 1 = 0.

З 23 — U 2 — V 3 = 0 26 — U 2 — V 3 = 0 (5).

З 31 — U 3 — V 1 = 0 23 — U 3 — V 1 = 0.

З 32 — U 3 — V 2 = 0 21 — U 3 — V 2 = 0.

З 34 — U 3 — V 4 = 0 21 — U 3 — V 4 = 0.

Для визначення m + n потенціалів необхідно, щоб було m + n — 1 рівнянь (де m — число рядків, n — число шпальт). Тоді одного з потенціалів можна привласнити будь-яке значення, наприклад однакову нулю, а значення інших потенціалів отримати, вирішуючи систему рівнянь (5).

Для даного завдання m + n — 1 = 6 і кількість зайнятих клітин одно 6.

U 1 = -2.

U 2 = 0.

U 3 = -2.

V 1 = 25 V 2 = 23 V 3 = 26 V 4 = 23.

2. Вирішимо систему рівнянь 4, присвоївши значення, однакову нулю, найчастіше яке невідомому індексу: U 2 = 0, тогда.

V 1 = 25; U 1 = -2;

V 2 = 23; U 2 = 0;

V 3 = 26; U 3 = -2.

V 4 = 23; Занесём дані в таблицю вище. 3. Всім небазисных змінних, т. е. для X ij = 0 (для порожніх клітин), визначимо невязки:

G ij = З ij — P. S ij, де P. S ij = U і + V j.

G 11 = З 11 — U 1 — V 1; G 11 = 27 — (-2) — 25 = 4;

G 12 = З 12 — U 1 — V 2; G 12 = 36 — (-2) — 23 = 15;

G 13 = З 13 — U 1 — V 3; G 13 = 28 — (-2) — 26 = 4; (6).

G 22 = З 22 — U 2 — V 2; G 22 =35 — 0 — 23 = 12;

G 24 = З 24 — U 2 — V 4; G 24 = 25 — 0 — 23 = 2;

G 33 = З 33 — U 3 — V 3; G 33 = 27 — (-2) — 26 = 3.

Негативних невязок немає, отже знайдений план (див. таблицю вище) оптимальний і значення цільової функції є минимальным.

Отже, мінімальна вартість перевезень Z дорівнює 2340 ум. од. і характеризується обсягах перевозок:

X 14 = 25, X 21 = 15, X 23 = 30, X 31 = 15, X 32 = 10, X 34 = 5.

ЗАВДАННЯ 3.

1. Умова задачи.

Фірма повинна налагодити перевезення продуктів із бази на 7 магазинів. Мережа доріг, котра зв’язує базу і магазини між собою, і навіть довжини ділянок дороги між кожної парою сусідніх пунктів представлені на рисунке.

Визначити найкоротші шляху від бази до кожного з магазинов.

Х 4.

Х 1 Х 7.

Х 5.

Х 3.

Х 2.

Х 8.

Х 6.

2. Побудова математичної модели.

Нехай G (A, U) — граф, де A — безліч вершин, що означають об'єкти (базу — вершина 1, а магазини — вершини 2, 3, 4, 5, 6, 7, 8), U — безліч ребер, що означають можливий зв’язок між двома вершинами. Кожному ребру поставлено відповідність певна кількість L ij (і, j = 1, 2,…, 8 — вагу ребра (відстань між двома вершинами).

Завдання відшукання найкоротшого шляхи виходу з вершини і в вершину j полягає в мінімізації цільової функции:

Y = L і X ij ,.

где X ij = 1, якщо шлях проходить з вершини і в вершину j,.

X ij = 0, інакше. Ця функція визначає довжину між заданої початкової ідеї та кінцевої вершинами.

У цьому їх необхідно виконувати такі условия:

(X ij — X ji) = 0, і = 2, 3,…, m — 1.

(т. е. для будь-який вершини і, виключаючи початкову і кінцеву, число шляхів, які входять у цю вершину, одно чису шляхів, які виходять із неё);

(X 1j — X j1) = 1.

(т. е. до останньої вершину входить однією шлях більше, ніж выходит);

(X mj — X jm) = 1.

(т. е. кількість шляхів, які входять у вершину 1, перевищує на одиницю число шляхів, які виходять із неё).

Необхідно визначити такі значення X ij, рівні 0 чи 1, які доставлять мінімум цільової функції Y за дотримання умов, заданих ограничениями.

Це завдання є саме про найкоротшому шляху й може быть решена индексно — матричним методом.

3. Рішення задачи.

Складемо матрицю терезів графа, що був малюнку. Эле;

мент L ij цієї матриці дорівнює вазі ребра, якщо вершини і і j пов’язані між собою руба, та безмежжя — інакше. Діагональні елементи також рівні нескінченності, оскільки граф без петель. Для наочності в матрицю терезів нескінченності записувати думати, залишаючи відповідні їм клітини пустыми.

Додамо до складеної в такий спосіб матриці нульову рядок и нулевой стовпець, у яких будемо записувати відповідно індекси шпальт і рядків U і і V j (U і - відстань від вершини 1 до вершини і, V j — відстань від вершини 1 до вершини j). Тоді матриця терезів матиме вид, поданий у таблиці ниже.

[pic].

Для обчислення індексів виконаємо такі дії: 1. Поклавши U 1 = V 1 = 0/ 2. Значення всіх заповнених клітин першого рядка чудово перенесём на відповідні місця індексів шпальт V j і рядків U і, т. е. V 2 = 8, V 3 = 10, V 4 = 10, V 7 = 12, U 2 = V 2 = 8, U 3 = V 3 = 10, U 4 = V 4 = 10,.

U 7 = V 7 = 12 (дивіться таблицю ниже).

[pic].

3. Визначимо відсутні індекси V j. У прикладі це індекси V 5, V 6 і V 8. І тому у кожному стовпці, соответсвующем невідомому індексу V j, переглянемо заповнені клітини, і обчислимо відсутні індекси за такою формулою V j = U і + L ij, для них відомі індекси U i.

Для шпальти, відповідного індексу V 5, цими елементами будуть L 4, 5 = 16 і L 7, 5 = 25. Значення U 4 і U 7 відомі: U 4 = 10, U 7 = 12. Следовательно,.

V 5 = min (U 4 + L 4, 5 = 10 + 16 = 26; U 7 + L 7, 5 = 12 + 25 = 37) = 26.

Для шпальти, відповідного індексу V 6, ними будуть L 2, 6 = 7, L 3, 6 = 17, L 7, 6 = 18. Значення індексів U 2, U 3, U 7 відомі: U 2 = 8, U 3 = 10, U 7 = 12. Следовательно,.

V 6 = min (U 2 + L 2, 6 = 8 + 7 = 15; U 3 + L 3, 6 = 10 + 17 = 27;

U 7 + L 7, 6 = 12 + 18 = 30) = 15.

Для шпальти, відповідного індексу V 8, ними будуть L 5, 8 = 17, L 6, 8 = 13, L 7, 8 = 19. Значення індексів U 5, U 6, U 7 відомі: U 5 = 26, U 6 = 15, U 7 = 12. Следовательно,.

V 8 = min (U 5 + L 5, 8 = 26 + 17 = 43; U 6 + L 6, 8 = 15 + 13 = 28;

U 7 + L 7, 8 = 12 + 19 = 31) = 28.

Запишем в рядок V і (дивіться таблицю нижче). 4. Усі індекси знайдено. Перевіримо отримане рішення на оптимальність, т. е. виконання умови L ij >= V j — U і кожної заповненою клітини матрицы.

[pic].

Всім заповнених клітин умова L ij >= V j — U і дотримується. Отримане рішення є оптимальним. Отже, мінімальними відстанями від вершини 1 до решти будут:

V 2 = 8, V 3 = 10, V 4 = 10, V 5 = 26, V 6 = 15, V 7 = 12, V 8 = 28.

Визначимо найкоротшого шляху від вершини 1 до вершини 5. І тому в стовпці 5 знайдемо елемент, значення одно різниці індексів шпальти і рядки L ij = V j — U і :

L 4, 5 = V 5 — U 4 = 26 — 10.

L 4, 5 — остання ланка шляху й, відповідно, вершина 4 — предпоследняя.

І далі, в стовпці 4 определим:

L 1, 4 = V 4 — U 1 = 10 — 0 = 10.

L 1, 4 — перше ланка шляху, оскільки вершина 1 є початковій фиксированной.

Отже, маємо мінімальний шлях від вершини 1 до вершини 5, проходить через вершини 1, 4, 5, довжина якого дорівнює 26.

———————————- [pic].

[pic].

[pic].

[pic].

[pic].

[pic].

[pic].

[pic].

[pic].

[pic].

[pic].

[pic].

[pic].

[pic].

[pic].