Xreferat.com » Рефераты по математике » Транспортная задача линейного программирования

Транспортная задача линейного программирования

программирования" width="59" height="24" />. В оставшейся новой таблице с тремя строками Транспортная задача линейного программирования и четырьмя столбцами Транспортная задача линейного программирования клеткой с наименьшим значением Транспортная задача линейного программирования клетка, гдеТранспортная задача линейного программирования. Заполняем описанным выше способом эту клетку и аналогично заполняем следующие клетки. В результате оказываются заполненными (в приведенной последовательности) следующие клетки:

Транспортная задача линейного программирования.

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

Транспортная задача линейного программирования.

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

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

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

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

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

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

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

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

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

Пусть Транспортная задача линейного программирования – некоторое свободное неизвестное, для которого мы построили цикл и осуществили пересчет по циклу с некоторым числом Транспортная задача линейного программирования. Если вершине цикла, находящейся в Транспортная задача линейного программирования строке и Транспортная задача линейного программирования столбце таблицы перевозок, приписан знак “+”, то значение неизвестного Транспортная задача линейного программирования, находящегося в этой вершине, увеличивается на Транспортная задача линейного программирования, что в свою очередь вызывает увеличение затрат на Транспортная задача линейного программирования. где Транспортная задача линейного программирования – тариф, соответствующий этой клетке; если же указанной вершине приписан знак “–”, то значение неизвестного Транспортная задача линейного программирования уменьшается на Транспортная задача линейного программирования, что вызывает уменьшение затрат на Транспортная задача линейного программирования.

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

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

Так, например, для цикла

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: