Транспортная задача
Содержание.
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
ПРЕОБРАЗОВАНИЕ ЗАКОНЧЕНО УСПЕШНО