Транспортная задача

 

Теорема.

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

 
 

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

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) либо с помощью специальной программы.

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

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

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