Постановка транспортной задачи на ЭВМ

Содержание.

 

1.   Введение.……….……………………………………………………..2

 

2.   Формулировка транспортной

 

задачи.……….………………………………………………………..3

 

3.   Математическая модель

 

транспортной задачи. ……………………………………………3

 

4.   Необходимое и  достаточное условия

 

разрешимости транспортной задачи. ……………………….6

 

5.   Свойство системы  ограничений

 

транспортной задачи  …………………………………………...7

 

6.   Опорное решение  транспортной задачи. ……………………8

 

7.   Методы построения  начального опорного решения……….11

 

8.   Переход от одного  опорного решения к другому.  ………….12

 

9.   Распределительный  метод. …………………………………….14

 

10.            Метод потенциалов. ………………………………………15

 

11.            Особенности решения транспортных  задач с неправильным балансом. ………………………………………..16

 

12.            Алгоритм решения транспортной  задачи методом потенциалов. ………………………………………………………18

 

13.            Транспортная задача с ограничениями  на пропускную способность.  ……………………………………………………..19

 

14.            Транспортная задача по критерию  времени. ……….20

 

15.            Применение транспортной задачи  для решения экономических задач.  ……………………………………………21

 

16.            Пример транспортной задачи и  ее решение…………23

 

17.            Постановка транспортной задачи  на ЭВМ. …………

 

18.            Заключение. …………………………………………………

 

19.            Литература. …………………………………………….

 

 

 

 

 

 

 

Введение.

 

  Под названием  “транспортная  задача” объединяется широкий  круг задач с единой математической  моделью. Классическая транспортная  задача – задача о наиболее  экономном плане перевозок однородного  продукта или взаимозаменяемых  продуктов из пунктов производства  в пункты потребления, встречается  чаще всего в практических  приложениях линейного программирования. Линейное программирование является  одним из разделов математического  программирования – области математики, разрабатывающей теорию и численные  методы решения многомерных экстремальных  задач с ограничениями.

 

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

 

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

 

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

 

 

 

 

 

 

 

1. Формулировка транспортной  задачи.

 

   Однородный груз  сосредоточен у m поставщиков в объемах . Данный груз необходимо доставить n потребителям в объемах . Известны , i=1,2,,…,m, j=1,2,…,n- стоимости перевозки единицы груза от каждого I-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором запасы всех потребителей полностью удовлетворены и суммарные затраты на перевозку всех грузов минимальны.

 

   Исходные данные  транспортной задачи обычно записываются  в таблице (таб1.1).

 

 

 

 

… 

 

 

 

 

 

… 

 

 

 

 

 

… 

 

 

… 

… 

… 

…. 

….

 

 

 

 

… 

 

 

 

Таблица1.1.

 

   Исходные данные  задачи могут быть представлены  также в виде вектора запасов   поставщиков  А=(),   вектора   запросов  потребителей

 

В=() и матрицы стоимостей  .

 

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

 

2. Математическая модель  транспортной задачи.

 

  Переменными (неизвестными)  транспортной задачи являются  i=1,2,,…,m, j=1,2,…,n – объемы перевозок от каждого i-го поставщика каждому j-му потребителю. Эти переменные можно записать в виде матрицы перевозок

 

  .

 

  Так как произведение  определяет затраты на перевозку  груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны . По условию задачи требуется обеспечить минимум суммарных затрат. Следовательно, целевая функция имеет вид .

 

  Система ограничений  задачи состоит из двух групп  уравнений. Первая группа из  m уравнений описывает тот факт, что запасы всех m поставщиков вывозятся полностью:

 

,  i=1,2,…,m.

 

  Вторая группа из  n уравнений выражает требование полностью удовлетворить запросы всех n потребителей:

 

,  j=1, 2, … , n.

 

  Учитывая условие неотрицательности объемов перевозок, математическую модель задачи можно записать так:

 

,            (1)

 

,  i=1,2,…,m ,             (2)

 

                             

 

,  j=1, 2, … , n,             (3)

 

,    i=1,2,,…,m,   j=1,2,…,n    (4)

 

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

 

   Такая задача называется  задачей с правильным балансом, а ее модель – закрытой. Если  же это равенство не выполняется,  то задача называется задачей  с неправильным  балансом, а ее  модель – открытой.

 

   Математическая формулировка  транспортной задачи такова: найти  переменные задачи ,   i=1,2,,…,m,  j=1,2,…,n, удовлетворяющие системе ограничений (2), (3), условиям неотрицательности (4) и обеспечивающие минимум целевой функции (1).

 

   Математическая модель  транспортной задачи может быть  записана в векторном виде. Для  этого рассмотрим матрицу А системы уравнений-ограничений задачи (2), (3):

 

       

 

                     

 

     .……………………………………………………

 

А =                                (6).

 

     ……………………………………………………

 

                            

 

  Сверху над каждым  столбцом матрицы указана переменная  задачи, коэффициентами при которой  являются элементы соответствующего  столбца в уравнениях системы  ограничений. Каждый столбец матрицы  А, соответствующий переменной , является вектором-условием задачи и обозначается через . Каждый вектор имеет всего m+n координат, и только две из них, отличные от нуля, равны единице. Первая единица вектора стоит на i-м месте, а вторая – на (m+j)-м месте, т.е.

 

                Номер

 

                    корди-

 

                   наты

 

     =          ;    =    .

 

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

 

,              (7)

 

=,                     (8)

 

,    i=1,2,,…,m,   j=1,2,…,n    (9)

 

3. Необходимое и достаточное  условия разрешимости транспортной  задачи.

 

 

 

 

 

 

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

 

, т.е. задача должна  быть с правильным балансом.

 

Доказательство.Необходимость. Пусть задача имеет допустимое решение                  ,  i=1,2,,…,m,   j=1,2,…,n     . Докажем, что . Подставим     в   уравнения системы ограничений (2),  (3),  получим ,  i=1,2,,…,m, ,  j=1,2,…,n . Просуммируем первую и вторую группы тождеств по отдельности:  и . Отсюда следует, что задача имеет правильный баланс .

 

Достаточность. Пусть задача имеет правильный баланс =М. Докажем, что в этом случае задача имеет  оптимальное решение. Сначала убедимся в том, что  область допустимых решений задачи – непустое множество. Проверим, что =, i=1,2,,…,m,   j=1,2,…,n является допустимым решением. Подставим в левые части уравнений системы ограничений (2), (3), получим ==М=, i=1,2,,…,m;

 

==М=, j=1,2,…,n, т.е. уравнения обращаются в тождества. Очевидно, что удовлетворяет и условиям неотрицательности.

 

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

 

 

 

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

 

4. Свойство системы ограничений  транспортной задачи.

 

Теорема2. Ранг системы – условий транспортной задачи равен N=m+n-1.

 

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

 

.

 

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

 

Системе векторов – условий  транспортной задачи Aij , i=1,2,,…,m, j=1,2,…,n соответствует однородная система уравнений

 

,

 

 где =(0,0,…,0)т – нулевой  вектор (транспонированный).

 

Запишем матрицу этой системы (она является также матрицей системы  ограничений транспортной задачи):

 

    

 

                                

 

Если к последней строке (уравнению) прибавить (n-1) строку (уравнение), начиная с (m+1)-й, и вычесть первые m строк, то получится строка, состоящая из нулей. Это значит, что число разрешенных неизвестных в этой системе и ранг r системы векторв-условий не могут быть равны числу m+n уравнений. Следовательно, rm+n-1.

 

Покажем, что найдутся N=m+n-1 линейно независимых векторов-условий. Из векторов-условий задачи выберем  следующие:  - и убедимся, что они  линейно независимы. Для этого  составим систему уравнений . Матрица этой системы имеет следующий вид:

 

 

Применение транспортной задачи для решения

 

экономических задач.

 

Задача о размещении производства

 

с учетом транспортных затрат.

 

Имеется (проектируется) m пунктов производства с объемами производства  и n пунктов потребления с объемами потребления . Затраты на производство единицы продукции в каждом i-м пункте производства известны и равны , i=1,2,…,m. Стоимости перевозки единицы груза от каждого i–го производителя каждому j–му потребителю известны и равны , i=1,2,,…,m,   j=1,2,…,n.  Суммарные объемы производства превосходят суммарные объемы потребления. Требуется составить план сокращения (размещения) производства, обеспечивающий минимальные производственно-транспортные затраты.

 

Задача решается как транспортная задача, матрица стоимостей которой  составляется как сумма матриц:

 

С=()=(+), i=1,2,,…,m,   j=1,2,…,n.

 

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

 

Задача о назначениях, или проблема выбора.

 

Имеется  m групп людей (станков) численностью  , которые должны выполнять n видов работ (операций) объемом . Известна производительность каждой i–й группы людей (станков) при выполнении каждого j–го вида работ (операций) , i=1,2,,…,m,   j=1,2,…,n.  . Требуется так распределить людей (станки) для выполнения работ (операций), чтобы суммарный объем производства работ (операций) был максимальным.

 

Составим математическую модель данной задачи по аналогии с  транспортной задачей. Обозначим  - число людей (станков) i–й группы, занятых j–го  вида  работ  (операций). Запишем  математическую  модель   

 

,                    (30) 

 

    ,  i=1,2,…,m ,                   (31)

 

                             

 

   ,  j=1, 2, … , n,                   (32)

 

   ,    i=1,2,,…,m,   j=1,2,…,n.          (33)

 

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

Можно также изменить критерий оптимальности. Например, вместо  (i,j) использовать новый критерий оптимальности (i,j).

 

Технические науки/4. Транспорт

 

Косова Е.Г.

 

Карагандинский экономический  университет Казпотребсоюза, Казахстан

 

Применение транспортных задач для решения 

 

экономических задач.

 

Задача о размещении производства с учетом транспортных затрат.

 

Имеется (проектируется) m пунктов производства с объемами производства   и n пунктов потребления с объемами потребления . Затраты на производство единицы продукции в каждом i-м пункте производства известны и равны , i=1,2,…,m. Стоимости перевозки единицы груза от каждого i–го производителя каждому j–му потребителю известны и равны , i=1,2,,…,m,    j=1,2,…,n.  Суммарные объемы производства превосходят суммарные объемы потребления. Требуется составить план сокращения (размещения) производства, обеспечивающий минимальные производственно-транспортные затраты.