Транспортная задача

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

Санкт-Петербургский  Промышленно - Экономический Колледж

 

 

 

 

 

 

 

Курсовая  работа

По  предмету: Методы математического анализа  экономической деятельности предприятия.

 

На  тему: Транспортная задача.

 

 

 

 

 

 

 

 

Работу выполнил:

Гончаров Дмитрий Николаевич.

Студент группы: 442-00

Преподаватель:

Бондарчук Галина Андриановна

Оценка: ______________________

 

 

 

 

 

 

Мурманск 2005 г.

Содержание

Введение 

 

1.Транспортная  задача.

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

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

1.3   Опорный  план 

 

2.  Решение транспортных задач.

2.1  Метод северо-западного угла

2.2  Метод  минимального элемента 

2.3  Метод  аппроксимации  

4. Потенциалы.
5. Критерий оптимальности плана

 

 

3.  Программа

3.1 Инструкция по эксплуатации программы (Delphi 7)

3.2 Код программы

3.3 Разработка  программы при помощи MS Excel.

 

4.  Практическое применение методов. 

Заключение 

 

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

 

Введение

При появлении мощных ЭВМ стало  возможным проведение сложных и емких расчетов, следовательно, появилась возможность реализовать на практике многие придуманные ранее теории. Одной из таких теорий является решение «транспортных задач». В связи с ростом промышленности и грузообороте без математической системы оптимизации обойтись было нельзя.  Данные методы стали, применятся в промышленности, транспорте и др. областях.

В данной работе я поставил себе задачу:

Изучить  методы решения транспортной задачи.

Написать программу  вычисляющую, одним из способов, решение Т.З.

 

1.Транспортная  задача 

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

 

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

Необходимо  составить план перевозок, позволяющий  вывезти все товары, полностью  удовлетворить потребности потребителей и иметь минимальную стоимость  затрат на перевозку.

  

 Условия  задачи можно записать в виде  таблицы.

Таблица    1

СКЛАДЫ		ПОТРЕБИТЕЛИ			ЗАПАСЫ
A1	C11 x11	C12 x12	...	C1n x1n	а1
A2	C21 x21	C22 x22	...	C2n x2n	а2
…					…
AN	Cm1 xm1	Cm2 xm2	...	Cmn xmn	N
Потребности	B1	B2	…	BN

 

 

  Так как от  поставщика к  потребителю запланирован к перевозке  груз, то стоимость перевозки составит.

Оценка стоимости всего  плана выразится  суммой:

     Z  =  .

 

 

 

 

 

Ограничений получаем из следующих  условий задачи:

 а) все грузы должны  быть вывезены, т.е. 

 б) все потребности должны быть удовлетворены, т.е. 

 

ММ транспортной задачи имеет  следующий вид:

  

 Z =                

  ,

i = 1, 2, ..., m,             

 ,

j = 1,2,3,...,n ,                

Суммарные запасы равны суммарным потребностям,

    

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

 

C¢¢ M ≤ Z ≤ C¢ M ,

 

1.2 Открытая  модель транспортной задачи

     Задача, в которой сумма запасов и потребностей совпадают, называется закрытой моделью;  в противном случае ¾ открытой. Для открытой модели может быть два случая:

 

суммарные запасы превышают суммарные потребности;

 

суммарные потребности  превышают суммарные запасы.

 

Открытая  модель решается приведением к закрытой модели.

 

В случае, когда  суммарные запасы превышают суммарные  потребности, вводится фиктивный потребитель B_n+1, потребности которого  b_n+1 = .

В случае, когда  суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик  A_m+1, запасы которого a_m+1 = .

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

 

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

 

1.3   Построение  опорного плана.          

 Система  ограничений (2) и (3) транспортной  задачи содержит m´n неизвестных и m+n уравнений. Если сложить почленно уравнения отдельно подсистемы  (2) и отдельно подсистемы (3), то получим два одинаковых уравнения. В таблице такое сложение равнозначно соответственно по членному сложению столбцов и почленно сложению строк. Если условие транспортной задачи и ее опорный план записаны в виде таблицы, то клетки, в которых находятся отличные от нуля перевозки, называются занятыми, а остальные - незанятыми.

 Клетки будучи  заполненными соответствуют неизвестным,  и для невырожденного опорного  плана их количество равно 

m+n-1. Если ограничения транспортной задачи записаны в виде (2) и (3) то, как известно, базисным неизвестным, включенным в опорный план, соответствует система линейно независимых векторов.

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

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

       
2. Решение транспортных задач.

2.1 Построение исходного опорного плана (метод северо-западного угла)

Для решения транспортной задачи необходим исходный опорный план.

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

Заполнение  клеток таблицы условно начинается с левой верхней клетки. Для  неизвестного Х 1, 1 (СЗУ) и заканчивается  клеткой для неизвестного Х мин. т.е. идет по диагонали таблицы.

Пример:

На три базы: А 1, А 2, А 3 поступил однородный груз в соответствующем количестве: 140, 180, 160 единиц.

Этот груз требуется  перевести в пять пунктов назначения: В 1, В 2, В 3, В 4, В 5,  соответственно в  количествах 60,  70,  120,  130,  100.

Тарифы перевозок  единицы груза с каждого из пунктов отправления в соответствующий пункт назначения указаны в таблице. Тарифы обозначим Х.

Представим  это в виде таблицы,

Х	Х	Х	Х	Х	А 1
Х	Х	Х	Х	Х	А 2
Х	Х	Х	Х	Х	А3
В 1	В 2	В 3	В 4	В 5

 

Где в столбце  справа указаны запасы, в строке снизу потребности, а пустые клетки оставлены для будущего плана перевозок.

Начнем заполнение с клетки, расположенной вверху слева, то есть с "северо-западного угла".

2       60	3	4	2	4	140
8	4	1	4	1	180
9	7	3	7	2	160
60	70	120	130	100

 

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

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

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

 

2      60	3       70	4      10	2	4	140
8	4	1      110	4      70	1	180
9	7	3	7      60	2      100	160
60	70	120	130	100

 

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

2*60+3*70+4*10+1*110+4*70+7*60+2*100=1380

     При составлении первоначального опорного плана методом северо-западного угла стоимость перевозки единицы не учитывается, поэтому построенный план далек от оптимального.

 

2.2  Метод минимального  элемента

Выбор пункта отправления  и назначения целесообразно производить, ориентируясь на тарифы перевозок:

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

Рассмотрим  этот метод на предыдущей задаче:

2	3	4	2	4	140
8	4	1	4	1	180
9	7	3	7	2	160
60	70	120	130	100