Программная реализация решения транспортной задачи

Размещено на http://allbest.ru

2

ВВЕДЕНИЕ

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

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

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

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

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

Решение экстремальных экономических задач можно разбить на 3 этапа:

- построение экономико-математической модели;

- нахождение оптимального решения одним из математических методов;

- практическое внедрение в народное хозяйство;

1. ПОСТАНОВКА ЗАДАЧИ

Продукцию, сосредоточенную у трех поставщиков - заводов А, В, С необходимо доставить пяти потребителям - складам № 1, 2, 3, 4, 5. Известна стоимость Су единицы продукции от i - го поставщика к j - му потребителю.

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

Мощность заводов, потребности складов (в тоннах) и стоимость перевозок (в рублях), смотри табл.1.

Таблица 1

Виды заводов	Виды складов	Мощности заводов, т.
	I	2	3	4	5
	Стоимости перевозок, руб.
А	30	32	25	50	23	500
В	40	10	12	21	25	300
С	21	20	50	18	15	600
Потребности складов, т.	100	400	600	200	100	1400

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

Задачу решить методом потенциалов, программу написать на языке программирования Turbo Pascal 7.0 и реализовать на ПЭВМ IBM-совместимой машине.

2. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ

Математическая модель в общем виде:

Вводятся обозначения:

m - количество видов заводов

n - количество видов складов

а - мощность i-ro завода

bj - потребность j-го склада

Cij - стоимость перевозки единицы продукции от i-ro завода к j-тому складу

Хij - количество единиц продукции, запланированных к перевозке от i-ro завода к j-тому складу

Zmin - минимальная стоимость перевозок (min транспортные издержки) Математическая модель данной задачи имеет вид:

Z=30X11+32X12+25X13+50X14+23X15+40X21+10X22+12X33+21X24+25X25+21X31+20X31+50X33+18X34+14X35 min



3. МЕТОД РЕАЛИЗАЦИИ МОДЕЛИ

Данная ТЗ решается методом потенциалов.

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

Для этого используется табл. 2.

Таблица 2

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

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

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

После получения опорного плана для дальнейших вычислений необходимо воспользоваться методом потенциалов. Для проверки найденного плана ТЗ, необходимо предварительно вычислить числа Ui и Vj , называемые потенциалами и отвечающие исходному плану. Для начала итерационного процесса нужно составить систему потенциалов для Хij > 0 в полученном опорном плане. Для Uj и Vj справедливо равенство Ui + Vj = Сij.

Получается m + n-1 уравнений с m + n неизвестными. Принимая U1 = О, найдем значения остальных неизвестных Uj и Vj.

Затем находится значение Uj + Vj - Сij для всех Хij = 0. Если при решении получается, что для всех Хij = 0 значение Ui + Vj-Cij > 0, то найденный план является оптимальным.

Если для некоторых Хij = 0 значения Ui + Vj-Cij > 0, то найденный опорный план не является оптимальным, то есть не выполняется условие оптимальности

С ij -- С ij < 0. Следовательно, нужно переходить к новому опорному плану и снова проверить его на оптимальность.

Для перехода к новому опорному плану выбирается наибольшее положительное число из всех С ij -- С ij < 0

Чтобы найти вектор, исключаемый из первоначального базиса, можно воспользоваться таким приемом: из клетки, имеющей максимум С ij -- С ij >0, проводятся линии таким образом, чтобы, начиная движение от данной клетки, двигаясь только под прямым углом и тем клеткам, в которых есть значения, в нее и возвратиться. Первый ход отмечается знаком (+), второй (-), третий (+) и т.д. до конца.

Из клеток со значением (+) выбирается наименьшее значение. Это значение необходимо вычесть из всех клеток со знаком (+) и прибавить к тем клеткам, у которых знак (-). При помощи этого способа получается новый опорный план. Далее снова находятся потенциалы Хij > 0. Этот процесс повторяется до тех пор, пока не получится оптимальный план, то есть пока не будет выполняться критерий оптимальности С ij -- С ij < 0 Вычисления сводятся в таблицу 2.

4. АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ

5. ВЫЧИСЛИТЕЛЬНАЯ СХЕМА

Находиться первоначальный опорный план по методу минимальной стоимости.

Таблица 3

=29700

Решение данной задачи осуществляется методом потенциалов.

Итерация №1

Таблица 4

Итерация №2

=29700

условие оптимальности выполняется, следовательно, план оптимальный, смотри табл. 6.

Таблица 6

6. БЛОК-СХЕМА

7. ПРОГРАММА

PROGRAM tz;

USES crt;

TYPE

MATR = ARRAY [1...6, 1...6] OF INTEGER; MASS-ARRAY [1...6] OF INTEGER;

LABEL 1, 2;

VAR

C,X: MATR; K,L,A,B,U,V: MASS;

S,W,Z,MIN, МАХ,В1,А1Д, J,M,N,T: INTEGER;

KBD, Gl: CHAR;

BEGIN

clrscr;

WRITELN; WRITELN; WRITELN; WRITELN;

WRITELN; WRITELN; WRITELN; WRITELN; WRITELN; WRITELN; WRITELN ('Выполнил студент группы П-10 Коваленко А.Г.')

WRITELN ('... Нажмите ввод...');

REPEAT UNTIL KEYPRESSED;

WRITELN (CHAR(12));

WRITE ('Введите количество заводов N= '); READ(N);

WRITELN; WRITELN;

WRITE ('Введите мощности заводов A[l]:');

WRITELN;

Al: = 0;

FOR I: = 1 TO N DO BEGIN READLN (A[I]);

Al: = A1+A[I]

END;

WRITE ('Введите количество складов M= '); READ(M);

WRITELN; WRITELN;

WRITE ('Введите потребности складов B[J]:');.

WRITELN;

Bl: = 0;

FOR I := 1 TO M DO BEGIN

READLN (B[I]);

Bl: =B1 +B[I]

END;

WRITELN; WRITELN; WRITELN; WRITELN; WRITELN; WRITELN;

WRITELN ('...Нажмите ввод...');

READ (KBD,G1);

FORI: =1 TO N DO

FOR J: = 1 TO M DO C[I,J]: = 0;

WRITE ('Введите матрицу стоимостей С [I, J]');

WRITELN;

FOR I: =1 TON DO BEGIN

FOR J: = 1 TO M DO

BEGIN

READ (C[I,J]);

END;

END;

WRITELN; WRITELN; WRITELN; WRITELN; WRITELN; WRITELN;

WRITELN ('...Нажмите ввод...');

READ (KBD,G1);

WRITELN (CHAR(12));

IF A1 <>B1 THEN

BEGIN

WRITELN ('Открытая модель');

END;

IF A1 >B1 THEN

BEGIN

WRITELN ('Добавление столбец');

М: = М+ 1;

FOR I: =1 ТО М DO C[I,M]: = 0;

END;

IFB1 > A1 THEN

BEGIN

WRITELN ('Добавление строки');

N:=N+ 1;

FOR I: = 1 TON DO

END;

WRITELN;

WRITE ('Введите первоначальный опорный план X[I,J]');

WRITELN;

FORI: = 1 TO N DO

BEGIN

FOR J: = 1 TO M DO

BEGIN

READ (X[I,J]);

END;

END;

W: = 1;

1: FOR I: = 1 TO N DO U[I]: = 999

FOR I: = 1 TO M DO V[I]: = 999

U[1]: = 0;

FOR T: = 1 TO 10 DO

BEGIN

FOR I: = 1 TO N DO

FOR J: = 1 TO M DO

BEGIN

IF (X[I,J]<>0) AND (V[J]<>999) THEN U[I]: = C[I,J] - V[J];

IF (X[I,J]<>0) AND (U[I]<>999) THEN V[J]: = C[I,J] - U[I]; END;

END;

WRITELN;

WRITELN ('...Нажмите ввод...');

READ (KBD, Gl);

WRITELN (CHAR(12));

WRITELN ('Таблица потенциалов N,W');

WRITELN;

FOR I: = 1 TO M DO

BEGIN

WRITE ('V[\I,'] =\ V[I])

END;

FOR I: = 1 TO N DO

BEGIN

WRITELN

FOR J: = 1 TO M DO

WRITE (X[I,J]: 5);

MAX: - -999;

FOR I: = 1 TO N DO

FOR J: = 1 TO M DO

IF X[I,J] = 0 THEN

IF (U[I] + V[J]>C[I,J]) THEN

IF (U[I] + V[J]-C[I,J]) >MAX

THEN

BEGIN

MAX: = (U[I] + V[J]) - С [I, J]; K[1]: = I;

L[l]: = J;

END;

Z: = 0;

IF MAX = -999 THEN BEGIN

FOR I: = 1 TO N DO

FOR J: = 1 TO M DO

IF X[I,J]<>0 THEN Z: = Z + X[I,J]*C[I,J];

WRITELN;WRITELN;WRITELN; WRITELN ('Z-,Z);

GOTO 2; END;

WRITE('Вершинацикла=\К[1]Д\Ц1]);

WRITELN;

WRITE ('Введите вершины цикла');

READ (Т);

WRITELN;

FOR I: = 2 TO T DO

BEGIN

READ (K[I]);

READ (L[I]);

END;

MIN: = -999;

FOR I: = 2 TO T DO

BEGIN

S: = I MOD 2;

IF (S = 0) AND (X[K[I],L[I]]<MIN) THEN MIN: = X[K[I],L[I]]

END;

FOR I: = 1TO T DO

BEGIN

S: = 1 MOD 2;

IF S<>0 THEN X[K[I], L[I]]: = X[K[I], L[I]] + MIN ELSE

X[K[I],L[I]]: = X[K[I],L[I]] - MIN;

END;

W: = W+l;

GOTO 1;

2: WRITELN ('Условие оптимальности выполняется ');

WRITELN ('Опорный план - является оптимальным');

WRITELN ('Конец вычислений.');

READLN;

END.

8. ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЮ

1 Включить ЭВМ

2 ЗапуститьPascalC:\Pascal\System\turbo.exe

3 Открыть программуTRMP2.pas через менюfile\open.

4 Откомпилировать программу file\compile

5 Запустить программу на выполнение File\run

6 Ввести исходные данные

7 Полученные результаты вывести на печать

9. РЕЗУЛЬТАТЫ СЧЕТА ПО ПРОГРАММЕ

... нажмите ввод...

введите количество заводов N = 3

введите мощности заводов А[1]:

500

300

600

введите количество складов М = 5

введите потребности складов B[J]:

100

400

600

200

100

... нажмите ввод...

введите матрицу стоимостей C[I,J]

30 32 25 50 23

40 10 12 21 25

21 20 50 18 15

... нажмите ввод...

введите первоначальный опорный план X[I,J]

0 0 500 0 0

0 300 0 0 0

100 100 100 200 100

... нажмите ввод...

таблица потенциалов N,W

V[l] = -4 V[2] = -5 V[3] - 25 V[4] = -7 V[5] - -10

0 0 500 0 0 U[l] = l

0 300 0 0 0 U[2] = 15

100 100 100 200 100 U[3] = 25

вершина цикла = 2,3

введите количество вершинцикла 4

введите вершины цикла

3 3

3 2

2 2

... нажмите ввод...

таблица потенциалов N,W

V[l] = 24 V[2] = 23 V[3] = 25 V[4] = 21 V[5] = 18

0 0 500 0 0 U[1] = 0

0 200 100 0 0 U[2] = -13

100 200 0 200 100 U[3] = -3

Z =26900

условие оптимальности выполняется

опорный план - является оптимальным

конец вычислений.

10. ЭКОНОМИЧЕСКОЕ ОБЪЯСНЕНИЕ РЕЗУЛЬТАТОВ

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

Z_опт = 26900

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

От завода А к складу№3 - 500 тонн продукции;

От завода В к складу№2 - 200 тонн продукции;

От завода В к складу№3 - 100 тонн продукции;

От завода С к складу№1-100 тонн продукции;

От завода С к складу№2 - 200 тонн продукции;

От завода С к складу№4 - 200 тонн продукции;

От завода С к складу№5 - 100 тонн продукции.

Минимальные транспортные издержки = 26900 рублей. В результате оптимизации плана перевозок, получили экономию затрат по транспортировке (29700 - 26900) = 2800 рублей.

ЗАКЛЮЧЕНИЕ

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

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

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1.Соколицин С.А. «Применение математических методов в экономике и огранизация машиностроительного производства» Л. «Машиностроение», 2010г.

2.Кузнецов Ю.Н. Кузубов В.И. Волощенко А.В. «Математическое программирование» Высшая школа 2010г.

3.ЕСПД схема алгоритмов и программ ГОСТ 19.002-90; ГОСТ 19.003-90, издательства стандартов, 2009г.

Размещено на Allbest.ru