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

Содержание.

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 соответствует однородная система уравнений

 

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

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

       

                                                           

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

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

  

                                                                +

         

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

                  

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

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

  Ввиду того, что ранг системы векторов-условий транспортной задачи равен m+n-1, опорное решение не может иметь отличных от нуля координат более m+n-1. Число отличных от нуля координат невырожденного опорного решения равно m+n-1,а для вырожденного опорного решения меньше m+n-1

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

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

Циклом называется такая последовательность клеток таблицы транспортной задачи (i1,j1), (i1,j2), (i2,j2), … , (ik,j1), в которой две и только две соседние клетки расположены в одной клетке или столбце, причем первая и последняя клетки также находятся в одной строке или столбце.

Цикл изображают в таблице транспортной задачи в виде замкнутой ломаной линии. В любой клетке цикла происходит поворот звена ломаной линии на 900. Простейшие циклы изображены на рис1, где звездочкой отмечены клетки таблицы, включенные в состав цикла.

*               *      *           *                    *           *

                         *                       *                     *                        *

     *               *                   *           *       *                                     *

рис1.

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

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

                  (10)

Пусть  имеет две равные единице координаты с номерами  и m+m+

В выбранной подобным образом последовательности векторов должен найтись вектор i1,j1), (i1,j2), (i2,j2), … , (ik,j1), которая образует цикл.

Достаточность. Пусть из соответствующих векторов  клеток (i,j)  выбрана последовательность клеток, образующих цикл  (i1,j1), (i1,j2), (i2,j2), …, (ik,j1). Нетрудно видеть, что      

Отсюда следует линейная зависимость рассматриваемой системы векторов. Теорема доказана полностью.      

Следствие. Допустимое решение транспортной задачи Х=(   i=1,2,,…,m,  j=1,2,…,n         является опорным тогда и только тогда, когда из занятых им клеток таблицы нельзя образовать ни одного цикла.      

Метод вычеркивания

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

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

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

Ниже приведены примеры “вычеркиваемого” (опорного) и ”невычеркиваемого” (неопорного) решений:

            

 

      “вычеркиваемое”            “невычеркиваемое”

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

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

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

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

1.     если  и исключается поставщик с номером i, k=1, 2, …, n, k,

2.     если  и исключается потребитель с номером j, k=1, 2, …, m, k,

3.     если  и исключается либо i-й поставщик, k=1, 2, …, n, k, j-й потребитель, k=1, 2, …, m, k,

Нулевые перевозки принято заносить в таблицу только тогда, когда они попадают в клетку (i,j), подлежащую заполнению. Если в очередную клетку таблицы (i,j) требуется поставить перевозку, а  i-й поставщик или j-й потребитель имеет нулевые запасы или запросы, то в клетку ставится перевозка, равная нулю (базисный нуль), и после этого, как обычно, исключается из рассмотрения соответствующий поставщик или потребитель. Таким образом, в таблицу заносят только базисные нули, остальные клетки с нулевыми перевозками остаются пустыми.

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

Теорема4. Решение транспортной задачи, построенное методом северо-западного угла, является опорным.

Доказательство. Число занятых опорным решением клеток таблицы должно быть равно N=m+n-1. на каждом шаге построения решения по методу северо-западного угла заполняется одна клетка и исключается из рассмотрения одна строка (поставщик) или один столбец (потребитель) таблицы задачи. Через m+n-2 шага в таблице будет занято m+n-2 клетки. В то же время останутся невычеркнутыми одна строка и один столбец, при этом незанятая клетка одна. При заполнении этой последней клетки число занятых клеток составит m+n-2+1=m+n-1.

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

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

Метод минимальной стоимости.

Метод минимальной стоимости прост, он позволяет построить опорное решение, достаточно близкое к оптимальному, так как использует матрицу стоимостей транспортной задачи С=(i=1,2,,…,m,  j=1,2,…,n. Как и метод северо-западного угла, он состоит из ряда однотипных шагов, на каждом из которых заполняется только одна клетка таблицы, соответствующая минимальной стоимости min {

Теорема5. Решение транспортной задачи, построенное методом минимальной стоимости, является опорным.

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

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

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

Доказательство. Опорное решение занимает N=m+n-1 клеток таблицы, которым соответствуют линейно независимые векторы-условия. Если же к занятым клеткам присоединить одну свободную, то соответствующие им m+n векторов линейно зависимы, и по той же теореме существует цикл, содержащий эту клетку. Предположим, что таких циклов два  (i1,j1), (i1,j2), (i2,j2), …, (ik,j1) и (i1,j1), (i2,j1), …, (i1,ji). Тогда, объединив клетки обоих циклов без свободной клетки  (i1,j1), получим последовательность клеток  (i1,j2), …, (ik,j1), (i2,j1), …, (i1,ji), которые образуют цикл. Это противоречит линейной независимости векторов-условий, образующих базис опорного решения. Следовательно, такой цикл единственный.

Означенный цикл.

Цикл называется означенным, если его угловые клетки пронумерованы по порядку и нечетным клеткам приписан знак «+», а четным – знак «-» (рис 2.)                         1          2    

                          +           -

                          -                         5   +

                            6

                                      +               -    

3                       4  

рис 2.

Сдвигом по циклу на величину  называется увеличение объемов перевозок во всех нечетных клетках цикла, отмеченных знаком «+», на  и уменьшение объемов перевозок во всех четных клетках, отмеченных знаком «-», на

Теорема7. Если таблица транспортной задачи содержит опорное решение, то при сдвиге по любому циклу, содержащему одну свободную клетку, на величину  получится опорное решение.

Доказательство. В таблице транспортной задачи, содержащей опорное решение, выберем свободную клетку и отметим ее знаком «+». По теореме6. для этой клетки существует единственный цикл, который содержит часть клеток, занятых опорным решением. Пронумеруем клетки цикла, начиная с клетки, отмеченной знаком «+». Найдем  и осуществим сдвиг по циклу на эту величину.

В каждой строке и в каждом столбце таблицы, входящих в цикл, две и только две клетки, одна из которых отмечена  знаком «+», а другая - знаком «-». Поэтому в одной клетке объем перевозки увеличивается на  

Если оставить свободной одну из клеток с нулевым объемом перевозки, соответствующих N=m+n-1. Так как цикл единственный, то удаление из него одной клетки разрывает его. Цикл из оставшихся занятых клеток образовать нельзя, соответствующие векторы-условия линейно независимы, а решение является опорным.

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

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

Пусть для транспортной задачи найдено начальное опорное решение  и вычислено значение целевой функции на этом решении Z(2.

Определим, как изменится целевая функция при переходе к новому опорному решению. При сдвиге на единицу груза по циклу, соответствующему клетке (l, k), приращение целевой функции  равно разности двух сумм:  - сумма стоимостей перевозок единиц груза в нечетных клетках цикла, отмеченных знаком  «+»,  - сумма стоимостей перевозок единиц груза в четных клетках цикла, отмеченных знаком  «-».

В клетках, отмеченных знаком  «+», величины груза прибавляются, что приводит к увеличению значения целевой функции Z(  знаком  «-», величины груза уменьшаются, что приводит к уменьшению значения целевой функции.

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

Для решения транспортной задачи распределительным методом необходимо найти начальное опорное решение. Затем для очередной опорной клетки (l, k) построить цикл и вычислить оценку

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

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

Широко распространенным методом решения транспортных задач является метод потенциалов. Этот метод позволяет упростить наиболее трудоемкую часть вычислений – нахождение оценок свободных клеток.

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

 при          (12)

  при         (13)

Доказательство.  Используем вторую теорему двойственности. Запишем математическую модель  транспортной задачи    

,   i=1,2,,…,m,   

 ,  j=1,2,…,n,      

   0,   i=1,2,,…,m,  j=1,2,…,n.

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

F(U, V)=, +,  i=1,2,,…,m,  j=1,2,…,n.

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

Группа равенств (12)  при  или

Данная система уравнений имеет m+n неизвестных    i=1,2,,…,m и   j=1,2,…,n. Число уравнений системы, как и число отличных от нуля координат невырожденного опорного решения, равно m+n-1. так как число неизвестных системы на единицу больше числа уравнений, то одной из них можно задать значение произвольно, а остальные найти из системы.

Группа неравенств (13)   при  при                           (14)

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

Оценки для свободных клеток транспортной таблицы используются для улучшения опорного решения. С этой целью находят клетку (k, l) таблицы, соответствующую max{k, l) строят цикл и улучшают решение, перераспределяя груз   по этому циклу.

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

До сих пор рассматривались транспортные задачи с правильным балансом. Однако на практике чаще встречаются задачи с неправильным балансом. Каковы особенности их решения?

1. Пусть суммарные запасы поставщиков превосходят суммарные запросы потребителей, т.е.    i=1,2,…,m.                         (15)

Вторая группа уравнений остается без изменения, так как запросы всех потребителей удовлетворяются полностью. Для приведения к канонической форме в неравенства (15) вводят дополнительные переменные m ограничений задачи принимают вид    i=1,2,…,m.

В целевую функцию дополнительные переменные не входят (входят с нулевыми коэффициентами). Математическая модель задачи принимает вид                    (16)    

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

                                                             

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

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

Запишем необходимое и достаточное условие разрешимости задачи (см. теорему1):

Отсюда

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

2. Аналогично в случае, когда суммарные запросы потребителей превосходят суммарные запасы поставщиков,  т.е.     останется  не удовлетворенной. Поэтому вторая группа уравнений системы ограничений (3) транспортной задачи заменяется неравенствами j=1, 2, … , n. 

После введения дополнительных переменных  в эти неравенства математическая модель задачи примет вид                    (20)    

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

                                                             

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

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

Для того чтобы задача имела решение, необходимо и достаточно, чтобы

 Отсюда

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

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

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

Порядок решения транспортной задачи методом потенциалов следующий.

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

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

3.                     Строят систему потенциалов, соответствующих опорному решению. Для этого решают систему уравнений  при   при                    (24)

4если известен потенциал

 при                                         (25)

если известен потенциал  

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

5.                     Переходят к новому опорному решению, на котором значение целевой функции будет меньше. Для этого находят клетку таблицы задачи, которой соответствует наибольшая положительная оценка max{«+» и «-», начиная с «+» в клетке с наибольшей положительной оценкой. Осуществляют сдвиг (перераспределение груза) по циклу на величину «-», в которой достигается  , остается пустой. Если минимум достигается в нескольких клетках, то одна из них остается пустой, а в остальных проставляют базисные нули, чтобы число занятых клеток оставалось равным m+n-1. Далее возвращаемся к пункту 3 алгоритма.

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

Пусть требуется при решении транспортной задачи ограничить перевозки от поставщика с номером l к потребителю с номером k. Возможны ограничения двух типов: 1)  и  - постоянные величины.

1. если   l-го поставщика и запросы k-го потребителя на оптимальном решении следует увеличить объем перевозки  на величину

2. если k-го потребителя с запросами  ввести двух других потребителей. Один из них с номером k должен иметь запросы n+1 – запросы n+1)-му потребителю, прибавляются к величинам перевозок k-го потребителя. Так как l, n+1) останется пустой,  не превзойдет

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

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

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

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

Т(Х)=                                   (26)

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

                                                             

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

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

Задача решается в следующем порядке. Находится начальное опорное решение Х1. определяется значение целевой функции Т(Х1)=T(X1), исключаются из рассмотрения (перечеркиваются). Занимать эти клетки нецелесообразно, так как повысится значение целевой функции. Чтобы понизить ее значение, необходимо освободить клетку (l1, k1), в которой  достигает максимума. Для этого строят так называемые разгрузочные циклы, которые могут включать в свой состав несколько свободных клеток. В каждом разгрузочном цикле, начиная с разгружаемой клетки  (l1, k1), расставляются поочередно знаки «-» и  «+» и осуществляется сдвиг на величину 2, на котором значение целевой функции меньше, чем на Х1. далее снова пытаются разгрузить клетку, соответствующую Т(Х2)=

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

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

 

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

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

Имеется (проектируется) 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).

                                                                                                        

                    

                

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

Программа решения транспортной задачи нетривиальна. Для облегчения понимания мы разбили эту программу на части. Приведем сначала блок-схему решения транспортной задачи (рис1.1).

Теперь приведем блок-схему определения первого допустимого базисного решения строки (500-840) (рис1.2).

В конце этой процедуры все элементы массива DA(I) и DB(J) должны быть равны 0. Переменные TR(I) и TC(I) должны быть равны количеству переменных соответственно в I-й строке и в J-м столбце.

В следующей процедуре (строки 1000 – 1585) вычисляются u и v и наименьшее значение сij, предположим сkl (рис1.3).

Ввести m,n

 

Задать начальные значения элементам

массивов хij; сij; аi,bj, ui, vj, а также

счетчикам и рабочим массивам

вычислить базисное допустимое

решение по правилу “самая

дешевая продукция реализу-

                                                  ется первой”

вычислить коэффициенты

 и   для базисного

допустимого решения

найти  для небазисных                 перейти к базисному

переменных                        допустимому решению                      

                         все ли                  нет

      

           Да

Оптимальное решение получено

Рис1.

Процедура перехода к новому базисному допустимому решению (начиная со строки 2000 до строки 3250) заслуживает внимательного изучения. Поясним ее подробнее. Сначала находим “цепь” клеток, которая не является “тупиковым путем” (строки 2050 – 2730).

Найти наименьший элемент C(I,J)

текущего массива C(RI,CJ)

                                                   

                                                  нет

      DA(RI)0<DB(CJ)?

                        да    

Проверить, что удалено не более М-1                  Положим X(RI,CJ)=DB(CJ) и

строк. Положить X(RI,CJ)=DA(RI) и                  пометить этот элемент как

пометить этот элемент как базисный.              базисный. Заменить DA(RI)

Заменить DB(CJ) на DB(CJ)-DA(RI).                    на DA(RI)-DB(CJ). Удалить

Удалить строку RI и подсчитать                        столбец и посчитать количество

количество удалений                                               удалений  

                                                                                             

                             нет

   Увеличить TR(RI) и TC(CJ) на 1

 

 Количество базисных

  переменных меньше

    чем М+N-1?

  Введите следующую программу

   для определения u и v

               Рис2.

На шаге 1 мы находимся в клетке (K,L), T  - счетчик шагов, IP – индикатор “тупикового пути”, (RT(T), CT(T))RI,CJ) – клетка, в которую мы попадаем на шаге Т.  Массив  D состоит из 1, соответствующих ; положим ММ=1, если клетка используется, IU=1 и IV=1, если строки и столбцы входят в цикл.

В команде 2100 на шаге Т ищется строка RT(T) для столбца, содержащего базисную переменную в неиспользованном столбце (строка 2140) в неотмеченной клетке (строка 2150). Если это единственная переменная в своем столбце, то производится присваивание IP=1 (строка 2170). Разумеется, это не делается в начальном столбце L. После того  как подходящая переменная найдена в столбце CJ, поиск прекращается; при этом FC=1.

Затем T увеличивается для следующего шага, в переменную RT(T) заносится номер текущей строки, а в переменную СT(T) – номер только что найденного столбца CJ; соответствующему D присваивается  значение –1,  и найденная клетка помечается присвоением ММ значения 1 (строка 2320). Если мы снова оказались в столбце L, откуда начали, то цикл завершен (строка 2400). В противном случае ищем столбец СT(T)[ J] для строки, содержащей базисную переменную в неотмеченных строке и клетке; таким образом снова помечаются “тупиковые пути”. Как только искомый столбец найден, поиск прекращается присвоением FR=1. Затем T увеличивается для следующего шага, переменной RT(T) присваивается номер только что найденной строки RI, а CT(T) - -номер только что обрабатывавшегося столбца; для этой клетки осуществляются присвоения: D=+1, MM=1,после чего программа возвращается к поиску строки в строке 2100 программы.

Заметим, что если в процессе поиска строки не удается найти столбец (СJ=0 в строке 2190), не являющийся “тупиковым путем”, то происходит возвращение (строка 2210) к строке предыдущего поиска столбца. Если в поисках столбца удается найти только строки (RI=0 в строке 2590), соответствующие тупиковым путям, то осуществляется возвращение (строка 2610) к строке предыдущего поиска строки. Однако в силу того, что ММ сохраняет свое значение, ошибка не повторяется в дальнейшем (ММ=1 в строках 2150 и 2550). Поскольку базис задан треугольной системой уравнений, процесс в конце концов закончится и управление будет передано из строки 2400 в строку 3000.

В строках 3000 – 3040 программы содержится наименьшая базисная переменная из клеток, в которых    D=-1. Здесь  определяются значение w и положение переменной (KK,LL), которая будет удалена из базиса. В строках 3100 – 3120 клетки включаются в цепь. В конечном счете переменная (K,L) определяются как базисная, переменная (KK,LL) – как небазисная и определяется количество базисных переменных во всех строках и столбцах. Затем программа возвращается к вычислению симплекс-множителей u и v.

При работе программы печать (u и v) в строках 1340 – 1342 и наибольшего по модулю значения сij в строке 1581, а также печать в строках 2071, 2321 и 2721 могут быть подавлены. Последние три строки отражают цепи и обратный поиск. Печать в строке 3221, определяющая w и переменную для удаления из базиса, тоже могут быть подавлена.

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

      Положим u и w, а также указатели

       строк и столбцов равными 0

   Найти строку с наибольшим числом

   Базисных переменных (строка L).

  Положить U(L)=0, пометить строкуL

IU(L)=1, подсчитать помеченные строки

Для занятых ячеек в строке L

Положить V(J)=C(L,J), пометить

столбцы IV(J)=1 и подсчитать

помеченные столбцы

Для занятых ячеек в помеченных

строках положить V(J)=C(I,J)-U(I).

Для занятых ячеек в помеченных

столбцах положить U(I)=C(I,J)-V(J).

Подсчитать помеченные столбцы и

строки

нет                                                              да

           Все строки и столбцы                                                  найти  и переслать

                  помечены?                                                               их в массив D(I,J)

                                                                                                Найти наименьший  эле-                

мент D(K,L) в массиве D(I,J)

                                  найти новое

                          допустимое базисное            нет       

                                    решение                                            D(K,L)0 ?

                                                                                                 

                                                                                                            да

                                                                                                   

                                                                                                  Оптимум найден

           

Рис3.

                           

READY.

20                PRINT «Решение транспортной задачи»

30                REM в задаче рассматриваются М строк и N столбцов

40                READ M, N

50                REM массивы A(I) и B(J) являются общим обозначением строк

51                REM И СТОЛБЕЦ; МАССИВЫ DA(I) И DB(J) ПРЕДНАЧНАЧЕНЫ ДЛЯ

52                REM ХРАНЕНИЯ ИХ КОПИЙ; МАССИВЫ  IP(I) И IC(J)  УКАЗЫВАЮТ

53                REM (ЕСЛИ ИХ ЭЛЕМЕНТЫ РАВНЫ 1), ЧТО СООТВЕТСТВУЮЩИЕ СТРОКИ 

54                REM И СТОЛБЦЫ БЫЛИ УДАЛЕНЫ; МАССИВЫ TP(I) И TC(J) ЯВЛЯЮТСЯ

55                REM СЧЕТЧИКАМИ БАЗИСНЫХ ПЕРЕМЕННЫХ В СТРОКАХ И СТОЛБЦАХ

60                DIM A(M), DA(M), B(N), DB(N), IR(M), IC(N), TR(M), TC(N)

65                 REM МАССИВЫ IU(I) И IV(J) УКАЗЫВАЮТ (ЕСЛИ ИХ ЭЛЕМЕНТЫ

66                 REM РАВНЫ 1), ЧТО ЭЛЕМЕНТАМ МАССИВОВ U И V БЫЛИ ПРИСВОЕНЫ

67                 REM ЗНАЧЕНИЯ

70        DIM  U(M), V(N), IU(M), IV(N)

80        DIM RT(M+N), CT(M+N)

85        REM МАССИВЫ C(I, J) СОДЕРЖИТ СТОИМОСТИ, МАССИВ X(I, J) –

90        REM НЕИЗВЕСТНЫЕ; МАССИВ IX(I, J) ОБОЗНАЧАЕМ БАЗИС, ЕСЛИ ЕГО  

95        REM ЭЛЕМЕНТЫ РАВНЫ 1

100      DIM C(M, N), X(M, N), IX(M, N), D(M, N), MM(M, N)

105      REM ПРОЧИЕ МАССИВЫ ЯВЛЯЮТСЯ РАБОЧИМИ

110      REM ПОДРОБНОСТИ ОПИСАНЫ В ТЕКСТЕ

140      REM  ВВЕСТИ СТОИМОСТИ, ОБЩИЕ СТРОКИ И СТОЛБЦЫ

150      FOR  I=1 TO M

160      FOR J=1 TO N 

170      READ C(I, J)  

180            NEXT J

190      NEXT I

200      FOR I=1 TO M: READ A(I): DA(I)=A(I): NEXT I

210      FOR J=1 TO N: READ B(J): DB(J)=B(J): NEXT J

490      REM  НАЙТИ НАИМЕНЬШУЮ СТОИМОСТЬ В МАССИВЕ C(RI, CJ)

500       C=0: CT=0: CR=0

510       RI=0: CJ=0: Y=IE10

600       FOR I=1 TO M

605       REM ПРОПУСТИТЬ УДАЛЕННЫЕ СТРОКИ

610       IF IR(I)=1 THEN GOTO 670

620       FOR J=1 TO N

625       REM ПРОПУСТИТЬ УДАЛЕННЫЕ СТОЛБЦЫ

630       IF IC(J)=1 THEN GOTO 660

640       IF C(I, J)>Y THEN GOTO 660

650       Y=C(I. J): RI=I: CJ=J

660       NEXT J

670       NEXT I

680            REM МИНИМАЛЬНЫЙ ЭЛЕМЕНТ ПО ВСЕМ СТРОКАМ И СТОЛБЦАМ

681       REM ПЕРЕСЛАТЬ В МАССИВ Х(RI, CJ)

685       REM ПОМЕТИТЬ БАЗИС В МАССИВЕ IX

690       REM УДАЛИТЬ СТРОКУ ИЛИ СТОЛБЕЦ И ПОМЕТИТЬ ИХ

695       REM ОПРЕДЕЛИТЬ ДРУГУЮ СУММУ, ПОДСЧИТАТЬ КОЛИЧЕСТВО

696       REM УДАЛЕНИЙ СТРОК

700       IF DA(RI)<=DB(CJ) THEN GOTO 760

710       X(RI, CJ)=DB(CJ)

720       IX(RI, CJ)=1

730       DA(RI)=DA(RI)-DB(CJ):DB(CJ)=0 

740       IC(CJ)=1: C0=C0+1: CT=CT+1

750       GOTO 810

760       IF DA(RI)=DB(CJ) AND CR=M-1 THEN GOTO 710

770       X(RI, CJ)=DA(RI)

780       IX(RI, CJ)=1

790       DB(CJ)=DB(CJ)-DA(RI): DA(RI)=0

800        IR(RI)=1: C0=C0+1: CR=CR+1  

810       TR(RI)=TR(RI)+1: TC(CJ)=TC(CJ)+1

820       IF C0<M+N-1 THEN GOTO 510

830       CR=CR+1

840       REM В СТРОКЕ 760 БЫЛИ ПРИНЯТЫ МЕРЫ К ТОМУ, ЧТОБЫ

850       REM НЕ УДОЛЯТЬ ВСЕ СТРОКИ, ПОКА ОСТАЮТСЯ СТОЛБЦЫ

990      REM НАЙТИ U И V, ПОЛОЖИВ ИХ СНАЧАЛА РАВНЫМИ 0

1000    FOR I=1 TO M

1010    IU(I)=0: U(I)=0

1020    NEXT I

1030    FOR J=1 TO N

1040    IV(J)=0: V(J)=0

1050    NEXT J

1060    REM НАЙТИ СТРОКУ С НАИБОЛЬШЕЙ БАЗИСНОЙ ПЕРЕМЕННОЙ,

1070   REM НАПРИМЕР СТРОКУ L

1080   T=0: L=0

1100   FOR I=1 TO M

1110    IF TR(I)<T THEN GOTO 1130

1120    T=TR(I): L=I

1130    NEXT I

1140    U(L)=0: IU(L)=1: C0=1: CR=1: CT=0

1150   FOR J=1 TO N

1160   IF IX(L, J)=0 THEN GOTO 1190

1170   V(J)=C(L, J): IV(J)=1

1180   CT=CT+1: C0=C0+1

1190   NEXT J

1195   REM ОБРАБОТАТЬ БАЗИСНЫЕ ПЕРЕМЕННЫЕ В ПОМЕЧЕННЫХ

1196    REM СТРОКАХ ИЛИ СТОЛБЦАХ

1200   FOR I=1 TO M

1210   FOR J=1 TO N

1220   IF IX(I, J)=0 THEN GOTO 1310

1230   IF IU(I)=0 AND IV(J)=0 THEN GOTO 1310

1240   IF IU(I)=1 AND IV(J)=1 THEN GOTO 1310

1250   IF IU(I)=0 AND IV(J)=1 THEN GOTO 1290

1260   V(J)=C(I, J)-U(I): IV(J)=1

1270   CT=CT+1: C0=C0+1

1280        GOTO 1310

1290   U(I)=C(I, J)-V(9J): IU(I)=1

1300   CR=CR+1: C0=C0+1

1310   NEXT J

1320   NEXT I

1325   REM ПРОВЕРИТЬ, ВСЕ ЛИ СТРОКИ И СТОЛБЦЫ БЫЛИ ПОМЕЧЕНЫ

1330   IF C0<>M+N THEN GOTO 1200

1340   PRINT “ДОПОЛНИТЕЛЬНЫЕ СТОИМОСТИ”

1341   PRINT “U(I)”;: FOR I=1 TO M: PRINT U(I);: NEXT I: PRINT ””

1342   PRINT “V(J)”;: FOR J=1 TO N: PRINT V(J):; NEXT J: PRINT “”

1390   REM ЭЛЕМЕНТЫ С’(IJ) ПОМЕЩАЮТСЯ В МАССИВ D(I, J);

1395   REM ПРОВЕРИТЬ, РАВНЫ ЛИ ОНИ 0 ДЛЯ БАЗИСА

1400   FOR I=1 TO M

1410   FOR J=1 TO N

1420   IF IX(I, J)=0 THEN GOTO 1460

1430   D(I, J)=C(I, J)-U(I)-V(J)

1440   IF D(I, J)<>0 THEN PRINT “ОШИБКА 1”

1450   GOTO 1470

1460   D(I, J)=C(I, J)-U(I)-V(J)

1470   NEXT J

1480   NEXT I

1490   REM НАЙТИ НАИМЕНЬШИЙ ЭЛЕМЕНТ В МАССИВЕ D(I, J) И

1495   REM ПРИПЕСАТЬ ЕМУ ИНДЕКСЫ (K, L)

1500   T=0: K=0: L=0

1510   FOR I=1 TO M

1520   FOR J=1 TO N

1530   IF IX(I, J)=1 THEN GOTO 1560

1540   IF D(I, J)>=T THEN GOTO 1560

1550   T=D(I, J): K=I: L=J

1560   NEXT J

1570   NEXT I

1575   REM ЕСЛИ Т ВСЕ ЕЩЕ БОЛЬШЕ 0, ТО ВСЕ D(I, J) ПОЛОЖИТЕЛЬНЫ

1576   REM И ДАННОЕ РЕШЕНИЕ ОПТИМАЛЬНО

1580   IF T=0 THEN GOTO 4000

1581   PRINT “”: PRINT “C’KL=”T;: PRINT “K=”K;: PRINT “L=”:PRINT “”

1582   PRINT “”: GOSUB 5000

1585   REM В ПОДПРОГРАММЕ, НАЧИНАЮЩЕЙСЯ СО СТРОКИ 5000,

1586   REM ПЕЧАТАЕТСЯ БАЗИСНОЕ ДОПУСТИМОЕ РЕШЕНИЕ

1990   REM НАЙТИ СЛЕДУЮЩЕЕ БАЗИСНОЕ ДОПУСТИМОЕ РЕШЕНИЕ;

1995   REM СНАЧАЛА ВСЕ ИНДИКАТОРЫ И СЧЕТЧИКИ ПОЛОЖИТЬ РАВНЫ 0

2000   FOR I=1 TO M: IU(I)=0: NEXT I

2010   FOR J=1 TO N: IV(J)=0: NEXT J

2015   FOR I=1 TO M+N: RT(I)=O: CT(I)=0: NEXT I

2020   FOR I=1 TO M: FOR J=1 TO N

2030   D(I, J)=0: MM(I, J)=0

2040  NEXT J: NEXT I

2050  T=1: IP=0

2060   RT(T)=K: CT(T)=L

2070   D(K, L)=1: MM(K, L)=1: IU(K)=1

2071   PRINT T, K; L

2100   FR=0: FC=0: RI=RT(T): CJ=0

2110   FOR J=1 TO N

2120        IF FC=1 THEN GOTO 2180

2130   IF IX(RI, J)=0 THEN GOTO 2180

2140   IF IV(J)=1 THEN GOTO 2180

2150   IF MM(RI, J)=1 THEN GOTO 2180

2155   IF TC(J)=1 AND J=L THEN GOTO 2170

2160   IF TC(J)=1 THEN IP=1: GOTO 2180

2170   FC=1: CJ=J: IV(J)=1: J=N

2180   NEXT J

2190    IF CJ<>0 THEN GOTO 2300

2200    IF IP>0 THEN IP=0

2210    D(RT(T), CT(T))=0: T=T-1

2220    GOTO 2500

2300   T=T+1

2310   RT(T)=RI: CT(T)=CJ

2320   D(RI, CJ)=-1: MM(RI, CJ)=1

2321   PRINT T, RI; CJ

2400   IF CT(T)=L AND T>2 THEN GOTO 3000

2500   FR=0: FC=0: RI=0: CJ=CT(T)

2510   FOR I=1 TO M

2520   IF FR=1 THEN GOTO 2580

2530   IF IX(I, CJ)=0 THEN GOTO 2580

2540   IF IU(I)=1 THEN GOTO 2580

2550   IF MM(I, CJ)=0 THEN GOTO 2580

2560   IF TR(I)=1 AND IP=0 THEN IP=1: GOTO 2580

2570   FR=1: RI=I: IU(I)=1: I=M

2580   NEXT I

2590   IF RI<>0 THEN GOTO 2700

2600   IF IP>0 THEN IP=0

2610   D(RT(T), CT(T)=0: T=T-1

2620   GOTO 2100

2700        T=T+1: IP=0

2710   RT(T)=RI: CT(T)=CJ

2720   D(RT(T), CT(T))=1: MM(RI, CJ)=1

2721    PRINT T, RI; CJ

2730   GOTO 2100

3000   W=1E10: L=0: KK=0

3010   FOR I=2 TO T STEP 2

3020   IF X(RT(I),CR(I))>=W THEN GOTO 3040

3030   W= X(RT(I), CT(I)): KK=RT(I): LL=CT(I)

3040   NEXT I

3100   FOR I=1 TO T

3110    X(RT(I), CT(I))=X(RT(I), CT(I))+W*D(RT(I), CT(I))

3120   NEXT I

3200   IX(K, L)=1: IX(KK, LL)=0

3210   TR(K)=TR(K)+1: TR(KK)=TR(KK)-1

3220   TC(L)=TC(L)+1: TC(LL)=TC(LL)-1

3221   PRINT “W=”W;: PRINT “KK=”KK;: PRINT “LL=”LL

3222   PRINT “ПРЕОБРАЗОВАНИЕ ЗАКОНЧЕНО УСПЕШНО”

3250   GOTO 1000

4000   PRINT “ОКОНЧЕННОЕ РЕШЕНИЕ”

4010   GOSUB 5000

4500   END

5000        CC=0

5010    PRINT “ I   J     XIJ        CIJ        СТОИМОСТЬ”

5020    FOR I=1 TO M

5030    FOR J=1 TO N

1320    NEXT I

1325    REM ПРОВЕРИТЬ ВСЕ ЛИ СТРОКИ И СТОЛБЦЫ БЫЛИ ПОМЕЧЕНЫ

1330    IF C0<>M+N THEN GOTO 1200

1340    PRINT “ДОПОЛНИТЕЛЬНЫЕ СТОИМОСТИ”

1341    PRINT “U(I)”;: FOR I=1 TO M: PRINT U(I);: NEXT I: PRINT “”

1342    PRINT “V(J)”;: FOR J=1 TO N: PRINT V(J);: NEXT J: PRINT ””

1390    REM ЭЛЕМЕНТЫ C’(IJ) ПОМЕЩАЮТСЯ В МАССИВ D(I, J);

1395    REM ПРОВЕРИТЬ, РАВНЫ ЛИ ОНИ 0 ДЛЯ БАЗИСА

1400    FOR I=1 TO M

1410    FOR J=1 TO N

1420    IF IX(I, J)=0 THEN GOTO 1460

1430    D(I, J)=C(I, J)-U(I)-V(J)

1440    IF D(I, J)<>0 THEN PRINT “ОШИБКА 1”

1450    GOTO 1470

1460     D(I, J)=C(I, J)-U(I)-V(J)

1470    NEXT J

1480    NEXT I

1490    REM НАЙТИ НАИМЕНЬШИЙ ЭЛЕМЕНТ В МАССИВЕ D(I, J) И

1495    REM ПРИПИСАТЬ ЕМУ ИНДЕКСЫ (K, L)

1500        T=0: K=0: L=0

1510        FOR I=1 TO M

1520        FOR J=1 TO N

1530        IF IX(I,J)=1 THEN GOTO 1560

1540        IF  D(I,J)>=T THEN GOTO 1560

1550        T=D(I,J): K=I: L=J

1560        NEXT J

1570        NEXT I

1575        REM  ЕСЛИ Т ВСЕ ЕЩЕ  БОЛЬШЕ 0, ТО ВСЕ В(I,J)  ПОЛОЖИТЕЛЬНЫ

1576        REM  И ДАННОЕ РЕШЕНИЕ ОПТИМАЛЬНО

1580        IF Y=0 THEN GOTO 4000

1581        PRINT ””: PRINT “C’KL=”T;: PRINT “K=”K:;PRINT “L=”:PRINT “”

1582        PRINT “”: GOSUB 5000

1585        REM  В ПРОГРАММЕ, НАЧИНАЮЩЕЙСЯ СО СТРОКИ 5000,

1586        REM  ПЕЧАТАЕТСЯ БАЗИСНОЕ ДОПУСТИМОЕ РЕШЕНИЕ

1990        REM  НАЙТИ СЛЕДУЮЩЕЕ БАЗИСНОЕ ДОПУСТИМОЕ РЕШЕНИЕ;

1995        REM СНАЧАЛА ВСЕ ИНДИКАТОРЫ И СЧЕТЧИКИ

1996        REM ПОЛОЖИТЬ РАВНЫМИ 0

2000        FOR I=1 TO M: IU(I)=0: NEXT I

2010        FOR J=1 TO N: IV(I)=0: NEXT J

2015        FOR I=1 TO M+N: RT(I)=0: CT(I)=0: NEXT I

2020        FOR I=1 TO M: FOR J=1 TO N

2030        D(I,J)=0: MM(I,J)=0

2040        NEXT J: NEXT I

2050        T=1: IP=0

2060        RT(T)=K: CT(T)=L

2070        D(K,L)=1: MM(K,L)=1: IU(K)=1

2071        PRINT  T,K;L

2100        FR=0: FC=0: RI=RT(T): CJ=0

2110        FOR J=1 TO N

2120        IF FC=1 THEN GOTO 2180

2130        IF IX(RI,J)=0 THEN  GOTO 2180

2140        IF IV(J)=1 THEN GOTO 2180

2150        IF MM(RI,J)=1 THEN GOTO 2180

2155        IF TC(J)=1 AND J=L THEN GOTO 2170

2160        IF  TC(J)=1 THEN IP=1: GOTO 2180

2170        FC=1: CJ=J: IV(J)=1: J=N

2180        NEXT J

2190        IF CJ<>0 THEN GOTO 2300

2200        IF IP>0 THEN IP=0

2210        D(RT(T),CT(T))=0: T=T-1

2220        GOTO 2500

2300        T=T+1

2310        RT(T)=RI: CT(T)=CJ

2320        D(RI,CJ)=-1: MM(RI,CJ)=1

2321        PRINT T,RI;CJ

2400        IF CT(T)=L AND T>2 THEN GOTO 3000

2500        FR=0: FC=0: RI=0: CJ=CT(T)

2510        FOR I=1 TO M

2520        IF FR=1 THEN GOTO 2580

2530        IF IX(I,CJ)=0 THEN GOTO 2580

2540        IF IU(I)=1 THEN GOTO 2580

2550        IF MM(I,CJ)=0 THEN GOTO 2580

2560        IF TR(I)=1 AND IP=0 THEN IP=1: GOTO 2580

2570        FR=1: RI=I: IU=1: I=M

2580        NEXT I

2590        IF RI<>0 THEN GOTO 2700

2600        IF IP>0 THEN IP=0

2610        D(RT(T),CT(T))=0: T=T-1

2620        GOTO 2100

2700        T=T+1: IP=0

2710        RT(T)=RI: CT(T)=CJ

2720        D(RT(T),CT(T))=1: MM(RI,CJ)=1

2721        PRINT T,RI;CJ

2730        GOTO 2100

3000        W=1E10: L=0: KK=0

3010        FOR I=2 TO T STEP 2

3020        IF X(RT(I),CR(I))>=W THEN GOTO 3040

3030        W=X(RT(I),CT(I)): KK=RT(I): LL=CT(I)

3040        NEXT I

3100        FOR I=1 TO T

3110        X(RT(I),CT(I))=X(RT(I),CT(I))+W*D(RT(I),CT(I))

3120        NEXT I

3200        IX(K,L)=1: IX(KK,LL)=0

3210        TR(K)=TR(K)+1: TR(KK)=TR(KK)-1

3220        TC(L)=TC(L)+1: TC(LL)=TC(LL)-1

3221        PRINT “W=”W;: PRINT “KK=”KK;: PRINT “LL=”LL

3222        PRINT “ПРЕОБРАЗОВАНИЕ ЗАКОНЧЕНО УСПЕШНО”

3250        GOTO 1000

4000        PRINT “ОКОНЧАТЕЛЬНОЕ РЕШЕНИЕ”

4010        GOSUB  5000

4500        END

5000        CC=0

5010     PRINT  “  I    J     XIJ     CIJ     СТОИМОСТЬ”

5020        FOR I=1 TO M

5030        FOR J=1 TO N

5040        IF IX(I,J)=0 THEN GOTO 5110

5050        PP=C(I,J)*X(I,J)

5060        CC=CC+PP

5070        PRINT I;J;

5080        PB=430: PA=X(I,J): GOSUB 9000

5090        PA=C(I,J): GOSUB 9000: PA=PP: GOSUB 9000

5100        PRINT “”

5110        NEXT J: NEXTI

5200        PRINT “ОБЩАЯ СТОИМОСТЬ РАВНА “;CC

5250        RETURN

9000        PC=INT(PB/100)

9010        P$=’’

9020        IF PC=0 THEN PRINT “”: GOTO 9040

9030        PRINT LEFT$(P$,PC);

9040        PC=PB-100*PC

9050        PD=INT(PC/10):PC=PC-10*PD

9060        IF PD=0 THEN PD=1

9070        IF PA<0 THEN P$=P$+”-”

9080        PE=ABS(PA)

9090        PE=PE+5*10^(-1-PC)

9100        IF PE>=10^PD THEN PRINT PA;: RETURN

9110        P$=P$+MID$(STR$(INT(PE)),2,PD)

9120        PRINT  RIGHT$(P$,PD+1)

9130        IF PC=0 THEN RETURN

9140        PRINT ”.”;

9150        PE=INT((PE-INT(PE))*10^PC)

9160        P$=”000000000”

9170        P$=P$+MID$(STR$(PE),2,PC)

9180        PRINT  RIGHT$(P$,PC);: RETURN

10000    DATA  3,5

10010    DATA  1,0,3,4,2

10020    DATA 5,1,2,3,3

10030    DATA  4,8,1,4,3

10040    DATA  15,25,20

10050    DATA  20, 12,5,8,15

READY.

РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ

ДОПОЛНИТЕЛЬНЫЕ СТОИМОСТИ

U(I)-4  0  0

V(J)  5  4  1  3  3

C’KL=-3  K=  2  L=  2

I     J     XIJ     CIJ      СТОИМОСТЬ

1    1         3        1            3

1    2        12       0            0

2    1        17       5           85

2    4         8        3           24

2    5         0        3           0

3    3         5        1           5

3    5         15      3           45

ОБЩАЯ  СТОИМОСТЬ   РАВНА  162

1                 2    2

2                 2    1

3                 1    1

4                 1    2

W=   12  KK=  1  L=  2

ПРЕОБРАЗОВАНИЕ  ЗАКОНЧЕНО  УСПЕШНО     

ДОПОЛНИТЕЛЬНЫЕ  СТОИМОСТИ

U(I)-4  0  0

V(J)  5  1  1  3  3

C’KL=-1  K=  3  L=  1

I     J        XIJ     CIJ      СТОИМОСТЬ

1    1         15        1            15

2    1          5         5            25

2    2         12        1            12

2    4          8         3            24

2    5          0         3            0

3    3          5         1            5

3    5         15        3            45

ОБЩАЯ  СТОИМОСТЬ   РАВНА  126

1                 3    1

2                 3    5

3                 2    5

4                 2    1

W=   5  KK=  2  L=  1

ПРЕОБРАЗОВАНИЕ   ЗАКОНЧЕНО УСПЕШНО