ОТЧЕТ
По выполнению лабораторной работы
РЕШЕНИЕ ЗАДАЧ
ТРАНСПОРТНОГО ТИПА
Выполнила: студент группы М-21
Алымова Е.Ю.
Преподаватель: Калиниченко Е.Ф.
Вариант 27
Г. Коломна
Г.
Транспортная модель с транзитом.
.
Рассмотрено решение задачи, заданной следующей транспортной сетью:
Все пункты - транзитные. Задача - несбалансированная: запасы равны 300+900+800=2000, а спрос равен: 800+300+700=1800. Как видим спрос ниже запасов. Буфер для транзитных перевозок составляет В = 1800. Для приведения задачи к задаче закрытого типа, вводится фиктивный пункт потребления с объемом потребностей равным 200 ед. Прямые маршруты из фиктивного пункта производства разрешены только в пункты потребления с удельными транспортными расходами, равными штрафам за не вывезенный товар. Естественно, что фиктивный пункт производства не может быть транзитным. Таким образом, в данной задаче имеется 8 пунктов производства и 9 пунктов потребления. Схема сбалансированной задачи представлена на рисунке:
В данной задаче 8 транзитных пунктов, которые включаются в число начальных и конечных, и 1 конечный фиктивный пункт. Поэтому при решении задачи с помощью программы будем считать, что имеется 8 исходных и 9 конечных пунктов. У всех транзитных пунктов увеличиваем объемы запасов и потребностей на величину буфера. Для запрещенных маршрутов используется значение удельных транспортных расходов сij = 500, которое в данной задаче представляет из себя «машинную бесконечность». Удельные транспортные расходы для маршрутов из i-го исходного пункта в i-ый конечный пункт равны 0, так как реального движения при этом не происходит.
Лист Расчет после решения задачи имеет вид.
| ТРАНСПОРТНАЯ ЗАДАЧА | |||||||||
| Исходные данные | |||||||||
| № | Название параметра | Значение | |||||||
| Число исходных пунктов | |||||||||
| Число конечных пунктов | |||||||||
| Число этапов моделирования | |||||||||
| Объемы запасов | |||||||||
| № | |||||||||
| a | 2100,00 | 2700,00 | 2600,00 | 1800,00 | 1800,00 | 1800,00 | 1800,00 | 1800,00 | |
| Сумма запасов | 16400,00 | ||||||||
| Объемы потребностей | |||||||||
| № | |||||||||
| b | 1800,00 | 1800,00 | 1800,00 | 1800,00 | 1800,00 | 2600,00 | 2100,00 | 2500,00 | 200,00 |
| Сумма потребностей | 16400,00 | ||||||||
| Матрица удельных расходов | |||||||||
| КП1 | КП2 | КП3 | КП4 | КП5 | КП6 | КП7 | КП8 | КП9 | |
| НП 1 | 0,00 | 10,00 | 500,00 | 30,00 | 500,00 | 500,00 | 500,00 | 500,00 | 70,00 |
| НП 2 | 10,00 | 0,00 | 20,00 | 40,00 | 50,00 | 500,00 | 500,00 | 500,00 | 100,00 |
| НП 3 | 500,00 | 20,00 | 0,00 | 40,00 | 30,00 | 500,00 | 500,00 | 500,00 | 50,00 |
| НП 4 | 30,00 | 40,00 | 40,00 | 0,00 | 10,00 | 20,00 | 60,00 | 500,00 | 500,00 |
| НП 5 | 500,00 | 50,00 | 30,00 | 10,00 | 0,00 | 500,00 | 50,00 | 30,00 | 500,00 |
| НП 6 | 500,00 | 500,00 | 500,00 | 20,00 | 500,00 | 0,00 | 10,00 | 500,00 | 500,00 |
| НП 7 | 500,00 | 500,00 | 500,00 | 60,00 | 50,00 | 10,00 | 0,00 | 10,00 | 500,00 |
| НП 8 | 500,00 | 500,00 | 500,00 | 500,00 | 30,00 | 500,00 | 10,00 | 0,00 | 500,00 |
| Таблица оптимальных перевозок | |||||||||
| КП 1 | КП 2 | КП 3 | КП 4 | КП 5 | КП 6 | КП 7 | КП 8 | КП 9 | |
| НП 1 | 900,00 | 0,00 | 0,00 | 1200,00 | 0,00 | 0,00 | 0,00 | 0,00 | 0,00 |
| НП 2 | 900,00 | 1800,00 | 0,00 | 0,00 | 0,00 | 0,00 | 0,00 | 0,00 | 0,00 |
| НП 3 | 0,00 | 0,00 | 1800,00 | 0,00 | 600,00 | 0,00 | 0,00 | 0,00 | 200,00 |
| НП 4 | 0,00 | 0,00 | 0,00 | 600,00 | 0,00 | 1200,00 | 0,00 | 0,00 | 0,00 |
| НП 5 | 0,00 | 0,00 | 0,00 | 0,00 | 1200,00 | 0,00 | 0,00 | 600,00 | 0,00 |
| НП 6 | 0,00 | 0,00 | 0,00 | 0,00 | 0,00 | 1400,00 | 400,00 | 0,00 | 0,00 |
| НП 7 | 0,00 | 0,00 | 0,00 | 0,00 | 0,00 | 0,00 | 1700,00 | 100,00 | 0,00 |
| НП 8 | 0,00 | 0,00 | 0,00 | 0,00 | 0,00 | 0,00 | 0,00 | 1800,00 | 0,00 |
| Транспортные расходы | 120000,00 |
В таблице реализован оптимальный план перевозок с минимальными транспортными затратами. Значение целевой функции для оптимального опорного плана z =120000.
Диагональные элементы таблицы получены в результате использования буфера и не дают информацию об окончательном решении. Недиагональные элементы соответствуют реальным объемам перевозок. Оптимальное решение задачи может быть представлено в графическом виде.
| |||||
| |||||
| |||||
Так как введен фиктивный пункт потребления, на практике это означает, что на третьем пункте производства осталось 200 единиц груза. Потребности всех потребителей удовлетворены полностью.
Задача о назначениях.
Требуется распределить 6 работ по 5 станкам. 
- затраты выполнения i -ой работы на j -том станке. Матрица, в которой задаются стоимости выполнения работ, называется матрицей стоимостей Матрица стоимостей имеет следующий вид:
Надо распределить работы по станкам так, чтобы затраты на выполнение всей работы были минимальны. Можно рассматривать эту задачу как транспортную, где работы интерпретируются как исходные пункты, а станки - конечные. При этом все 
и 
равны 1. Если на i -ом станке работу j выполнить нельзя, то стоимость задается равной большому числу 500.
Чтобы решить задачу о назначении методом транспортной задачи, она должна быть сбалансированной. Для задачи о назначении это означает, что число работ должно быть равно числу станков. Заданная задача не сбалансированная. - один рабочий будет простаивать. Вводим фиктивный станок, работа которого соответствует простою рабочего. Пусть штрафы за простой заданы в таблице:
| № | |||||
| с5j |
Лист Расчет после решения задачи имеет вид.
| ТРАНСПОРТНАЯ ЗАДАЧА | ||||||
| Исходные данные | ||||||
| № | Название параметра | Значение | ||||
| Число исходных пунктов | ||||||
| Число конечных пунктов | ||||||
| Число этапов моделирования | ||||||
| Объемы запасов | ||||||
| № | ||||||
| a | 1,00 | 1,00 | 1,00 | 1,00 | 1,00 | 1,00 |
| Сумма запасов | 6,00 | |||||
| Объемы потребностей | ||||||
| № | ||||||
| b | 1,00 | 1,00 | 1,00 | 1,00 | 1,00 | 1,00 |
| Сумма потребностей | 6,00 | |||||
| Матрица удельных расходов | ||||||
| КП1 | КП2 | КП3 | КП4 | КП5 | КП6 | |
| НП 1 | 7,00 | 19,00 | 6,00 | 9,00 | 500,00 | 0,00 |
| НП 2 | 7,00 | 5,00 | 8,00 | 500,00 | 8,00 | 0,00 |
| НП 3 | 10,00 | 9,00 | 500,00 | 6,00 | 7,00 | 0,00 |
| НП 4 | 9,00 | 4,00 | 9,00 | 11,00 | 8,00 | 0,00 |
| НП 5 | 8,00 | 8,00 | 8,00 | 5,00 | 8,00 | 0,00 |
| НП 6 | 9,00 | 500,00 | 12,00 | 7,00 | 6,00 | 0,00 |
| Таблица оптимальных перевозок | ||||||
| КП 1 | КП 2 | КП 3 | КП 4 | КП 5 | КП 6 | |
| НП 1 | 0,00 | 0,00 | 1,00 | 0,00 | 0,00 | 0,00 |
| НП 2 | 1,00 | 0,00 | 0,00 | 0,00 | 0,00 | 0,00 |
| НП 3 | 0,00 | 0,00 | 0,00 | 0,00 | 0,00 | 1,00 |
| НП 4 | 0,00 | 1,00 | 0,00 | 0,00 | 0,00 | 0,00 |
| НП 5 | 0,00 | 0,00 | 0,00 | 1,00 | 0,00 | 0,00 |
| НП 6 | 0,00 | 0,00 | 0,00 | 0,00 | 1,00 | 0,00 |
| Транспортные расходы | 28,00 |
Оптимальное назначение соответствует тем клеткам последней таблицы, в которых находятся единицы. Таким образом, получено следующее оптимальное назначение:
1 работа на 3 станок,
2 работа на 1 станок,
3 работа на 6 станок (фиктивный),
4 работа на 2 станок,
5 работа на 4 станок,
6 работа на 5 станок,
Суммарные затраты составили z = 28.
Таким образом, третья работа на практике будет не выполнена.
Задача о кратчайшем пути.
Рассмотрим следующую транспортную сеть. Параметры сети представлены в виде дроби, числитель которой соответствует расстоянию от пункта с меньшим номером до пункта с большим номером, а знаменатель соответствует расстоянию между этими же пунктами в обратном направлении. Символ ²¥² соответствует отсутствию сообщения между пунктами в данном направлении.
Найдем кратчайшее расстояние от пункта 1 до пункта 8.
Составим таблицу расстояний:
| № | |||||||
| ¥ | |||||||
| ¥ | |||||||
При решении данной задачи с помощью программы таблица расстояний рассматривается, как таблица удельных транспортных расходов. Пустые клетки воспринимаются, как запрещенные маршруты и удельные транспортные расходы равны «машинной бесконечности» (в данной задаче «машинная бесконечность» равна 500). Удельные транспортные расходы для маршрутов из i-го исходного пункта в i-ый конечный пункт равны 0, так как реального движения при этом не происходит.
Лист Расчет после решения задачи имеет вид.
| ТРАНСПОРТНАЯ ЗАДАЧА | |||||||
| Исходные данные | |||||||
| № | Название параметра | Значение | |||||
| Число исходных пунктов | |||||||
| Число конечных пунктов | |||||||
| Число этапов моделирования | |||||||
| Объемы запасов | |||||||
| № | |||||||
| a | 2,00 | 1,00 | 1,00 | 1,00 | 1,00 | 1,00 | 1,00 |
| Сумма запасов | 8,00 | ||||||
| Объемы потребностей | |||||||
| № | |||||||
| b | 1,00 | 1,00 | 1,00 | 1,00 | 1,00 | 1,00 | 2,00 |
| Сумма потребностей | 8,00 | ||||||
| Матрица удельных расходов | |||||||
| КП1 | КП2 | КП3 | КП4 | КП5 | КП6 | КП7 | |
| НП 1 | 0,00 | 8,00 | 9,00 | 4,00 | 500,00 | 500,00 | 500,00 |
| НП 2 | 9,00 | 0,00 | 1,00 | 3,00 | 7,00 | 500,00 | 500,00 |
| НП 3 | 5,00 | 2,00 | 0,00 | 9,00 | 7,00 | 3,00 | 9,00 |
| НП 4 | 6,00 | 2,00 | 7,00 | 0,00 | 500,00 | 9,00 | 500,00 |
| НП 5 | 500,00 | 5,00 | 500,00 | 500,00 | 0,00 | 2,00 | 5,00 |
| НП 6 | 500,00 | 500,00 | 500,00 | 6,00 | 6,00 | 0,00 | 8,00 |
| НП 7 | 500,00 | 500,00 | 6,00 | 500,00 | 7,00 | 5,00 | 0,00 |
| Таблица оптимальных перевозок | |||||||
| КП 1 | КП 2 | КП 3 | КП 4 | КП 5 | КП 6 | КП 7 | |
| НП 1 | 1,00 | 0,00 | 0,00 | 1,00 | 0,00 | 0,00 | 0,00 |
| НП 2 | 0,00 | 0,00 | 1,00 | 0,00 | 0,00 | 0,00 | 0,00 |
| НП 3 | 0,00 | 0,00 | 0,00 | 0,00 | 0,00 | 0,00 | 1,00 |
| НП 4 | 0,00 | 1,00 | 0,00 | 0,00 | 0,00 | 0,00 | 0,00 |
| НП 5 | 0,00 | 0,00 | 0,00 | 0,00 | 1,00 | 0,00 | 0,00 |
| НП 6 | 0,00 | 0,00 | 0,00 | 0,00 | 0,00 | 1,00 | 0,00 |
| НП 7 | 0,00 | 0,00 | 0,00 | 0,00 | 0,00 | 0,00 | 1,00 |
| Транспортные расходы | 16,00 |
Таким образом, кратчайшее расстояние между пунктами 1 и 7 равно 16. При восстановлении соответствующего кратчайшего маршрута учитываются ненулевые недиагональные клетки:
из пункта 1 - в пункт 4;
из пункта 4 - в пункт 2;
из пункта 2 - в пункт 3;
из пункта 3 - в пункт 7;
Графически это выглядит так:
