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

Оглавление

 Описание методов решения транспортных задач       2

Аналитическое решение  задачи         4

Ручной расчет           5

Заключение            7

Список литературы           8

Блок-схема решения  задачи          9

Листинг программы           13

Инструкция пользователя         23

 Контрольный тест  программы          24 
2. Описание методов решения транспортных задач

 

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

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

Транспортная задача — задача об оптимальном плане  перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).

Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку).

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

Транспортная задача является частным типом задачи линейного  программирования и формулируется следующим образом. Имеется m пунктов отправления (или пунктов производства) Аi…, Аm, в которых сосредоточены запасы однородных продуктов в количестве a1, ..., аmединиц. Имеется n пунктов назначения (или пунктов потребления) В1, ..., Вm, потребность которых в указанных продуктах составляет b1, ..., bnединиц. Известны также транспортные расходы Сij, связанные с перевозкой единицы продукта из пункта Aiв пункт Вj, i 1, …, m; j 1, ..., n. Предположим, что т. е. общий объем производства равен общему объему потребления. Требуется составить такой план перевозок (откуда, куда и сколько единиц продукта везти), чтобы удовлетворить спрос всех пунктов потребления за счет реализации всего продукта, произведенного всеми пунктами производства, при минимальной общей стоимости всех перевозок. Приведенная формулировка транспортной задачи называется замкнутой транспортной моделью. Формализуем эту задачу.

Пусть хij- количество единиц продукта, поставляемого из пункта Аiв пункт Вj. Подлежащие минимизации суммарные затраты на перевозку продуктов из всех пунктов производства во все пункты потребления выражаются формулой. Суммарное количество продукта, направляемого из каждого пункта отправления во все пункты назначения, должно быть равно запасу продукта в данном пункте. Формально это означает, что i=1, …, m

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

 j=1, …, n (3)

Объемы перевозок - неотрицательные  числа, так как перевозки из пунктов потребления в пункты производства исключены: xij 0, i 1, ..., m; j 1, ..., n

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

2.2 Математические методы решения транспортных задач

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

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

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

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

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

Алгоритм:

1.Из таблицы стоимостей выбирают наименьшую стоимость и в клетку, которая ей соответствует, вписывают большее из чисел.

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

3.Если не все потребители удовлетворены и не все поставщики израсходовали товары, возврат к п. 1, в противном случае задача решена.

Методы определения  оптимального плана

Метод потенциалов

Метод потенциалов является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций.

Общая схема отдельной  итерации такова.

По допустимому решению каждому пункту задачи сопоставляется число, называемое его предварительным потенциалом. Пунктам Аi соответствуют числа ui, пунктам Bj - числа vj. Они выбираются таким образом, чтобы их разность на k-й итерации была равна Сij - стоимости перевозки единицы продукции между пунктами Аi и Вj:

Если разность предварительных  потенциалов для каждой пары пунктов  Аi, Вj не превосходит Сij, то полученный план перевозок является решением задачи. В противном случае указывается способ получения нового допустимого плана, связанного с меньшими транспортными издержками. За конечное число итераций находится оптимальный план задачи.

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

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

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

называемые разностями потенциалов. В таблице они выписаны для всех небазисных клеток под ценами.

Разность потенциалов  можно трактовать как увеличение цены продукта при его перевозке  из пункта i в пункт j.

Процесс «улучшения»  плана состоит в определении  вводимой и выводимой клеток, в  чем прослеживается содержательная аналогия с соответствующими пунктами симплекс-процедур.

 

 

 

 

 

 

 

3. Аналитическое решение задачи

3.1 Решение в табличном  процессоре MS Excel

 

 

 

3.2 Ручной расчет

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

 

Дано:

 

	B1	B2	B2	B4	Запасы
A1	2	3	4	3	180
A2	5	3	1	2	60
A3	2	1	4	7	80
Потреб	140	40	60	80

 

 

 

 

 

 

Запасы=180+60+80=320

Потребности=140+40+60+80=320

Вычисляем:

 

	B1	B2	B2	B4	Запасы
A1	140	40			0
A2			60		0
A3				80	0
Потреб	0	0	0	0

 

 

 

 

 

 

F(x)=2*140+3*40+1*60+2*80=620

140	40	0	0
0	0	60	0
0	0	0	80

Ответ:F(x) = 620

            F(x)=          

 

 

 

 

 

 

 

 

 

 

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

 

	B1	B2	B2	B4	Запасы
A1	140			40	0
A2			60		0
A3		40		40	0
Потреб	0	0	0	0

 

 

 

 

 

      

F(x)=2*140+3*40+1*60+40+2*40=580

Ответ:F(x) = 580

140	0	0	40
0	0	60	0
0	40	0	40

                  

  F(x)=

 

4.Заключение

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

 

5.Список литературы

  

Материал, используемый для составления и решения  транспортных задач:

1)Материал из Википедии  — свободной энциклопедии: Транспортная задача.

http://ru.wikipedia.org/wiki/Транспортная_задача  

2) Учебник по C++ Builder.

http://www.intbook.info/C/menu.html

 

 

6.Приложение A (обязательное). Блок-схема решения задачи

6.1 Структурная блок-схема

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6.2Блок-схема метода северо-западного угла

 

1

 

 

2

 

да  

 

 

 

нет

 

3

 

4 да

 

 

 

нет

 

5

да

6

 

 

 

нет

 

7

да

8

 

 

 

нет

 

 

 

 

9

6.3.Блок-схема метода минимального элемента

 

 

 

 

1

 

 

 

 

 

 

 

 

2

 

 5

 да

 3

нет

 нет

   да

4 12

 

 

 

 

 

 

 

7

6

 

 

 

 

 

 

 

 

 

 

 

 нет

9

8

 

 

 

 

 

 

 

нет

 

11 10

 

 

 

 

нет

 
7.Приложение Б (обязательное) Листинг программы

Исходный код menu .cpp

//---------------------------------------------------------------------------

#include <vcl.h>

#pragma hdrstop

 

#include "menu.h"

#include "about.h"

#include "help1.h"

#include "sevzap1.h"

#include "minimal1.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma resource "*.dfm"

Tmenu1 *menu1;

//---------------------------------------------------------------------------

__fastcall Tmenu1::Tmenu1(TComponent* Owner)

        : TForm(Owner)

{///////заполняем таблицу  (потребители)

StringGrid1->Cells[1][0]="B1";

StringGrid1->Cells[2][0]="B2";

StringGrid1->Cells[3][0]="B3";

StringGrid1->Cells[4][0]="B4";