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

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

loading="lazy" src="http://xreferat.ru/image/54/1306478425_112.gif" alt="Транспортная задача линейного программирования" width="120" height="24" /> в рассмотренной задаче алгебраическая сумма тарифов

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

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

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

тогда как по исходному плану он составил Транспортная задача линейного программирования. Имеем снижение объема перевозок на 1200 тонно-километров, что и следовало ожидать, так как алгебраическая сумма тарифов в данном случае равна –15, а пересчет по циклу осуществляется с помощью числа Транспортная задача линейного программирования (изменение затрат равно Транспортная задача линейного программирования).

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

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

так что

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

где Транспортная задача линейного программирования – тарифы, соответствующие клеткам, заполненным базисными неизвестными. Эти числа Транспортная задача линейного программирования и Транспортная задача линейного программирования называются потенциалами соответствующих баз и потребителей.

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

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

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

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

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

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

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

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

Из (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 будем считать равной нулю. Введением фиктивного пункта назначения B n+1 с его заявкой b n+1 мы сравняли баланс транспортной задачи, и теперь ее можно решать, как обычную транспортную задачу с правильным балансом.

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

Эту задачу можно свести к обычной транспортной задаче с правильным балансом, если ввести фиктивный пункт отправления Am+1 с запасом am+1 равным недостающему запасу, и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равной нулю.

Задача, двойственная к транспортной.

Построим задачу, двойственную к транспортной. С этой целью вспомним, что каждому пункту отправления Транспортная задача линейного программирования и назначения Транспортная задача линейного программирования отвечает определенное ограничение

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

В то же время каждому ограничению из (6.1) сопоставляется определенная неизвестная в двойственной задаче. Тем самым устанавливается соответствие между всеми пунктами Транспортная задача линейного программирования и Транспортная задача линейного программирования и всеми неизвестными двойственной задачи.

Обозначим неизвестную в двойственной задаче, отвечающую пункту отправления Транспортная задача линейного программирования, через Транспортная задача линейного программирования, а пункту назначения Транспортная задача линейного программирования – через Транспортная задача линейного программирования.

Каждому неизвестному в транспортной задаче соответствует ограничение, связывающее неизвестные в двойственной задаче. Неизвестное Транспортная задача линейного программирования входит ровно в два ограничения системы (6.1): одно из них отвечает пункту Транспортная задача линейного программирования, а другое – пункту Транспортная задача линейного программирования. В обоих этих уравнениях коэффициент при Транспортная задача линейного программирования равен 1. Поэтому соответствующее Транспортная задача линейного программирования ограничение в двойственной задаче имеет вид

(6.2)

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

Правая часть неравенства (6.2) равна Транспортная задача линейного программирования, потому что именно с этим коэффициентом неизвестная Транспортная задача линейного программирования входит в минимизируемую формулу (2.4).

Оптимизируемая форма двойственной задачи имеет вид

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

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

Предположим, что нам известно некоторое допустимое базисное решение транспортной задачи, в котором все базисные неизвестные строго положительны. Это решение оптимально лишь в том случае, когда соответствующая ей система оказывается совместной. Эта система возникает из системы (6.2), если в ней все неравенства, отвечающие базисным неизвестным Транспортная задача линейного программирования заменить точными равенствами.

В итоге приходим к соотношению:

(6.4)
Транспортная задача линейного программирования (для всех свободных неизвестных Транспортная задача линейного программирования)

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

7.Пример решения транспортной задачи.

В городе N имеется 4 склада Аi, на которых хранится ткань (в рулонах) и 5 магазинов Bj, занимающихся продажей ткани. Ниже, в таблице, приведены данные по количеству рулонов на каждом складе, запросы магазинов и стоимость перевозки одного рулона из Аi в Bj. Необходимо составить такой план перевозок, при котором запросы магазинов будут удовлетворены при минимальной суммарной стоимости перевозок.

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

Склад

B1

(b1=40)

B2

(b2=50)

B3

(b3=15)

B4

(b4=75)

B5

(b5=40)

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

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

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

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