Транспортная задача по критериям стоимости и времени (стр. 1 из 4)

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

ИРКУТСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра Автоматизированных систем

ТРАНСПОРТНАЯ ЗАДАЧА ПО КРИТЕРИЯМ СТОИМОСТИ И ВРЕМЕНИ

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту по дисциплине

Теория принятия решения

Иркутск 2009г.

Содержание:

1. Постановка задачи

2. Обоснование математической модели

3. Краткие сведения о методе решения задачи

4. Проверка достоверности полученных результатов

5. Алгоритм решения задачи

6. Листинг программы, реализующий алгоритм задачи

7. Руководство пользователя

7.1 Системные требования

7.2 Описание возможностей

7.3 Использование

7.4 Использование инженерного режима

8. Решение задачи курсовой работы на ПЭВМ по исходным данным индивидуального варианта

9. Список использованной литературы

1. Постановка задачи

Имеется

пунктов отправления, в каждом из которых сосредоточено определенное количество единиц однородного продукта, предназначенного к отправке: в первом пункте имеется единиц этого продукта, во втором - единиц, в м пункте единиц, и, наконец, в м пункте единиц продукта. Этот продукт следует доставить в пунктов назначения (потребления), причем в первый пункт назначения следует доставить единиц продукта, во второй - единиц, в й пункт единиц, и, наконец, в й пункт единиц продукта.

Каждый пункт отправления соединен с каждым пунктом назначения некоторым маршрутом (число таких маршрутов

), причем известна удельная стоимость перевозки одной единицы продукта из го пункта отправления в й пункт назначения. Общая стоимость перевозки по любому маршруту пропорциональна количеству перевозимого продукта. Известно также время перевозки продукта из го пункта отправления в й пункт назначения, причем это время не зависит от количества перевозимого груза.

Удельные стоимости

и время перевозок приведены в таблице, при этом:

1) на пропускные способности коммуникаций ограничения не накладываются;

2)

и - количество условных единиц продукта;

3) в верхних отделениях клеток таблицы помещены удельные стоимости

в рублях, а в нижних - время перевозок в часах.

Составить план, минимизирующий общую стоимость перевозок; определить уровень временных затрат при этом плане; произвести, если это возможно, дооптимизацию по времени. Поставленную задачу решить методом потенциалов, использовав для нахождения начального опорного плана метод минимального элемента.

Разработанный программный продукт должен обрабатывать числовые значения из заданного диапазона:

а) количество пунктов отправления может быть или 6, или 7, или 8;

б) количество пунктов отправления может быть или 7, или 8, или 9;

в) количество единиц продукта, предназначенного к отправке может быть взято из диапазона

;

г) количество единиц продукта, которое следует доставить в пункты назначения может быть взято из диапазона

;

д) удельные стоимости могут быть назначены из диапазона

;

е) значения времени перевозок могут быть назначены из диапазона

2. Обоснование математической модели

В пункте

производится единиц однородного продукта. В пункте требуется единиц этого продукта.

Пусть

- количество единиц продукта, перевозимого из пункта в пункт , а затраты на перевозку - материальные, - временные. Необходимо определить множество переменных ( ; ), удовлетворяющих условиям:

,

,

и таких, что целевая функция

достигает минимума.

· Так как во всех пунктах производства не должно остаться не вывезенного товара, необходимо условие

, . Оно гарантирует полный вывоз продукта из всех пунктов производства

· Так как во всех пунктах потребления товара необходимо доставить согласно спросу, необходимо условие

, . Оно означает полное удовлетворение спроса во всех пунктах потребления.

· Количество единиц товара, перевозимого из пункта

в пункт , не может быть отрицательным, следовательно, необходимо ввести условиенеотрицательности ( ; )

· Так как нам необходимо минимизировать суммарные материальные транспортные издержки при перевозе всего товара из пунктов производства в пункт потребления, целевая функция будет иметь вид:

Для дооптимизации по времени необходимо использовать следующую целевую функцию:

·

,при этом необходимо учитывать, что стоимость перевозок не должна изменяться.

3. Краткие сведения о методе решения задачи

Сведение открытой модели транспортной задачи к открытой

В некоторых случаях модель транспортной задачи получается открытой, т.е.

возможны 2 случая:

1.

, тогда вводят фиктивный пункт потребления , а дополнительный столбик матрицы С заполняют очень большими числами (М). После того, как решение получено, все перевозки x_i,n+1 ( ), в оптимальном плане Х_k считают равными нулю.