Курсовая работа: Решение транспортных задач

Однородный груз сосредоточен у т поставщиков в объемах .

Данный груз необходимо доставить п потребителям в объемах .

Известны (i=1,2,…,m; j=1,2,…,n)- стоимости перевозки единицы груза от каждого i-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью и суммарные затраты на перевозку всех грузов минимальны.

Исходные данные транспортной задачи записываются в таблице вида

Таблица 1

		…
			…
			…
…	…	…	…	…
			…

Переменными(неизвестными) транспортной задачи являются (i=1,…,m;i=1,2,…,n)- объемы перевозок от каждого i-го поставщика каждому j-му потребителю. Эти переменные могут быть записаны в матрице перевозок

Математическая модель транспортной задачи в общем случае имеет вид

(1.1)

i=1,2,…,m, (1.2)

j=1,2,…,n, (1.3)

i=1,2,…,m; j=1,2,…,n. (1.4)

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

Таким образом, математическая формулировка транспортной задачи состоит в следующем: найти переменные задачи

i=1,2,…,m; j=1,2,…,n,

удовлетворяющее системе ограничений (1.2), (1.3), условиям неотрицательности (1.4) и обеспечивающее минимум целевой функции (1.1).

В рассмотренной модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарным запросам потребителей, т.е.

.

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

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

Пример 1:

Составить математическую модель транспортной задачи перевоза груза из двух складов в 3 магазина:

Таблица 2

	50	70	80
90	9	5	3
110	4	6	8

Решение. Введем переменные задачи(матрицу перевозок)

Запишем матрицу стоимостей

.

Целевая функция задачи равна сумме произведений всех соответствующих элементов матриц С и Х: