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 |
Выбор в качестве х минимального среди чисел, стоящих в отрицательных вершинах цикла, обеспечивает допустимость нового базиса.
Если минимальное значение среди базисных неизвестных, стоящих в отрицательных вершинах цикла, принимается не в одной отрицательной вершине, то свободной оставляют только одну из них, а в других клетках с тем же минимальным значением пишут нули. В этом случае новое базисное решение будет вырожденным.
Может случиться, что и само минимальное значение среди чисел в отрицательных клетках равно нулю. Тогда преобразование таб-лицы перевозок сведется к перестановке этого нуля в свободную клетку. Значения всех неизвестных при этом остаются неизменными, но решения считаются различными, так как различны базисы. Оба решения вырождены.
Описанное выше преобразование таблицы перевозок, в результате которого преобразуется базис, называется пересчетом по циклу.
Заметим, что неизвестные, не входящие в цикл, этим преобразованием не затрагиваются, их значения остаются неизменными и каж-дое из них остается либо в группе базисных, либо в группе свобод-ных неизвестных, как и до пересчета.
Выясним теперь, как пересчет по циклу влияет на общий объем затрат на перевозки и при каком условии эти затраты становятся меньше.
Пусть - некоторое свободное неизвестное, для которого мы построили цикл и осуществили пересчет по циклу с некоторым числом . Если вершине цикла, находящейся в строке и столбце таблицы перевозок, приписан знак “+”, то значение неизвестного , находящегося в этой вершине, увеличивается на , что в свою очередь вызывает увеличение затрат на . где - тариф, соответствующий этой клетке; если же указанной вершине приписан знак “-”, то значение неизвестного уменьшается на , что вызывает уменьшение затрат на .
Сложим тарифы, соответствующие положительным вершинам цикла, и вычтем из этой суммы сумму тарифов, соответствующих отрицательным вершинам цикла; полученную разность назовем алгебраической суммой тарифов для данного свободного неизвестного . Подсчет алгебраической суммы тарифов можно истолковать и так: припишем тарифам те же знаки, которые приписаны соответствующим вершинам цикла, тогда алгебраическая сумма тарифов равна сумме таких тарифов со знаком (“относительных тарифов”).
Теперь, очевидно, мы можем, заключить, что в целом при пере-счете но циклу, соответствующему свободному неизвестному общий объем затрат на перевозки изменится на произведение алгеб-раической суммы тарифов на , т. е. на величину . Следовательно, если алгебраическая сумма тарифов для некоторого свобод-ного неизвестного отрицательна , то пересчет по циклу, соответствующему этому неизвестному, приводит к уменьшению общей суммы затрат на реализацию плана перевозок. Если же алгебраическая сумма тарифов положительна , то пересчет по соответствующему циклу приведет к увеличению общей суммы затрат. И, наконец, если алгебраическая сумма тарифов равна нулю , то пересчет по соответствующему циклу не изменит общую сумму затрат (два различных базисных плана требуют одинаковых затрат на их реализацию).
Так, например, для цикла в рассмотренной задаче алгебраическая сумма тарифов
.
Значит, пересчет по этому циклу снижает расходы. И действитель-но, осуществив такой пересчет, мы получаем план, по которому объем перевозок в тонно-километрах составляет
тогда как по исходному плану он составил . Имеем снижение объема перевозок на 1200 тонно-километров, что и следовало ожидать, так как алгебраическая сумма тарифов в дан-ном случае равна -15, а пересчет по циклу осуществляется с помощью числа (изменение затрат равно ).
Вычисление алгебраической суммы тарифов для каждого из сво-бодных неизвестных можно производить без построения соответ-ствующего цикла, пользуясь, так называемыми, потенциалами. При-пишем каждой базе , некоторое число и каждому потребителю некоторое число :
,
так что
,
где - тарифы, соответствующие клеткам, заполненным базис-ными неизвестными. Эти числа и называются потенциалами соответствующих баз и потребителей.
Зная потенциалы, легко вычислить алгебраическую сумму тари-фов. Действительно, если в алгебраической сумме тарифов по циклу, соответствующему свободному неизвестному , заменить тарифы базисных клеток их выражениями через потенциалы по формулам (4.1), то, в силу чередования знаков при вершинах цикла, все потенциалы, кроме и сократятся, и мы получим:
.
Так, например, для цикла в рассмотренной выше задаче имеем
.
Для базисных клеток сумма потенциалов строки и столбца, в которых находится эта клетка, равна тарифу, соответствующему этой клетке; если же клетка для неизвестного свободная, то сумму потенциалов
называют косвенным тарифом этой клетки. Следовательно, алгеб-раическая сумма тарифов для свободной клетки равна разности ее настоящего (“истинного”) и косвенного тарифов:
Из (4.3) следует, что если косвенный тариф для данной свобод-ной клетки больше её истинного тарифа, то алгебраическая сумма тарифов по циклу, соответствующему этой клетке, будет отрица-тельна; если же косвенный тариф меньше истинного, то алгебраи-ческая сумма тарифов положительна, и, наконец, если косвенный тариф равен истинному, то алгебраическая сумма тарифов равна нулю.
Потенциалы можно найти из системы равенств (4.1), рассматри-вая их как систему уравнений с неизвестными. Так как неизвестных здесь на единицу больше, чем уравнений, то, по крайней мере, один из потенциалов мы можем выбрать произвольно, положив, например, ; тогда остальные потенциалы легко опре-деляются из уравнений (4.1).
Например, для плана, полученного по диагональному методу в рассмотренной выше задаче, имеем
Система содержит семь уравнений с восемью неизвестными. Выбирая произвольно значение , находим последовательно из пер-вых трех уравнений значения , , , затем из четвертого уравнения - , из пятого уравнения - , из шестого уравнения и, наконец, из седь-мого уравнения - .
Положив, например, , получаем значения потенциалов:
Найдем теперь косвенные тарифы для свободных клеток и сравним их с истинными тарифами:
Для клеток с неизвестными и косвенные тарифы больше истинных. Следовательно, для них мы будем иметь отрицательные алгебраические суммы тарифов:
Значение мы уже имели раньше, вычисляя алгебраиче-скую сумму тарифов для этой клетки непосредственно по циклу.
Замечание 1. Подсчитывая косвенные тарифы как суммы соответ-ствующих потенциалов, полезно не пропускать и клетки с базисны-ми неизвестными (заполненные клетки). Для этих клеток сумма потенциалов равна истинному тарифу; последнее может служить проверкой правильности найденных значении потенциалов.
Замечание 2. Можно показать, что если сумму всех затрат по данному плану перевозок выразить через свободные неизвестные [для этого надо исключить базисные неизвестные из выражения для S, см. формулу (2.4)], то коэффициент при каждом из таких неизвестных будет равен алгебраической сумме тарифов по циклу, соответствующему ей в таблице перевозок. Это еще раз подтверждает, что пересчет по циклам является специфической формой применения симплекс-метода к решению транспортной задачи.
- 1.История зарождения и создания линейного программирования.
- 2.Транспортная задача. Общая постановка, цели, задачи. Основные типы, виды моделей.
- 3. Методы составления начального опорного плана.
- 4.Понятие потенциала и цикла.
- Критерий оптимальности базисного решения транспортной задачи. Методы отыскания оптимального решения.
- Задача, двойственная к транспортной.
- 7.Пример решения транспортной задачи.
- Транспортная задача линейного программирования
- 36. Задачи линейного программирования.
- Задачи линейного программирования
- Задачи линейного программирования.
- 5. Транспортная задача линейного программирования
- 1.3. Транспортная задача линейного программирования
- 3.1. Линейное программирование. Транспортная задача – 4/12 час.
- 6.Транспортные задачи линейного программирования
- Транспортная задача линейного программирования