Курсовая работа: Транспортная задача линейного программирования
Если в качестве выбрать наименьшее из чисел,
стоящих в вершинах, снабженных знаком “–“, то, по крайней мере, одно из прежних
базисных неизвестных примет значение нуль, и мы можем перевести его в число
свободных неизвестных, сделав вместо него базисным то неизвестное, которое было
свободным.
Так, например, в рассмотренном выше цикле имеем
отрицательные вершины и
; следовательно, выбрав
, мы получаем:
старые значения: ;
новые значения:
т. е. вместо прежнего базисного решения получаем новое базисное решение:
Пункты Отправления |
Пункты назначения | Запасы | |||||||||
|
|
|
|
|
|||||||
|
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, а пересчет по циклу
осуществляется с помощью числа
(изменение затрат равно
).
Вычисление алгебраической суммы тарифов для каждого из
свободных неизвестных можно производить без построения соответствующего
цикла, пользуясь, так называемыми, потенциалами. Припишем каждой базе , некоторое число
и каждому
потребителю
некоторое
число
:
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12