Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Лабораторна 4
Інформація про навчальний заклад
ВУЗ:
Вінницькій національний технічний університет
Інститут:
Інститут комп’ютерних наук та інформаційних технологій
Факультет:
ФІТКІ
Кафедра:
компютерні науки
Інформація про роботу
Рік:
2019
Тип роботи:
Лабораторна робота
Предмет:
ммдо
Група:
КН 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);
}
14.06.2020 11:06-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора