Методы оптимального решения транспортной задачи с дополнительными условиями (ограничениями)

Пусть для каждого  поставщика нерационально везти  меньше 200 единиц товара, так как  машина не будет использоваться полностью  и затраты  на поставку продукции  вырастут в 3 раза. Рассмотрим такую  ситуацию: x>= 200

 

Таблица 18. «Пол»  перевозок

Склады	Магазины						Определение избытка (недостатка)
	900	500	300	400	200	200
800	2 [400]	4 [200]	5	8	9	6	800
600	7	9	8	7	5 [200]	5 [200]	600
400	6	4	6	4     [400]	5	8	0
100	7	3	8	8	4	9	-100
300	6	1  [300]	4 [300]	5	6	4	-500
500	1    [500]	2	6	9	7	3	-500
Определение дифференциальной ренты	5	5			4	1

В нашей задаче возникает проблема: у 4 поставщика на складе содержится всего 100 единиц груза, которые он провезет уже по цене в 3 раза дороже, чем указана в  таблице. Перераспределяем план перевозок.

F=2*400+4*200+5*200+5*200+4*400+1*500+1*300+4*300=7200

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

 

 

 

 

3 Решение транспортных  задач с ограничениями с помощью ЭВМ

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

3.1Решение транспортной задачи с помощью MS Excel.

Возьмем задачу, которую  мы уже рассмотрели выше и сравним  результат, полученный методом потенциалов с результатом, полученным в MS Excel:

Таблица 19. ППП

Склады	Кондитерские  цеха
		1	2	3	4	5	Запас, т/мес.
1	4	6	8	2	2	80
2	3	1	5	6	5	70
3	5	2	1	6	3	60
4	3	7	2	4	9	55
5	2	5	8	2	4	65
Спрос, т/мес.	78	57	59	63	74

 

Пошагово рассмотрим, как  реализовать с помощью MS Excel 2007 транспортную  задачу:

1)Сначала внесем  первоначальный план в MS Excel, как указано на рисунке 2

В ячейки А12:F16 введены стоимости перевозок. В ячейки H12:H16 введены запасы на складах. В ячейки A18:F18 введены потребности кондитерских цехов в сахарном  песке. Ячейки А1:F5 – это опорный план, полученный выше, эти ячейки выделены цветом.

2) В ячейки А6:F6 введены формулы определяющие объем продукции, необходимый для кондитерских цехов:

=СУММ(А1:А15)

=СУММ(В1:В15)

=СУММ(С1:С5)

=CУMM(D1:D5)

=СУММ(Е1:Е5)

=СУММ(F1:F5)

В ячейки G1:G5 введены формулы, вычисляющие объем продукции, вывозимой со складов:

=СУММ(А1:F1)

=СУММ(А2:F2)

=СУММ(А3:F3)

=СУММ(А4:F4)

=СУММ(А5:F5)

В ячейку G6 введена целевая функция:

=СУММПРОИЗВ(А12:F16; А1:F5)

Рисунок 2

 

 

3)Теперь выберем команду Сервис, Поиск решения (Tools, Solver) и заполним открывшееся диалоговое окно Поиск решения (Solver). Для MS Excel 2007 необходимо зайти в меню данные, поиск решения. Заполнить открывшееся окно, как показано на рисунке 3.

Рисунок 3

В диалоговом окне Параметры поиска решения (Solver Options) установите флажок Линейная модель (Assume Linear Model). После нажатия кнопки Выполнить (Solve) средство поиска решений находит оптимальный план поставок продукции и соответствующие ему транспортные расходы. Результат выполнения можно посмотреть на рисунке 4.Составим также в MS Excel отчет по результатам, чтоб просмотреть как изменился первоначальный план. (рисунок 5)

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

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 4

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 5

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

3.2 Программная реализация транспортной задачи с помощью Delphi 7

Блок – схема  программы представлена в приложении 1.

Программа, которая  будет представлена дальше, выполнена  в системе Delphi 7.[6] Задача выводит допустимое решение, пользователю лишь необходимо ввести с клавиатуры потребности i-го потребителя, затем ввести запасы j-го поставщика. Клавишей «Enter» пользователь вызывает таблицу, в которой отображены вводимые пользователем данные и допустимое решение. Ниже представлен пример (рисунок 6) использования написанной задачи, код самой программы представлен в приложении 2. Программа выдает лишь допустимое решение, оно возможно не является оптимальным.

Рисунок 6

 

 

 

Заключение

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

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

В данной курсовой показана программная реализация транспортной задачи с построением первоначального опорного плана северо – западным методом и само решение - методом потенциалов. Программа является не конечным продуктом, ее можно доработать, подстроить под нужное нам количество потребителей и поставщиков. Универсальность данной программы, это ее главный плюс. Решение данной программы возможно и не является оптимальным, но решается пользователем за доли секунд. Таким образом, мы можем гораздо быстрее составить план перевозок и сэкономить время.

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

Цель курсовой работы выполнена, посредством поставленных задач.

 

 

 

Список использованных источников:

[1] http://www.grandars.ru/model-transportnoy-zadachi.html

[2] Монахов В.М., Беляева Э.С., Краснер Н.Я. Методы оптимизации. – М.: Просвещение, 1978.

[3] http://ru.wikipedia.org/wiki/Алгоритм_Куна

[4] Глухов В.В., Медников М.Д., Коробко С.Б.. Математические методы и модели для менеджмента.- СПб.:Лань,2007.

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

[6]Фаронов В.В, DELPHI. Программирование на языке высокого уровня: Учебник для ВУЗов-СПб.: Питер,2008.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение 1

 

 

нет                                              да

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

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

  

    

 Нет   Да

  

Приложение 2

Program Transportnaya;

Uses crt; {подключение модуля очистки экрана}

Const n=6; {количество строк}

m=5; {количество столбцов}

Var a:array [1..n] of integer; {Массив поставщиков}

b:array [1..m] of integer; {Массив потребителей}

 a1:array [1..n] of integer; {Дополнительный массив запасов}

b1:array [1..m] of integer; {Дополнительный массив потребностей}

c:array [1..n,1..m] of integer; {Основной массив в который производится запись базисного решения}

i,j,k,x,y,s,p:integer; {Необходимые  переменные}

{ввод с клавиатуры}

procedure vvodklav;

begin

i:=1;

k:=0;

s:=0;

while (k=0) and (i<n) do

 begin

write('Введите  запaсы ',i,' поставщика: ');

 readln(a[i]);

if a[i]=0 then

begin

k:=1;

i:=i-1;

end

else

begin

a1[i]:=a[i];

s:=s+a1[i];

i:=i+1;

end;

end;

j:=1;

k:=0;

p:=0;

textcolor(6);

while (k=0) and (j<m) do

 begin

write('Введите  потребности ',j,' потребителя: ');

 readln(b[j]);

if b[j]=0 then

begin

k:=1;

j:=j-1;

end

else

begin

b1[j]:=b[j];

p:=p+b1[j];

j:=j+1;

end;

end;

k:=0;

if s<p then

 begin

writeln('Ошибка  ввода!!! Проверьте баланс между  поставщиками и потребителями');

 readln;

halt;

end;

if (p<s) and (k=0) then

 begin

writeln('Ошибка  ввода!!! Проверьте баланс между  поставщиками и потребителями');

 readln;

halt;

end;

x:=i;

y:=j;

end;

begin

clrscr; {очистка экрана}

writeln('Построение  первоначального плана перевозок  методом северо-западного угла');

writeln;

writeln('Программу  составила студентка группы ПИ-31:Бурягина  Оксана Юрьевна ');

writeln;

vvodklav; {Использование  процедуры ввода с клавиатуры}

repeat

k:=0;

if (b[j]-a[i]<0) then

begin

c[i,j]:=b[j];

a[i]:=a[i]-b[j];

b[j]:=0;

j:=j-1;

k:=1;

end;

if (b[j]-a[i]>0) and (k=0) then

begin

c[i,j]:=a[i];

b[j]:=b[j]-a[i];

a[i]:=0;

i:=i-1;

k:=1;

end;

if (b[j]-a[i]=0) and (k=0) then

begin

c[i,j]:=a[i];

a[i]:=0;

b[j]:=0;

i:=i-1;

j:=j-1;

end;

if (i=0) or (j=0) then break;

until false;{Выводим решение}

clrscr;

for i:=1 to x do

begin

for j:=1 to y do

if j=y then write(c[i,j]:6,a1[i])

else

write(c[i,j]:6);

writeln;

end;

for j:=1 to y do

 write(b1[j]:6);

readln;

end.