IV Международная студенческая научная конференция Студенческий научный форум - 2012

  АННОТАЦИЯ

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

ВВЕДЕНИЕ

Одной из классических задач экономического содержания является транспортная задача, решаемая средствами линейного программирования. Данная задача относится к задачам прикладной направленности, и в промышленных регионах ее решение приобретает особо важное значение. Цель транспортной задачи - разработка наиболее рациональных путей и способов транспортирования товаров, устранение чрезмерно дальних, встречных, повторных перевозок. Все это сокращает время продвижения товаров, уменьшает затраты предприятий, фирм, связанные с осуществлением процессов снабжения сырьем, материалами, топливом, оборудованием и т.д. В настоящее время разработано множество различных алгоритмов решения транспортной задачи: распределительный метод, метод потенциалов, дельта-метод, венгерский метод, метод дифференциальных рент, различные сетевые методы [1] и т. д. Задачи эти часто усложняются разного рода дополнительными условиями: например, в них включается расчет не только себестоимости перевозок, но и себестоимости производства продукции (производственно-транспортная задача), оптимизируется совместно доставка взаимозаменяемых видов продукции, доставка грузов с промежуточными базами (складами). Кроме того, следует учитывать, что математическая модель транспортной задачи позволяет описывать множество ситуаций, весьма далеких от проблемы перевозок.

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

1. СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ

На три станции "Ерунаково", "Ускатская", "Томусинская" прибыл некоторый однородный груз (уголь), который необходимо перевезти потребителям четырех населенных пунктов Тагарыш, Таганково, Красулино, Кузедеево. 

Потребности заказчиков (в условных единицах), количество груза на каждой станции (в условных единицах) и тарифы (стоимость перевозки единицы груза от данной станции к данному заказчику) указаны в таблице.

Таблица 1 - Исходные данные транспортной задачи

bi ai	90	120	110	130
105	12	9	7	11
165	4	3	12	2
180	5	17	9	4

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

Значит,  мы имеем закрытую модель транспортной задачи. Ее можно решить классическими методами - методом северо-западного угла или методом минимального элемента.

2. РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ СРЕДСТВАМИ MS EXCEL

Поставленная транспортная задача решается средствами Excel [2].

Пусть с трех станций требуется развести грузы в объемах 105, 165 и 180 условных единиц заказчикам в 4 пункта доставки в объеме 90, 120, 110 и 130 условных единиц. (рис. 1). Известна цена перевозки единицы груза с каждого склада в каждый пункт доставки (столбцы С, Е, G, I). Наша задача заключается в следующем: определить такие объемы перевозок со станций в пункты доставки, чтобы стоимость транспортировки была минимальной. На рис. 1 искомые значения уже вычислены и обведены жирной рамкой. Видим, что стоимость всего "мероприятия" составляет 2020 руб. Рассмотрим, как были получены эти значения.

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

Для решения используем инструмент ПОИСК РЕШЕНИЯ (Solver), где введем следующие параметры:

Установить целевую ячейку С8 равной минимальному значению.

Изменяя ячейки: D3:D5;F3:F5;H3:H5;J3:J5

Ограничения:

B3=D3+F3+H3+J3  - стоимость вывоза с 1-го склада

B4=D4+F4+H4+J4  - стоимость вывоза со 2-го склада

B5=D5+F5+H5+J5  -стоимость вывоза с 3-го склада

D6=D3+D4+D5 -стоимость доставки в 1-й пункт

F6=F3+F4+F5  - стоимость доставки в 2-й пункт

H6=H3+H4+H5  - стоимость доставки в 3-й пункт

J6=J3+J4+J5  - стоимость доставки в 4-й пункт

F3:F5>=0 - условие положительности стоимости

D3:D5>=0 - условие положительности стоимости.

H3:H5>=0- условие положительности стоимости

J3:J5>=0 -условие положительности стоимости

В задачах может предполагаться перевозка груза, измеряемого в условных единицах, расфасовка которого по транспортным средствам безразлична, например, жидкость, песок или мелкоштучные грузы. Если же имеется в виду перевозка чего-то крупного и неделимого, например, грузовых контейнеров (как в нашем случае) следует ввести дополнительные ограничения на целочисленность перевозимых объемов: D3:D5=целое, F3:F5=целое, J3:J5=целое и H3:H5=целое, при этом значение целевой функции осталось как и прежде - 2020 руб.

3. РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ ПРИ ПОМОЩИ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ

Написание любой программы начинается с написания её на алгоритмическом языке.[3]

Приведем фрагмент такого алгоритма:

алг транспортная задача (арг вещ таб а[1:4,1:5], вещ таб а[1:4,1:5], рез вещ s)

дано таб а |таблица

надо s |оценить суммарную стоимость плана перевозок

нач

            a[1,1]:=0; | Заказчики

            Вывод Введите потребности 1 заказчика

            Ввод a[1,2]

...

Вывод  Введите количество груза 1 станции

            Ввод a[2,1]

...

нс        | Тарифы

Вывод Введите тариф от 1 станции к 1 заказчику

            Ввод a[2,2]

...

нс

            Вывод Исходная таблица

            ВЫВ (а)

            нс

            Вывод  Построим исходный план перевозок по правилу «Северо-западного угла»

            b[1,2]:=a[1,2];

b[1,3]:=a[1,3];

...

ВЫВ (b)

Вывод Суммарная стоимость построенного плана

s:=b[2,2]*a[2,2]+b[2,3]*a[2,3]+b[3,3]*a[3,3]+b[3,4]*a[3,4]+b[4,4]*a[4,4]+b[4,5]*a[4,5];

нс

Вывод s

кон

 

алг ВЫВ (арг вещ таб а[1:4,1:5],)

            арг вещ i, j

нач

            нц для i от 1 до 4

                        нц для j от 1 до 5

                        вывод a[i, j]

                        нс

                        кц

            кц

кон

 

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

Пример построения кода программы на языке Pascal (не полный код)

Program Trans;

Uses crt;

Const n=4; m=5;

Type tab=array [1..n, 1..m] of integer;

Var a,b:tab;

:integer;

Procedure vivod(var x:tab);

Var i,j:integer;

Begin

...

End;

Begin clrscr;

a[1,1]:=0;

{Zakazhiki}

Write(´vvedite potrebnost 1 zakazhika ´); Readln(a[1,2]);

...

{Tarifi}

Write(´vvedite tarif ot 1 stancii k 1 zakazhiky ´); Readln(a[2,2]);

Write(´vvedite tarif ot 1 stancii ko 2 zakazhiky ´); Readln(a[2,3]);

...

Writeln;

Writeln(´TABLICA 1´);

vivod(a);

Writeln;

Writeln(´Postroim ishodnii plan perevozok po pravily "NordWest"´);

b[1,2]:=a[1,2];

b[1,3]:=a[1,3];

b[1,4]:=a[1,4];

b[1,5]:=a[1,5];

b[2,1]:=a[2,1];

b[3,1]:=a[3,1];

b[4,1]:=a[4,1];

if b[1,2]<b[2,1] Then

Begin

b[2,2]:=b[1,2];

b[2,1]:=b[2,1]-b[1,2];

b[1,2]:=0;

end;

...

if b[1,5]=b[4,1] Then

Begin

b[4,5]:=b[1,5];

end;

vivod(b);

Writeln(´Summarnai stoimost postroennogo plana´);

s:=b[2,2]*a[2,2]+b[2,3]*a[2,3]+b[3,3]*a[3,3]+b[3,4]*a[3,4]+b[4,4]*a[4,4]+b[4,5]*a[4,5];

Writeln(´s:=´,s);

Readln;

End.

ЗАКЛЮЧЕНИЕ

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

СПИСОК ЛИТЕРАТУРЫ

1. Партыка Т.Л. Математические методы [текст]: Учебник/ Партыка Т.Л., Попов И.И. - 1-е издание - М.: ФОРУМ: ИНФРА-М, 2005.-464 с.:- (серия Профессиональное образование).
2. Попов А.А. Excel Практическое руководство [текст]: Учебное пособие для ВУЗов/ Попов А.А. - 2-е издание - ДЕСС КОМ, 2000.-302 с.
3. Семакин И.Г. Основы программирования [текст]: Учебник для среднего профессионального образования/ Семакин И.Г., Шестаков А.П. - 3-е издание, стереотипное - М.: Издательский центр «Академия», 2004. - 432 с.

Код для цитирования: Скопировать