Курсовая работа: Решение транспортной задачи распределения методом потенциалов

задача программа модель

Теоретическое введение . Задача о размещении (транспортная задача) – это задача, в которой работы и ресурсы измеряются в одних и тех же единицах. В таких задачах ресурсы могут быть разделены между работами, и отдельные работы могут быть выполнены с помощью различных комбинаций ресурсов. Примером типичной транспортной задачи (ТЗ) является распределение (транспортировка) продукции, находящейся на складах, по предприятиям-потребителям.

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

Особенности экономико-математической модели транспортной задачи:

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

Критерий оптимальности формулируется следующим образом: базисное распределение поставок оптимально тогда и только тогда, когда оценки всех свободных клеток неотрицательны. Циклом в матрице называется ломаная с вершинами в клетках и звеньями, лежащими вдоль строк и столбцов матрицы, удовлетворяющую условиям:

· ломаная должна быть связной, т.е. из любой ее вершины можно попасть в любую другую вершину по звеньям ломаной;

· в каждой вершине ломаной встречаются два звена, одно из которых располагается по строке, другое - по столбцу.

Циклом пересчета называется такой цикл в таблице с базисным распределением поставок, при котором одна из его вершин лежит в свободней клетке, остальные - в заполненных. Цикл пересчета называется означенным, если в его вершинах расставлены знаки "+" и "-" так, что в свободной клетке стоит знак "+", а соседние вершины имеют противоположные знаки.

Исходные параметры модели транспортной задачи

1) n– количество пунктов отправления, m – количество пунктов назначения.

2) a_i – запас продукции в пункте отправления A_i (i=1, n) [ед. прод.].

3)b_j – спрос на продукцию в пункте назначения B_j (j=1,m) [ед. прод.].

4)c_ij – тариф (стоимость) перевозки единицы продукции из пункта отправления a_i в пункт назначения b_j [руб./ед. прод.].

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

1) x_ij – количество продукции, перевозимой из пункта отправления a_i в пункт назначения b_j [ед. прод.].

2) L(x)– транспортные расходы на перевозку всей продукции [руб.].

Этапы построения модели

I. Определение переменных.

II. Проверка сбалансированности задачи.

III. Построение сбалансированной транспортной матрицы.

IV Задание целевой функции.

V Задание ограничений.

Целевая функция представляет собой общие транспортные расходы на осуществление всех перевозок в целом. Первая группа ограничений указывает, что запас продукции в любом пункте отправления должен быть равен суммарному объему перевозок продукции из этого пункта. Вторая группа ограничений указывает, что суммарные перевозки продукции в некоторый пункт потребления должны полностью удовлетворить спрос на продукцию в этом пункте. Наглядной формой представления модели транспортной задачи является транспортная матрица (табл. 4.1).

Таблица 4.1Общий вид транспортной матрицы

Пункты отправления, A1	Пункты потребления, Bj				Запасы, ед. прод.
	B1	B2	…	Bm
A1	c11 , [руб./ед. прод.]	c12	…	c1m	a1
A2	c21	c22	…	C2m	a2
…	…	…	…	…	…
An	Cn1	Cn2	…	Cnm	an
« 1 2 3 4 » К-во Просмотров: 196 Бесплатно скачать Курсовая работа: Решение транспортной задачи распределения методом потенциалов >>> Скачать <<< Меню Поиск