Транспортная задача линейного программирования
.
На пятом шаге клеток с наименьшими значениями
оказалось две
. Мы заполнили клетку для
, положив
. Можно было выбрать для заполнения другую клетку, положив
, что приведет в результате к другому опорному плану. Общий
объем перевозок в тонно-километрах для этого плана составит
.
Замечание. В диагональном методе не учитываются величины тарифов, в методе же наименьшей стоимости эти величины учитываются, и часто последний метод приводит к плану с меньшими общими затратами (что и имеет место в нашем примере), хотя это и не обязательно.
Кроме рассмотренных выше способов иногда используется, так называемый, метод Фогеля. Суть его состоит в следующем: В распределительной таблице по строкам и столбцам определяется разность между двумя наименьшими тарифами. Отмечается наибольшая разность. Далее в строке (столбце) с наибольшей разностью заполняется клетка с наименьшим тарифом. Строки (столбцы) с нулевым остатком груза в дальнейшем в расчет не принимаются. На каждом этапе загружается только одна клетка. Распределение груза производится, как и ранее.
4.Понятие потенциала и цикла.
Для перехода от одного базиса к другому при решении транспортной задачи используются так называемые циклы.
Циклом пересчета или короче, циклом в таблице перевозок называется последовательность неизвестных, удовлетворяющая следующим условиям:
Одно из неизвестных последовательности свободное, а все остальные – базисные.
Каждые два соседних в последовательности неизвестных лежат либо в одном столбце, либо в одной строке.
Три последовательных неизвестных не могут находиться в одном столбце или в одной строке.
Если, начиная с какого-либо неизвестного, мы будем последовательно переходить от одного к следующему за ним неизвестному то, через несколько шагов мы вернемся к исходному неизвестному.
Второе условие означает, что у двух соседних неизвестных в цикле либо первые, либо вторые индексы одинаковы.
Если каждые два соседних неизвестных цикла соединить отрезком прямой, то будет получено геометрическое изображение цикла – замкнутая ломаная из чередующихся горизонтальных и вертикальных звеньев, одна из вершин которой находится в свободной клетке, а остальные - в базисных клетках.
Можно доказать, что для любой свободной клетки таблицы перевозок существует один и только один цикл, содержащий свободное неизвестное из этой клетки, и что число вершин в цикле всегда четно.
Так, например, в таблице перевозок, составленной по
диагональному методу при решения задачи из предыдущего пункта, неизвестному
соответствует цикл
и т.д.
Пусть теперь мы имеем некоторую свободную клетку с
соответствующим ей циклом. Если мы изменим значение свободного неизвестного,
увеличив его на некоторое число
, то, переходя последовательно от одной вершины цикла к
другой, мы должны будем в силу неизменности сумм по строкам и по столбцам
поочередно уменьшать и увеличивать значения неизвестных в цикле на то же число
. Например, в указанном выше цикле для свободного
неизвестного
получим:
старые значения:
;
новые значения: ![]()
Очевидно, если снабдить вершины цикла поочередно
знаками “+” и “–“, приписав вершине в свободной клетке знак “+”, то можно
сказать, что в вершинах со знаком “+” число
прибавляется к
прежнему значению неизвестного, находящегося в этой вершине, а в вершинах со
знаком “–“ это число
вычитается из прежнего
значения неизвестного, находящегося в этой вершине.
Замечание. Так как число вершин в цикле всегда четно, то, возвращаясь в свободную клетку, мы должны будем приписать ей знак “+”, т. е. тот знак, который ей уже приписан при выходе из нее. Это очень существенное обстоятельство, так как иначе мы пришли бы к противоречию. Безразлично также, в каком направлении обходится цикл при “означивании” вершин.
Если в качестве
выбрать наименьшее из
чисел, стоящих в вершинах, снабженных знаком “–“, то, по крайней мере, одно из
прежних базисных неизвестных примет значение нуль, и мы можем перевести его в
число свободных неизвестных, сделав вместо него базисным то неизвестное,
которое было свободным.
Так, например, в рассмотренном выше цикле имеем
отрицательные вершины
и
; следовательно, выбрав
, мы получаем:
старые значения:
;
новые значения: ![]()
т. е. вместо прежнего базисного решения получаем новое базисное решение:
|
Пункты Отправления |
Пункты назначения | Запасы | |||||||||
|
|
|
|
|
|
|||||||
|
|
70 | 50 | 15 | 80 | 70 | 300 | |||||
| 90 | 110 | 100 | |||||||||
|
|
80 | 90 | 40 | 60 | 85 | 150 | |||||
| 80 | 70 | ||||||||||
|
|
50 | 10 | 90 | 11 | 25 | 250 | |||||
| 50 | 200 | ||||||||||
| Потребности | 170 | 110 | 100 | 120 | 200 | 700 |
Выбор в качестве х минимального среди чисел, стоящих в отрицательных вершинах цикла, обеспечивает допустимость нового базиса.
Если минимальное значение среди базисных неизвестных, стоящих в отрицательных вершинах цикла, принимается не в одной отрицательной вершине, то свободной оставляют только одну из них, а в других клетках с тем же минимальным значением пишут нули. В этом случае новое базисное решение будет вырожденным.
Может случиться, что и само минимальное значение среди чисел в отрицательных клетках равно нулю. Тогда преобразование таблицы перевозок сведется к перестановке этого нуля в свободную клетку. Значения всех неизвестных при этом остаются неизменными, но решения считаются различными, так как различны базисы. Оба решения вырождены.
Описанное выше преобразование таблицы перевозок, в результате которого преобразуется базис, называется пересчетом по циклу.
Заметим, что неизвестные, не входящие в цикл, этим преобразованием не затрагиваются, их значения остаются неизменными и каждое из них остается либо в группе базисных, либо в группе свободных неизвестных, как и до пересчета.
Выясним теперь, как пересчет по циклу влияет на общий объем затрат на перевозки и при каком условии эти затраты становятся меньше.
Пусть
– некоторое свободное
неизвестное, для которого мы построили цикл и осуществили пересчет по циклу с
некоторым числом
. Если вершине цикла, находящейся в
строке и
столбце таблицы
перевозок, приписан знак “+”, то значение неизвестного
, находящегося в этой вершине, увеличивается на
, что в свою очередь вызывает увеличение затрат на
. где
– тариф,
соответствующий этой клетке; если же указанной вершине приписан знак “–”, то
значение неизвестного
уменьшается на
, что вызывает уменьшение затрат на
.
Сложим тарифы, соответствующие положительным вершинам
цикла, и вычтем из этой суммы сумму тарифов, соответствующих отрицательным
вершинам цикла; полученную разность
назовем алгебраической
суммой тарифов для данного свободного неизвестного
. Подсчет алгебраической суммы тарифов можно истолковать и
так: припишем тарифам те же знаки, которые приписаны соответствующим вершинам
цикла, тогда алгебраическая сумма тарифов равна сумме таких тарифов со знаком
(“относительных тарифов”).
Теперь, очевидно, мы можем, заключить, что в целом при
пересчете но циклу, соответствующему свободному неизвестному
общий объем затрат на
перевозки изменится на произведение алгебраической суммы тарифов на
, т. е. на величину
. Следовательно, если алгебраическая сумма тарифов для
некоторого свободного неизвестного
отрицательна
, то пересчет по циклу, соответствующему этому неизвестному,
приводит к уменьшению общей суммы затрат на реализацию плана перевозок. Если же
алгебраическая сумма тарифов положительна
, то пересчет по соответствующему циклу приведет к увеличению
общей суммы затрат. И, наконец, если алгебраическая сумма тарифов равна нулю
, то пересчет по соответствующему циклу не изменит общую
сумму затрат (два различных базисных плана требуют одинаковых затрат на их
реализацию).
Так, например, для цикла