Общий объем перевозок в тонно-километрах для этого плана составит

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

Пример.



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

. Пола­гая , вписываем это значение в клетку  и исключаем из рассмотрения второй столбец. На базе  остается изменённый запас . В оставшейся новой таблице с тремя строками  и четырьмя столбцами  клеткой с наименьшим значе­нием  клетка, где. Заполняем описанным выше способом эту клетку и аналогично заполняем следующие клетки. В резуль­тате оказываются заполненными (в приведенной последовательности) следующие клетки:
.

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

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

    Кроме рассмотренных выше способов иногда используется, так называемый, метод Фогеля. Суть его состоит в следующем: В распределительной таблице по строкам и столбцам определяется разность между двумя наименьшими тарифами. Отмечается наибольшая разность. Далее в строке (столбце) с наибольшей разностью заполняется клетка с наименьшим тарифом. Строки (столбцы) с нулевым остатком груза в дальнейшем в расчет не принимаются. На каждом этапе загружается только одна клетка. Распределение груза производится, как и ранее.
1.5 Методы решения транспортной задачи
1.5.1 Метод потенциалов.

 При решении методом потенциалов необходимо:

1)   Построить опорный план таблицы;

2)   Провести ноль-преобразование в таблице тарифов. Если в результате ноль-преобразования имеются отрицательные тарифы, то переходим к следующему пункту, если нет, задача решена оптимально;
3)   Строим новое решение, в котором стоимость перевозки будет меньше в исходной таблице тарифов следующим способом: выбираем клетку с наименьшим отрицательным тарифом и строим замкнутый контур, в углах которого будут клетки с перевозками.
1.5.1.1 Пример решения задачи методом потенциалов.

Дана задача:

Вывозится продукция из 3 пунктов: A₁₌400, A₂₌970, A₃₌560;

Потребности в населенных пунктах: B₁₌540, B₂₌170, B₃₌980, B₄₌240;

Тарифы из:  C_1,1=3,  C_1,2=5,  C_1,3=3,  C_1,4=5;

                                           C_2,1=3,   C_2,2=4,  C_2,3=5,  C_2,4=2;

                                                      C_3,1=3,  C_3,2=2,  C_3,3=4,  C_3,4=2;

1) Опорный план. В данном примере мы строим опорный план методом наименьшей стоимости(см. стр.11):
















Найдем целевую функцию:

S
₁
= 400*3 + 140*3 + 170*4 + 420*5 + 240*2 + 560*4 = 7120;


2)Проведем ноль–преобразование таблицы тарифов(см. стр.7-8):

X₁+Y₁=-3;                 X₂=0;                        Y₁=-3;

X₂+Y₁=-3;                 X₁=2;                        Y₂=-4;

X₂+Y₂=-4;                 X₃=1;                        Y₃=-5;

X
₂
+
Y
₃
=-5;                                                 
Y
₄
=-2;

X
₂
+
Y
₄
=-2;                                                 

X
₃
+
Y
₃
=-4;                                                 
3)Построим замкнутый контур:


                                                В клетках с перевозками находятся                                                                                            нулевые стоимости, но в остальных

 еще есть отрицательные стоимости т.е.

 проводим еще раз ноль-преобразование.

И так до тех пор, пока не останется

отрицательных тарифов.
X₁+Y
₃
=-3             X₂=0;     Y₁=-3;

X
₂
+
Y
₁
=-3;           
X
₁
=-2;   
Y
₂
=-4;

X
₂
+
Y
₂
=-4;           
X
₃
=1;    
Y
₃
=-5;

X₂+Y₃=-5;                          Y₄=-2;

X₂+Y₄=-2;                                                          

X₃+Y₃=-4;               



X₁+Y₃=-3             X₂=0;     Y₁=-3;

X₂+Y₁=-3;            X₁=-2;    Y₂=-4;

X₂+Y₂=-4;            X₃=1;     Y₃=-5;

X₂+Y₃=-5;                          Y₄=-2;

X₂+Y₄=-2;                                                          

X₃+Y₃=-4;               

В итоге у нас не осталось

отрицательных тарифов и

все клетки с перевозками обладают нулевыми тарифами, вывод это оптимальное решение.




Находим целевую функцию:

S
₁
= 400*3 + 540*3 + 190*5 + 240*2 + 170*2 + 390*4 =6150;
[5]1.5.2 Метод прямоугольников.

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

Прямоугольники бывают трех типов:

1)   обе диагонали не пустые;

2)   одна диагональ полная, а вторая имеет одну нулевую перевозку;

3)   одна диагональ полная, а другая пустая.

Прямоугольник у которого суммы тарифов по одной и по другой диагонали равны, называется нейтральным.

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

Теорема.

Стоимость перевозки по неправильному прямоугольнику всегда больше, чем по правильному.

[6]Правила решения транспортной задачи методом прямоугольника.

1)   Построить опорный план задачи;

2)    Выписать все неправильные прямоугольники;

3)   Определить мощности неправильных прямоугольников и выбрать прямоугольник наибольшей мощности;

4)   Заменить прямоугольник наибольшей мощности на правильный и подставить его в таблицу, получив новое решение;

5)   Перейти к пункту 2 до тех пор, пока, не останется ни одного неправильного прямоугольника в таблице;

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

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



Мощность

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

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

1.5.2.1 Пример решения задачи методом прямоугольника.
Дана задача:

Вывозится продукция из 3 пунктов: A₁₌400, A₂₌970, A₃₌560;

Потребности в населенных пунктах: B₁₌540, B₂₌170, B₃₌980, B₄₌240;

Тарифы из:  C_1,1=3,  C_1,2=5,  C_1,3=3,  C_1,4=5;

                                           C_2,1=3,   C_2,2=4,  C_2,3=5,  C_2,4=2;

                                                      C_3,1=3,  C_3,2=2,  C_3,3=4,  C_3,4=2;

1)Опорный план. В данном примере мы строим опорный план методом наименьшей стоимости:



















S
₁
= 400*3 + 140*3 + 170*4 + 420*5 + 240*2 + 560*4 = 7120;

2)Выпишем все неправильные прямоугольники:

    1)                                2)
3)Наедем их мощность

     1) М=(7-6)*400=400

     2) М=(8-6)*400=80

Заменяем неправильный прямоугольник наибольшей мощности на правильный. И далее ищем все неправильные прямоугольники, если их несколько, выбираем наибольшей мощности и меняем на правильный и так до тех пор пока не останется неправильных прямоугольников :
                                                                                 
Если неправильных нет,  проводим ноль-преобразование:

                                                             

X₁+Y₃=-3             X₂=0;     Y₁=-3;

X₂+Y₁=-3;            X₁=-2;    Y₂=-4;

X₂+Y₂=-4;            X₃=1;     Y₃=-5;

X
₂
+
Y
₃
=-5;                         
Y
₄
=-2;

X
₂
+
Y
₄
=-2;                                                          

X
₃
+
Y
₃
=-4;               

В итоге у нас не осталось отрицательных тарифов и все клетки с перевозками обладают нулевыми тарифами, вывод это оптимальное решение.

Находим целевую функцию:

S
₁
= 400*3 + 540*3 + 190*5 + 240*2 + 170*2 + 390*4 =6150;

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

В этом разделе мы рассмотрим решение транспортной задачи с помощью Microsoft Office Excel.

Нам дана задача:
Для решения транспортной задачи в Excel нужно:

Ø    Если у нас 3 поставщика и 4 покупателя, то на листе Excel в ячейки A1:D3 вводятся тарифы:
Ø    Диапазон ячеек A5:D7 отводятся под значения неизвестных перевозок т.е. плана перевозки грузов, они не указываются, но указываются в окне диолога как изменяемые ячейки
Ø    В ячейки F5:F7 вводим количество вывозимого товара, а в ячейки A9:D9 – потребности ввозимого товара.
Ø    В ячейки A8:D8 вводятся формулы суммы изменяемых ячеек соответствующего столбца, и так все столбцы (автосумма), а в ячейки E5:E7 вводятся суммы изменяемых ячеек по строкам.
Ø    В ячейку F9 вводится целевая функция которая равна суммпроизв(A1:D3;A5:D7) тарифов на соответствующие перевозки.
Ø    Далее выбираем МЕНЮ      ПОИСК РЕШЕНИЯ

В целевую ячейку устанавливаем F9 делаем её равной минимальному значению, в строке ИЗМЕНЯЕМЫЕ ЯЧЕЙКИ вводим A5:D7, далее вводим ограничения: A5:D7 >= 0,

A8:D8 = A9:A9, E5:E7 = F5:F7. В этом же окне выбираем вкладку ПАРАМЕТРЫ и ставим галочку на линейную модель .
Ø    После нажатия кнопки Выполнить, в ячейках A5:D7 отобразится оптимальный план перевозки грузов, а в ячейке F9 – минимальная стоимость перевозки т.е. оптимальное решение.
7. Описание входной информации.

Входные данные вводятся с клавиатуры:

      Вводится прямоугольник:

ü  Вводятся перевозки X_1,1 , X_1,2 , X_2,1 , X_2,2 .

ü  Вводится стоимость C_1,1 , C_1,2 , C_2,1 , C_2,2 .

В данном примере
ü  Вводятся перевозки 400 , 0 , 140 , 420 .

ü  Вводится стоимость 3 , 3 , 3 , 5 .
8. описание выходной информации.

Информация выводится на экран в виде таблицы с введенными данными и еще одной таблицы уже с правильным решением.



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

Язык Паскаль, названный в честь французского математика и философа Блеза Паскаля (1623-1662), был создан как учебный язык программирования в 1968-71 годах швейцарским ученым Николаусом Виртом на кафедре информатики Стэндфордского университета (Цюрих). В настоящее время это язык имеет более широкую сферу применения, чем предусматривалось при его создании. Свое признание Паскаль получил с появлением пакета Турбо Паскаль (Turbo Pascal). Этот язык отличается простотой понимания, стройностью и структурностью алгоритмов, быстротой компилятора и удобными средствами создания и отладки программ.

Достоинствами языка Паскаль являются:
Простой синтаксис языка. Небольшое число базовых понятий. Программы на Паскале достаточно легко читаемы. Достаточно низкие аппаратные и системные требования, как самого компилятора, так и программ, написанных на Паскале. Универсальность языка. Язык Паскаль применим для решения практически всех задач программирования. Поддержка структурного программирования, программирования "сверху-вниз", а также объектно-ориентированного программирования. В настоящем пособии рассматривается Turbo Pascal v7.0. Данная версия разработана фирмой Borland и является последней в линейке компиляторов Pascal для DOS. Дальнейшее развитие Паскаль получил в Delphi - системе разработки программ для Windows.
Окно среды разработчика

Основной экран интегрированной среды разработчика Turbo Pascal 7.0 выглядит следующим образом:

По функциональному назначению выделяется три области экрана:

1)    Строка меню

2)    Рабочая область

3)    Строка состояния
10. Инструкция для пользователя.
Общие сведения:

Программа производит вычисления выбранного прямоугольника, определяет его тип и мощность.
Управление:

Данные вводятся с клавиатуры:

При запуске задачи, появляется диалоговое окно с приветствием, в котором, предлагается продолжить дальше, нажав клавишу «1» и «Enter» , либо выйти нажав  «0» и «Enter».

Далее пользователь вводит перевозки X_1,1 , X_1,2 , X_2,1 , X_2,2 .После нажатия клавиши «Enter» пользователь вводит стоимость C_1,1 , C_1,2 , C_2,1 , C_2,2 , и жмем «Enter», после чего на экране появляются прямоугольник с вводимыми данными, его тип, мощность и еще один уже решенный прямоугольник.

После этого пользователю предлагается попробовать еще раз, нажав «1» и «Enter» либо выйти из программы, нажав   «0» и «Enter».Так же во время работы программы предлагается ввести «-1» и «Enter», для выхода или «-2» и «Enter», для перезапуска программы.


11. Инструкция для программиста
Данная программа реализуется с помощью процедурного языка Turbo Pascal 7.0, используется текстовый режим.
ТРЕБУЕМЫЕ ИНФОРМАЦИОННО–ВЫЧИСЛИТЕЛЬНЫЕ СРЕДСТВА:
1)               техническое обеспечение: IBM PC\XT совместимые машины

а) оперативная память – не менее 8Мб

б) свободное место на жестком диске – не менее 60Кб

в) центральный процессор – от Intel 8088 до семейства Pentium или совместимых с ним

2) информационные средства для нормального функционирования программы достаточно иметь информационную систему MS DOS
ЗАКЛЮЧЕНИЕ

Транспортная задача делится на два вида: транспортная задача по критерию стоимости- определение плана перевозок, при котором стоимость груза была бы минимальна; транспортная задача по критерию времени- более важным является выигрыш по времени.

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

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

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

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


СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1.      Общий курс высшей математики для экономистов. Учебник / под ред В.И. Ермакова.- М.: ИНФА – М. – 656 с. – (серия «высшее образование»).

2.     Сборник задач и упражнений по высшей математике: математическое программирование: учебник пособие / А.В. Кузнецов, В.А. Сакович, Н.И. Холод и др; МН.: выш. ик., 2002. – 447с.:ил.

3.     Т.Л. Партыкина, И.И. Попов Математические методы: учебник. – М.: ФОРУМ: ИНФА-М, 2005. – 464 с.: ил – (профессиональное образование)

4.      И.Г. Семакин Основы программирования: учебник для сред. проф. Образования / И.Г. Семакин, А.П.Шестаков. – 2-е изд., стер,- М.: Издательский центр «Академия», 2003.-432 с.

5.     Г.С. Малик Основы экономики и математические методы в планировании. Москва Высшая школа 1988 г.

6. А.А. Глаголев, Т.В. Солнцева  Курс высшей математики Москва Высшая школа 1971 г.


ПРИЛОЖЕНИЕ А

program zadacha;

uses crt;

const w=('_____________');

const e=('-------------');

label q;

var

 a,a1,b,b1,c,c1,d,d1,a2,b2,c2,d2,m,n,x,s1,s2: integer;

 begin

 clrscr;

 writeln('Здравствуйте!');

 writeln('Вас приветствует программа решения   транспортной задачи методом прямоугольника - TranZet, ver 1/1');

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

 begin 

   writeln('введите 1 - продолжить, 0 - выйти');

     readln(n);

       if n = 1 then
goto q end; exit;

 a:=0; b:=0; c:=0; d:=0; x:=0; m:=0;

 q:writeln;

 writeln('введите перевозки X1,1 , X1,2 , X2,1 , X2,2');

   writeln('Для выхода из программы нажмите -1, чтобы начать сначала начала нажмите -2');

    readln(a); begin if (a=-1) then exit;if a=-2 then
goto q end;

    readln(b); begin if (b=-1) then exit;if b=-2 then
goto q end;

    readln(c); begin if (c=-1) then exit;if c=-2 then
goto q end;

    readln(d); begin if (d=-1) then exit;if d=-2 then
goto q end;

 writeln('введите тарифы С1,1 , C1,2 , C2,1 , C2,2');

   writeln('Для выхода из программы нажмите -1, чтобы начать сначала начала нажмите -2');

    readln(a1); begin if (a1=-1) then exit;if a1=-2 then
goto q end;

    readln(b1); begin if (b1=-1) then exit;if b1=-2 then
goto q end;

    readln(c1); begin if (c1=-1) then exit;if c1=-2 then
goto q end;

    readln(d1); begin if (d1=-1) then exit;if d1=-2 then
goto q end;

 writeln;

 writeln('НАШ ПРЯМОУГОЛЬНИК');

 writeln(w);

 writeln('|   |',a1,'|   |',b1,'|');

 writeln('|',a:5,'|',b:5,'|');

  writeln(e);

 writeln('|   |',c1,'|   |',d1,'|');

 writeln('|',c:5,'|',d:5,'|');

 writeln(e);

 begin

  if (a>0) and (b>0) and (c>0) and (d>0) and ((a1+d1)<>(b1+c1))then writeln('первый тип - неправильный')else

    if (a=0) and (d=0) and ((a1+d1)<(b1+c1)) then begin writeln('третий тип - неправильный');

          if (b>c) then x:=c else x:=b;  a2:=a+x; b2:=b-x; c2:=c-x; d2:=d+x; m:=((b1+c1)-(a1+d1))*x; writeln('МОЩНОСТЬ = ',M); end else

      if (c=0) and (b=0) and ((b1+c1)<(a1+d1)) then begin writeln('третий тип - неправильный');

            if (a>d) then x:=d else x:=a; a2:=a-x; b2:=b+x; c2:=c+x; d2:=d-x; m:=((a1+d1)-(b1+c1))*x;writeln('МОЩНОСТЬ = ',M); end else

        if (a=0) and ((a1+d1)<(b1+c1)) then begin writeln('второй тип - неправильный');

              if (b>c) then x:=c else x:=b; a2:=a+x; b2:=b-x; c2:=c-x; d2:=d+x; m:=((b1+c1)-(a1+d1))*x;writeln('МОЩНОСТЬ = ',M); end else

          if (b=0) and ((b1+c1)<(a1+d1)) then begin writeln('второй тип - неправильный');

                if (a>d) then x:=d else x:=a; a2:=a-x; b2:=b+x; c2:=c+x; d2:=d-x; m:=((a1+d1)-(b1+c1))*x;writeln('МОЩНОСТЬ = ',M); end else

            if (c=0) and ((b1+c1)<(a1+d1)) then begin writeln('второй тип - неправильный');

                  if (a>d) then x:=d else x:=a; a2:=a-x; b2:=b+x; c2:=c+x; d2:=d-x; m:=((a1+d1)-(b1+c1))*x; writeln('МОЩНОСТЬ = ',M);end else

              if (d=0) and ((a1+d1)<(b1+c1)) then begin writeln('второй тип - неправильный');

                    if (b>c) then x:=c else x:=b; a2:=a+x; b2:=b-x; c2:=c-x; d2:=d+x; m:=((b1+c1)-(a1+d1))*x; writeln('МОЩНОСТЬ = ',M);end

                                                                                                                     else begin writeln('правильный');

   writeln;

   writeln;

   writeln('НАШ РЕШЕННЫЙ ПРЯМОУГОЛЬНИК');

   writeln(w);

   writeln('|   |',a1,'|   |',b1,'|');

   writeln('|',a:5,'|',b:5,'|');

   writeln(e);

   writeln('|   |',c1,'|   |',d1,'|');

   writeln('|',c:5,'|',d:5,'|');

   writeln(e);

     begin

        writeln('Нажмите 0 - чтобы выйти, нажмите 1 - чтобы повторить');

            readln(n);

                 if n = 1 then
goto q end; exit; end

 end;

   writeln;

   writeln;

   writeln('НАШ РЕШЕННЫЙ ПРЯМОУГОЛЬНИК');

   writeln(w);

   writeln('|   |',a1,'|   |',b1,'|');

   writeln('|',a2:5,'|',b2:5,'|');

   writeln(e);

   writeln('|   |',c1,'|   |',d1,'|');

   writeln('|',c2:5,'|',d2:5,'|');

   writeln(e);

     begin

        writeln('Нажмите 0 - чтобы выйти, нажмите 1 - чтобы повторить');

            readln(n);

                 if n = 1 then
goto q end; exit;

  readln;

end.