Лабораторная работа № 6 решения Тема: транспортных задач. Задание Реализация алгоритма 1…
- User
Лабораторная работа № 6 решения Тема: транспортных задач. Задание Реализация алгоритма 1 Разработать алгоритм решения и составить блок-схему основных процедур программы. 2 Разработать программу решения задачи. 3 Выполнить программу на ЭВМ. 4 Составить отчет о проделанной работе. Цель работы 1 Овладение практическими навыками решения транспортных задач разработки программы, реализующий решение данных задач. 2 Получение навыков по отладке программы. Контрольные задания Контрольные задания на выполнение лабораторной работы представлены в таблице 1. Имеются 3 пункта поставки однородного груза А1, А2, А3 и 5 пунктов потребления этого груза В1, В2, В3, В4, В5. На пунктах Аi (i = 1,2,3) груз находится соответственно в количествах а1, а2, а3 условных единиц. В пункты Вj (j = 1,2,3,4,5) требуется доставить соответственно bj единиц груза. Стоимость перевозки единицы груза (с учетом расстояний) из Аi в Вj определена матрицей С={cij}. Решить задачу методом северо-западного угла и найти такой план закрепления потребителей и поставщиков, чтобы общие затраты на перевозки были минимальны.
а1 = 200, а2 = 250, а3 = 160, b1 = 120, b2 = 120, b3= 100, b4= 210, b5= 60 С=21 13 16 15 12 7 9 10 9 21 20 12 16 15 1
с++
- Assistant
Для решения транспортной задачи методом северо-западного угла (СЗУ) мы можем следовать нескольким шагам. Ниже представлен алгоритм, который иллюстрирует этот метод, а также пример C++ кода.
1. Алгоритм решения с использованием метода северо-западного угла
Шаги алгоритма:
-
Инициализация:
- Определите матрицу затрат
C, массивыa(поставки) иb(потребления). - Создайте матрицу решений
X, гдеX[i][j]— количество груза из пункта поставкиAiв пункт потребленияBj.
- Определите матрицу затрат
-
Начальная установка:
- Начните с верхнего левого элемента матрицы
X, т.е. (0, 0). - Определите максимальное количество груза, которое можно отправить (minimum из
aiиbj). - Запишите это количество в
X[i][j], вычтите его изa[i]иb[j]. - Переместитесь либо вниз (если все
bjудовлетворены), либо вправо (если всеaiудовлетворены).
- Начните с верхнего левого элемента матрицы
-
Повторяйте:
- Повторяйте процесс до тех пор, пока все поставки и потребности не будут удовлетворены.
-
Расчет затрат:
- Подсчитайте общие затраты на основе матрицы
Cи решений из матрицыX.
- Подсчитайте общие затраты на основе матрицы
2. Блок-схема
Блок-схема может быть создана с использованием графических инструментов, но в текстовой форме можно описать:
+---------------------+ | Инициализация | | C, a, b, X | +---------------------+ | v +---------------------+ | Пока есть a[i] и b[j] | +---------------------+ | v +---------------------+ | Минимум (ai, bj) | +---------------------+ | v +---------------------+ | Обновление X[i][j]| | Обновление a и b | +---------------------+ | v +---------------------+ | Подсчет затрат | +---------------------+ | v +---------------------+ | Завершение | +---------------------+3. Программа на C++
#include <iostream> #include <vector> using namespace std; int main() { int a[] = {200, 250, 160}; // Запасы int b[] = {120, 120, 100, 210, 60}; // Потребности int C[3][5] = { {21, 13, 16, 15, 12}, {7, 9, 10, 9, 21}, {20, 12, 16, 15, 1} }; // Стоимость int x[3][5] = {0}; // Решение (план отгрузок) int i = 0, j = 0; while (i < 3 && j < 5) { int shipment = min(a[i], b[j]); x[i][j] = shipment; a[i] -= shipment; b[j] -= shipment; // Если вычерпали такой пункт, двигаем вниз или вправо if (a[i] == 0) i++; if (b[j] == 0) j++; } // Подсчет общих затрат int totalCost = 0; for (int k = 0; k < 3; k++) { for (int l = 0; l < 5; l++) { totalCost += x[k][l] * C[k][l]; } } // Вывод cout << "Решение транспортной задачи:\n"; for (int k = 0; k < 3; k++) { for (int l = 0; l < 5; l++) { cout << "X[" << k << "][" << l << "] = " << x[k][l] << endl; } } cout << "Общие затраты на перевозку: " << totalCost << endl; return 0; }4. Отчет о проделанной работе
В отчете нужно указать следующую информацию:
- Описание задачи и её значимости.
- Обоснование выбора метода (метод северо-западного угла) для решения задачи.
- Алгоритм решения, включая блок-схему.
- Описание программы (выбор языка, структура кода, введенные данные и вывод).
- Результаты выполнения программы с анализом полученных данных (например, полученные отгрузки и общие затраты).
- Выводы о выполненной работе (освоенные навыки, результаты тестирования и отладки, возможные улучшения).
Если у вас есть какие-либо другие вопросы или вам нужна дополнительная информация, не стесняйтесь спрашивать!
-