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

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

означает, что у двух соседних неизвестных в цикле либо первые, либо вторые индексы одинаковы.

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

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

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

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

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

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

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

Замечание. Так как число вершин в цикле всегда четно, то, возвращаясь в свободную клетку, мы должны будем приписать ей знак “+”, т. е. тот знак, который ей уже приписан при выходе из нее. Это очень существенное обстоятельство, так как иначе мы пришли бы к противоречию. Безразлично также, в каком направлении обходится цикл при “означивании” вершин.

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

Так, например, в рассмотренном выше цикле имеем отрицательные вершины Транспортная задача линейного программирования и Транспортная задача линейного программирования; следовательно, выбрав Транспортная задача линейного программирования, мы получаем:

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

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

т. е. вместо прежнего базисного решения получаем новое базисное решение:


Пункты

Отправления

Пункты назначения Запасы

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

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

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

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

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


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


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.3). В случае выполнения (1.4) (открытая модель) баланс транспортной задачи может нарушаться в 2-ух направлениях:

1. Сумма запасов в пунктах отправления превышает сумму поданных заявок (транспортная задача с избытком запасов):

е аi > е bj ( где i=1,...,m ; j=1,...,n );

2. Сумма поданных заявок превышает наличные запасы (транспортная задача с избытком заявок):

е аi < е bj ( где i=1,...,m ; j=1,...,n );

Рассмотрим последовательно эти два случая:

Транспортная задача с избытком запасов.

Сведем её к ранее рассмотренной транспортной задаче с правильным балансом. Для этого, сверх имеющихся n пунктов назначения В1, B2, ... , Bn, введём ещё один, фиктивный, пункт назначения Bn+1, которому припишем фиктивную заявку, равную избытку запасов над заявками

bn+1 = е аi - е bj ( где i=1,...,m ; j=1,...,n ) ,

а стоимость перевозок из всех пунктов отправления в фиктивный пункт назначения bn+1 будем

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

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

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

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