Навигация
Решение транспортной задачи
10126
знаков
2
таблицы
21
изображение
ИНСТИТУТ ТРАНСПОРТА И СВЯЗИ
ФАКУЛЬТЕТ КОМПЬЮТЕРНЫХ НАУК И ЭЛЕКТРОНИКИ
Курсовая работа
Тема: "Решение транспортной задачи"
Выполнила: Долгополова Анастасия 4902BD
Рига
2010
Оглавление
1. Постановка задачи
2. Формулировка задачи
3. Теоретическое обоснование. Общие вопросы
4. Описание алгоритма нахождения потока минимальной стоимости
5. Решение индивидуального задания по шагам
6. Программа (Mathcad)
7. Исходные данные
8. Результат программы
9. Конечные результаты
Вывод
1. Постановка задачи
Математическая постановка задачи. Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза k-пунктов отправления а1,а2,…аiв m пунктов назначения b1,b2,…bj. При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость всего груза, либо минимальное время его доставки. Данная транспортная задача была рассмотрена, где в качестве критерия оптимальности была взята минимальная стоимость перевозок все груза. Были введены следующие обозначения:
k – число поставщиков;
m – число потребителей;
i – индекс производителя i =1,к
j – индекс потребителя j = 1,m
а1 – возможности i-ro производителя
bj – спрос j-ro потребителя
сi,j– транспортные издержки (расходы) за доставку продукции от i к j.
xi,j – объемы перевозок от i к j.
Требуется составить план перевозок для которого:
1. все потребители удовлетворены
2. общие транспортные расходы минимальны
Требуется минимизировать функцию:
Ограничения по производству:
Общая сумма производимой продукции больше или равна спросу:
Следовательно ci,j тарифы перевозок единицы груза из i-го пункта отправления в j-й пункт назначения, через ai– запасы груза в i-м пункте отправления, через bj – потребности в грузе в j-м пункте назначения, а через хi,j – количество единиц груза, переводимого из i-го пункта определений в j-й пункт назначения. Тогда математическая постановка транспортной задачи состоит в определении минимального значения функции.
2. Формулировка задачи
Число производителей
k=3
а1=38
Объем производимой продукции
а2=45
а3=97
Число потребителей
m=4
b1=42
b2=35
Потребности потребителей:
b3=63
B4=15
| Производители | Потребители | |||
| j=1 | j=2 | j=3 | j=4 | |
| i=1 | 10 | 11 | 18 | 32 |
| i=2 | 16 | 14 | 20 | 25 |
| i=3 | 26 | 28 | 22 | 30 |
Рис. 1
На рисунке 1 представлен исходный граф, который иллюстрирует транспортную задачу. Для решения данной задачи требуется использовать стандартную форму фиксированного источника и стока. Каждый производитель связан с каждым потребителем. Источник не может иметь связи с потребителем, но зато каждый потребитель, в свою очередь, связан с фиктивным стоком. В обозначении дуги присутствует два параметра. Первый параметр указывает пропускную способность дуги, второй параметр показывает стоимость пересылки единицы потока на дуге. Так, например, из источника выходят дуги содержащие ограничения по пропускной способности, т.к. данная величина характеризует производительную возможность каждого поставщика, стоимость данной дуги равна нулю, т.к. источник – фиксированный элемент нашего графа. Такая же ситуация обстоит с дугами, которые втекают в сток. Дуги, которые выходят из i-ых вершин (производители) и входят j-ые вершины (потребители), т.е. соединяющие поставщика со складок, характеризуются тоже двумя параметрами. Только в этом случае, для данных дуг, в качестве первого параметра берется пропускная способность дуги равная бесконечности, а второй показатель – стоимость пересылки единицы потока.
Похожие работы
... сразу же составлен план перевозок, удовлетворяющий балансовым условиям. Полученное решение является опорным решением транспортной задачи. Составленный нами план перевозок, не является оптимальным по стоимости, так как при его построении мы совсем не учитывали стоимость перевозок Сij . 3. Метод потенциалов. Пусть имеется транспортная таблица, соответствующая начальному решению, хil= для ...
... . Система векторов условий транспортной задачи линейно независима тогда и только тогда, когда из соответствующих им клеток таблицы нельзя образовать ни одного цикла. Следовательно, допустимое решение транспортной задачи , i=1,2,…,m; j=1,2,…,n является опорным только в том случае, когда из занятых им клеток таблицы нельзя образовать ни одного цикла. Метод вычеркивания. Для проверки возможности ...
... . При этом значения cij соответствуют коэффициентам целевой функции исходной замкнутой транспортной задачи (1) и в последующем не изменяются. Элементы xij соответствуют значениям переменных промежуточных решений транспортной задачи линейного программирования и изменяются на каждой итерации алгоритма. Если в некоторой ячейке xij=0, то такая ячейка называется свободной, если же xij>0, то такая ...
... ). Требуется распределить все работы между всеми рабочими так, чтобы время выполнения работ было минимальным, а каждую работу выполнял только один рабочий. §4. Решение транспортной задачи в Excel В качестве примера я рассмотрел транспортную задачу для 2 складов и 5 магазинов. · В ячейки C4:C5 записал объемы продукции, имеющиеся на 2 складах. · В ячейки E5:I5 - заявки на продукцию, ...
0 комментариев