Программная реализация решения транспортной задачи
ВВЕДЕНИЕ
Оптимальной производственной программой предприятия считается такая программа выпуска продукции, при которой достигается максимальный экономический эффект. Такая производственная программа может быть определена только путем решения задачи по размещению и концентрации производства по отрасли или народному хозяйству в целом.
Одним из необходимых условий дальнейшего развития экономической науки является применение четных методов количественного анализа и широкое применение математики. В настоящее время новейшие достижения в математике и в современной вычислительной технике находят все более широкое применение в экономических исследованиях и планировании.
Уже накоплен достаточный опыт расстановки и решения экономических задач с помощью математических методов. Особенно успешно развиваются методы оптимального планирования, которые и составляют сущность математического программирования.
Применение методов математического программирования и ЭВМ дает возможность решать сложные экономические задачи, которые ранее не могли быть поставлены и решены, а многие задачи решать быстрее и точнее, чем прежде. Это открывает также новые возможности для качественного анализа, повышает его уровень и действенность.
Все это приводит к значительному улучшению планирования производства и повышению его экономической активности.
Решение экстремальных экономических задач можно разбить на 3 этапа:
построение экономико-математической модели;
нахождение оптимального решения одним из математических методов;
практическое внедрение в народное хозяйство;
1. ПОСТАНОВКА ЗАДАЧИ
Продукцию, сосредоточенную у трех поставщиков - заводов А, В, С необходимо доставить пяти потребителям - складам № 1, 2, 3, 4, 5. Известна стоимость Су единицы продукции от i - го поставщика к j - му потребителю.
Необходимо составить план перевозок, позволяющих вывести всю продукцию, полностью удовлетворить потребности складов и получить минимальные транспортные издержки.
Мощность заводов, потребности складов (в тоннах) и стоимость перевозок (в рублях), смотри табл.1.
Таблица 1
Виды заводовВиды складовМощности заводов, т.I2345Стоимости перевозок, руб.А3032255023500В4010122125300С2120501815600Потребности складов, т.1004006002001001400
Определить оптимальное закрепление заводов к складам, при котором достигается минимизация транспортных издержек.
Задачу решить методом потенциалов, программу написать на языке программирования 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. ПРОГРАММА
tz; crt; = ARRAY [1...6, 1...6] OF INTEGER; MASS-ARRAY [1...6] OF INTEGER; 1, 2; ,X: MATR; K,L,A,B,U,V: MASS;,W,Z,MIN, МАХ,В1,А1Д, J,M,N,T: INTEGER;, Gl: CHAR;;; WRITELN; WRITELN; WRITELN;; WRITELN; WRITELN; WRITELN; WRITELN; WRITELN; WRITELN ('Выполнил студент группы П-10 Коваленко А.Г.')('... Нажмите ввод...');UNTIL KEYPRESSED;(CHAR(12));
WRITE ('Введите количество заводов N= '); READ(N);; WRITELN;('Введите мощности заводов A[l]:');
WRITELN;: = 0;I: = 1 TO N DO BEGIN READLN (A[I]);: = A1+A[I]
END;('Введите количество складов M= '); READ(M); ; WRITELN;
WRITE ('Введите потребности складов B[J]:');.
WRITELN;
Bl: = 0;I := 1 TO M DO BEGIN (B[I]);
Bl: =B1 +B[I];; WRITELN; WRITELN; WRITELN; WRITELN; WRITELN; ('...Нажмите ввод...');(KBD,G1);
FORI: =1 TO N DOJ: = 1 TO M DO C[I,J]: = 0; ('Введите матрицу стоимостей С [I, J]');
WRITELN;I: =1 TON DO BEGIN J: = 1 TO M DO(C[I,J]);
END;
WRITELN ('Добавление столбец');
М: = М+ 1;
FOR I: =1 ТО М DO C[I,M]: = 0; ;> A1 THEN
BEGIN('Добавление строки');:=N+ 1;I: = 1 TON DO
END;;('Введите первоначальный опорный план X[I,J]');
WRITELN;: = 1 TO N DOJ: = 1 TO M DO(X[I,J]);;;
W: = 1;
: FOR I: = 1 TO N DO U[I]: = 999I: = 1 TO M DO V[I]: = 999 [1]: = 0;T: = 1 TO 10 DO I: = 1 TO N DOJ: = 1 TO M DO (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; ;
WRITELN;('...Нажмите ввод...');(KBD, Gl);(CHAR(12)); ('Таблица потенциалов N,W');
WRITELN;I: = 1 TO M DO('V[\I,'] =\ V[I]) ;I: = 1 TO N DOJ: = 1 TO M DO(X[I,J]: 5);: - -999;I: = 1 TO N DOJ: = 1 TO M DOX[I,J] = 0 THEN(U[I] + V[J]>C[I,J]) THEN(U[I] + V[J]-C[I,J]) >MAX: = (U[I] + V[J]) - С [I, J]; K[1]: = I; [l]: = J; ;
Z: = 0;MAX = -999 THEN BEGINI: = 1 TO N DOJ: = 1 TO M DOX[I,J]<>0 THEN Z: = Z + X[I,J]*C[I,J];
WRITELN;WRITELN;WRITELN; WRITELN ('Z-,Z); 2; END;
WRITE('Вершинацикла=\К[1]Д\Ц1]); ;
WRITE ('Введите вершины цикла');(Т);
WRITELN;I: = 2 TO T DO(K[I]);(L[I]);;: = -999;I: = 2 TO T DO: = I MOD 2;(S = 0) AND (X[K[I],L[I]]<MIN) THEN MIN: = X[K[I],L[I]] ;I: = 1TO T DO: = 1 MOD 2;S<>0 THEN X[K[I], L[I]]: = X[K[I], L[I]] + MIN ELSE[K[I],L[I]]: = X[K[I],L[I]] - MIN;;: = W+l;1;
2: WRITELN ('Условие оптимальности выполняется ');('Опорный план - является оптимальным');('Конец вычислений.');;.
8. ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЮ
Включить ЭВМ
ЗапуститьPascalC:\Pascal\System\turbo.exe
Открыть программуTRMP2.pas через менюfile\open.
Откомпилировать программу file\compile
Запустить программу на выполнение File\run
Ввести исходные данные
Полученные результаты вывести на печать
9. РЕЗУЛЬТАТЫ СЧЕТА ПО ПРОГРАММЕ
... нажмите ввод...
введите количество заводов N = 3
введите мощности заводов А[1]:
500
введите количество складов М = 5
введите потребности складов B[J]:
... нажмите ввод...
введите матрицу стоимостей C[I,J]
32 25 50 23
10 12 21 25
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
300 0 0 0 U[2] = 15
100 100 100 200 100 U[3] = 25
вершина цикла = 2,3
введите количество вершинцикла 4
введите вершины цикла
3 3
2
2
... нажмите ввод...
таблица потенциалов N,W
V[l] = 24 V[2] = 23 V[3] = 25 V[4] = 21 V[5] = 18
0 500 0 0 U[1] = 0
200 100 0 0 U[2] = -13
200 0 200 100 U[3] = -3
Z =26900
условие оптимальности выполняется
опорный план - является оптимальным
конец вычислений.
10. ЭКОНОМИЧЕСКОЕ ОБЪЯСНЕНИЕ РЕЗУЛЬТАТОВ
В результате решения задачи по минимизации транспортных издержек получен оптимальный план
Zопт = 26900
Чтобы достигнуть минимальных суммарных затрат на перевозку продукции от заводов к складам, необходимо произвести такое закрепление перевозок:
От завода А к складу№3 - 500 тонн продукции;
От завода В к складу№2 - 200 тонн продукции;
От завода С к складу№1-100 тонн продукции;
От завода С к складу№2 - 200 тонн продукции;
От завода С к складу№4 - 200 тонн продукции;
От завода С к складу№5 - 100 тонн продукции.
Минимальные транспортные издержки = 26900 рублей. В результате оптимизации плана перевозок, получили экономию затрат по транспортировке (29700 - 26900) = 2800 рублей.
ЗАКЛЮЧЕНИЕ
транспортный программный моделирование издержки
В результате выполнения данной курсовой работы были закреплены знания по математическим и программным средствам моделирования при решении минимизации транспортных издержек.
При выполнении курсовой работы закреплены навыки нахождения опорного плана ТЗ, используя метод минимальной стоимости, а также навыки решения ТЗ методом потенциалов.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1.Соколицин С.А. «Применение математических методов в экономике и огранизация машиностроительного производства» Л. «Машиностроение», 2010г.
.Кузнецов Ю.Н. Кузубов В.И. Волощенко А.В. «Математическое программирование» Высшая школа 2010г.
.ЕСПД схема алгоритмов и программ ГОСТ 19.002-90; ГОСТ 19.003-90, издательства стандартов, 2009г.