Лабораторна 4. Лабораторна робота з ммдо. Робота № 531797

Лабораторна 4

Інформація про навчальний заклад

ВУЗ:

Вінницькій національний технічний університет

Інститут:

Інститут комп’ютерних наук та інформаційних технологій

Факультет:

ФІТКІ

Кафедра:

компютерні науки

Інформація про роботу

Рік:

2020

Тип роботи:

Лабораторна робота

Предмет:

ммдо

Група:

КН 217

Варіант:

1 13

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Міністерство освіти, науки, молоді та спорту Вінницький національний технічний університет Кафедра комп’ютерних наук Лабораторна робота №4 З дисципліни «Математичні методи дослідження операцій» Тема: Розробка алгоритму та програми для розв’язування спеціальних задач лінійного програмування (транспортна задача) Мета: набути практичних навичок побудови опорного плану транспортної задачі різними методами та приведення його до оптимального методом потенціалів, а також програмної реалізації розв’язання транспортної задачі (ТЗ). Хід роботи Відповідно до варіанту 1.13 практично розв’язати транспортну задачу: / побудувати опорний план ТЗ трьома методами (методом північно-західного кута, методом мінімальної вартості, методом апроксимації Фогеля); обрати опорний план, значення Fi якого є найменше; перевірити побудований опорний план на оптимальність методом потенціалів; якщо опорний план не є оптимальним, то за допомогою методу потенціалів будуємо оптимальний план; якщо опорний план є оптимальним, то беремо відмінний від нього опорний план і застосовуючи метод потенціалів приводимо його до оптимального. Розробити алгоритм та програму для розв’язання ТЗ. Було розроблено програму для реалізації методу подвійної позначки. Блок-схема алгоритму програми наведена далі: Рисунок 1 Блок-схема алгоритму розв’язування ТЗ методом подвійної позначки. Для тестування програми були введені дані з практичного завдання, результати виконання програми наведені далі: / Рисунок 2 – Результати тестування програми / Рисунок 3 – Результати тестування програми / Рисунок 4 – Результати тестування програми Висновок: У ході виконання даної роботи, були набуті практичні навички побудови опорного плану транспортної задачі різними методами та приведення його до оптимального методом потенціалів, а також програмної реалізації розв’язання транспортної задачі (ТЗ). Було практично розв’язано транспортну задачу відповідного варіанту, розроблена програма для вирішення закритої транспортної задачі методом мінімального елемента. При тестуванні програми використовувалась задача з практичного завдання – відповіді зійшлись, отже програма працює правильно. Додаток 1 – Інструкція користувача Запустити програму RTZMP.exe; / Ввести к-ть постачальників і потреб., і натиснути ОК / Далі заповнити необхідні поля. / Вибрати метод і натиснути «Расчет» Додаток 2 – Лістинг програми static void DoubleMarkMethod(int[,] tarif, int[] amount, int[] needs, int providers, int customers) { Console.WriteLine("Метод подвійної позначки:\n"); //Вивід транспортної таблиці: Console.WriteLine("\nтранспортна таблиця"); Console.WriteLine("prov / cust | B1 | B2 | B3 | amount |"); for(int i = 0; i < providers; i++) { Console.Write("A{0, -11:N0}|", i+1); for(int j = 0; j < customers; j++) { Console.Write("{0, -4:N0}|", tarif[i, j]); } Console.Write("{0, -8:N0}|\n", amount[i]); } Console.Write("needs |"); for(int i = 0; i < customers; i++) { Console.Write("{0, -4:N0}|", needs[i]); } // int[,] markTable = new int[providers, customers]; int[] needsSatisfy = new int[customers]; Array.Copy(needs, needsSatisfy, needs.Length); int[] amountSatisfy = new int[providers]; Array.Copy(amount, amountSatisfy, amount.Length); int[,] result = new int[providers, customers]; int needsSum = 0; for(int j = 0; j < customers; j++) { needsSum += needsSatisfy[j]; } while(needsSum != 0) { for (int i = 0; i < providers; i++) for (int j = 0; j < customers; j++) if (markTable[i, j] != -1) markTable[i, j] = 0; int minIndex = 0; for (int i = 0; i < providers; i++) for (int j = 0; j < customers; j++) if (markTable[i, j] != -1) minIndex = j; for (int i = 0; i < providers; i++) { for (int j = 0; j < customers; j++) { if (tarif[i, minIndex] >= tarif[i, j] && markTable[i, j] != - { minIndex = j; } } for (int j = 0; j < customers; j++) { if (tarif[i, minIndex] == tarif[i, j] && markTable[i, j] != { markTable[i, j] += 1; } } } minIndex = 0; for (int i = 0; i < providers; i++) for (int j = 0; j < customers; j++) if (markTable[i, j] != -1) minIndex = i; for (int j = 0; j < customers; j++) { for (int i = 0; i < providers; i++) { if (tarif[minIndex, j] >= tarif[i, j] && markTable[i, j] != -1) { minIndex = i; } } } Console.WriteLine("\nтаблиця позначок"); Console.WriteLine("\n | B1 | B2 | B3 |"); for (int i = 0; i < providers; i++) { for (int j = 0; j < customers; j++) { if (markTable[i, j] == 2) { if (amountSatisfy[i] != 0 && needsSatisfy[j] != 0) { if (amountSatisfy[i] >= needsSatisfy[j]) { amountSatisfy[i] -= needsSatisfy[j]; result[i, j] += needsSatisfy[j]; needsSatisfy[j] -= needsSatisfy[j]; } else { needsSatisfy[j] -= amountSatisfy[i]; result[i, j] += amountSatisfy[i]; amountSatisfy[i] -= amountSatisfy[i]; } markTable[i, j] = -1; if (amountSatisfy[i] == 0) { for (int q = 0; q < customers; q++) markTable[i, q] = -1; } if (needsSatisfy[j] == 0) { for (int q = 0; q < providers; q++) markTable[q, j] = -1; } } } } } Console.WriteLine("\nрезультуюча таблиця"); Console.WriteLine("\n | B1 | B2 | B3 |"); for (int i = 0; i < providers; i++) { Console.Write("A{0, -4}|", i + 1); for (int j = 0; j < customers; j++) { Console.Write("{0, -4:N0}|", result[i, j]); } Console.WriteLine(); } //перерахунок суми потреб споживачів needsSum = 0; for (int j = 0; j < customers; j++) { needsSum += needsSatisfy[j]; } } // int L = 0; for (int i = 0; i < providers; i++) { for (int j = 0; j < customers; j++) { if (result[i, j] != 0) { L += tarif[i, j] * result[i, j]; } } } Console.WriteLine("\nпочатковий L = {0}", L); //перевіримо на оптимальність план знайдений методом пн-зх кута Console.WriteLine("Перевірка та приведення до оптимального, план знайдений методом пн-зх кута"); int[,] NorthWestPlan = { {50, 0, 0 }, {30, 15, 20 }, {0, 0, 25 } }; PotentialMethod(tarif, NorthWestPlan, providers, customers); }

Лабораторна робота ммдо

Kazbek2013

14.06.2020 11:53

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись