-- 3 --
Критерий оптимальности базисного решения транспортной задачи. Методы отыскания оптимального решения.
Задача, двойственная к транспортной.
Пример решения транспортной задачи.
Выводы.
1.История зарождения и создания линейного программирования.
Каждый человек ежедневно, не всегда осознавая это, решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда ограничены. Жизнь была бы менее интересной, если бы это было не так. Не трудно выиграть сражение, имея армию в 10 раз большую, чем у противника. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий. Раньше план в таких случаях составлялся “на глазок” (теперь, впрочем, зачастую тоже). В середине XX века был создан специальный математический аппарат, помогающий это делать “по науке”. Соответствующий раздел математики называется математическим программированием. Слово “программирование” здесь и в аналогичных терминах (“линейное программирование, динамическое программирование” и т.п.) обязано отчасти историческому недоразумению, отчасти неточному переводу с английского. По-русски лучше было бы употребить слово “планирование”. С программированием для ЭВМ математическое программирование имеет лишь то общее, что большинство возникающих на практике задач математического программирования слишком громоздки для ручного счета, решить их можно только с помощью ЭВМ, предварительно составив программу. Временем рождения линейного программирования принято считать 1939г., когда была напечатана брошюра Леонида Витальевича Канторовича “Математические методы организации и планирования производства”. Поскольку методы, изложенные Л.В.Канторовичем, были мало пригодны для ручного счета, а быстродействующих вычислительных машин в то время не существовало, работа Л.В.Канторовича осталась почти не замеченной.
Свое второе рождение линейное программирование получило в начале пятидесятых годов с появлением ЭВМ. Тогда началось всеобщее увлечение линейным программированием, вызвавшее в свою очередь развитие других разделов математического программирования. В 1975 году академик Л.В.Канторович и американец профессор Т.Купманс получили Нобелевскую премию по экономическим наукам за “вклад в разработку теории и оптимального использования ресурсов в экономике”.
В автобиографии, представленной в Нобелевский комитет, Леонид Витальевич Канторович рассказывает о событиях, случившихся в 1939 году. К нему, 26-летнему профессору-математику, обратились за консультацией сотрудники лаборатории планерного треста, которым нужно было решить задачу о наиболее выгодном распределении материала между станками. Эта задача сводилась к нахождению максимума линейной функции, заданной на многограннике. Максимум такой функции достигался в вершине, однако число вершин в этой задаче достигало миллиарда. Поэтому простой перебор вершин не годился. Леонид Витальевич писал: “оказалось, что эта задача не является случайной. Я обнаружил большое число разнообразных по содержанию задач, имеющих аналогичный математический характер: наилучшее использование посевных площадей, выбор загрузки оборудования, рациональный раскрой материала, распределение транспортных грузопотоков… Это настойчиво побудило меня к поиску эффективного метода их решения”. И уже летом 1939 года была сдана в набор книга Л.В.Канторовича “Математические методы организации и планирования производства”, в которой закладывались основания того, что ныне называется математической экономикой.
Однако идеи Л.В.Канторовича не встретили понимания в момент их зарождения, были объявлены ересью, и его работа была прервана. Концепции Леонида Витальевича вскоре после войны были переоткрыты на западе. Американский экономист Т.Купманс в течение многих лет привлекал внимание математиков к ряду задач, связанных с военной тематикой. Он активно способствовал тому, чтобы был организован математический коллектив для разработки этих проблем. В итоге было осознано, что надо научиться решать задачи о нахождении экстремумов линейных функций на многогранниках, задаваемых линейными неравенствами. По предложению Купманса этот раздел математики получил название линейного программирования.
Американский математик А.Данциг в 1947 году разработал весьма эффективный конкретный метод численного решения задач линейного программирования (он получил название симплекс метода). Идеи линейного программирования в течение пяти шести лет получили грандиозное распространение в мире, и имена Купманса и Данцига стали повсюду широко известны.
Примерно в это время Купманс узнал, что еще до войны в далекой России уже было сделано нечто похожее на разработку начал линейного программирования. Как легко было бы Данцигу и Купмансу проигнорировать эту информацию! Маленькая книжица, изданная ничтожным тиражом, обращенная даже не к экономистам, а к организаторам производства, с минимумом математики, без четко описанных алгоритмов, без доказательств теорем - словом, стоит ли принимать такую книжку во внимание… Но Купманс настаивает на переводе и издании на западе книги Канторовича. Его имя и идеи становятся известны всем. Воздадим должное благородству американского ученого!
А самому Леониду Витальевичу - как естественно было бы ему, испытав первые грозные удары ретроградов, остеречься от “грехов” молодости, забыть про всю эту экономику и вернуться к математике. Но Л.В.Канторович продолжает писать математические работы, навеянные экономическими идеями, участвует и в конкретных разработках на производстве. При этом (одновременно с Данцигом, но, не зная его работ) он разрабатывает метод, позже названный симплекс-методом. Как только в 50-е годы образуется маленький просвет, и кое-что из запретного становится возможным, он организует группу студентов на экономическом факультете ЛГУ для обучения методам оптимального планирования. А, начиная с 1960 года, Леонид Витальевич занимается только экономической и связанной с нею математической проблемами. Его вклад в этой области был отмечен Ленинской премией в 1965 году (присуждена ему совместно с В.С.Немчиновым и В.В.Новожиловым) и, как уже говорилось, Нобелевской премией в 1975 году.
2.Транспортная задача. Общая постановка, цели, задачи. Основные типы, виды моделей.
Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.
В общей постановке транспортная задача состоит в отыскании опти-мального плана перевозок некоторого однородного груза с баз потребителям .
Различают два типа транспортных задач: но критерию стоимости (план перевозок оптимален, если достигнут минимум затрат на его реализацию) и по критерию времени (план оптимален, если на его реализацию затрачивается минимум времени).
Обозначим количество груза, имеющегося на каждой из баз (запасы), соответственно ,а общее количество имею-щегося в наличии груза-:
;
заказы каждого из потребителей (потребности) обозначим соот-ветственно, а общее количество потребностей - :
,
ПунктыОтправления |
Пункты назначения |
Запасы |
||||
… |
||||||
… |
||||||
… |
||||||
… |
… |
… |
… |
… |
… |
|
… |
||||||
Потребности |
… |
или |
||||
При этом легко заметить, что под символами такого суммирования объединяются только свободные неизвестные (здесь , ).
В рассматриваемой нами системе только два уравнения, а имен-но первое горизонтальное и первое вертикальное, содержат более одного неизвестного из числа выбранных нами для построения базиса. Исключив из первого горизонтального уравнения базисные неизвестные с помощью вертикальных уравнений, мы получаем уравнение
или короче
где символ означает сумму всех свободных неизвестных. Аналогично, исключив из первого вертикального уравнения базисные неизвестные с помощью горизонтальных уравнений, мы получаем уравнение
Так как для закрытой модели транспортной задачи , то полученные нами уравнения (2.2) и (2.2) одинаковы и, исключив из одного из них неизвестное , мы получим уравнение-тождество 0=0, которое из системы вычеркивается.
Итак, преобразование системы (2.1) свелось к замене двух урав-нений (первого горизонтального и первого вертикального) уравне-нием (2.2). Остальные уравнения остаются неизменными. Система приняла вид
В системе (2.3) выделен указанный выше базис: базисные неиз-вестные из первых т уравнений образуют первый столбец матрицы перевозок, а базисные неизвестные остальных уравнений образуют первую строку матрицы перевозок без первого неизвестного [она входит в первое уравнение системы (2.3)]. В системе (2.3) имеется уравнений, выделенный базис содержит неизвест-ных, а, следовательно, и ранг системы (2.1) .
Для решения транспортной задачи необходимо кроме запасов и потребностей знать также и тарифы , т. е. стоимость перевозки единицы груза с базы потребителю .
Совокупность тарифов также образует матрицу, которую можно объединить с матрицей перевозок и данными о запасах и потребностях в одну таблицу:
Пункты Отправления |
Пункты назначения |
Запасы |
|||||||
… |
|||||||||
… |
|||||||||
… |
|||||||||
… |
… |
… |
… |
… |
… |
||||
… |
|||||||||
Потребности |
… |
или |
|||||||
Сумма всех затрат, т. е. стоимость реализации данного плана перевозок, является линейной функцией переменных :
Требуется в области допустимых решений системы уравнений (2.1) и (2.1.1) найти решение, минимизирующее линейную функцию (2.4).
Таким образом, мы видим, что транспортная задача является задачей линейного программирования. Для ее решения применяют также симплекс-метод, но в силу специфики задачи здесь можно обойтись без симплекс-таблиц. Решение можно получить путем неко-торых преобразований таблицы перевозок. Эти преобразования соответствуют переходу от одного плана перевозок к другому. Но, как и в общем случае, оптимальное решение ищется среди базисных решений. Следовательно, мы будем иметь дело только с базисными (или опорными) планами. Так как в данном случае ранг системы ограничений-уравнений равен то среди всех неизвест-ных выделяется базисных неизвестных, а остальные ·
неизвестных являются свободными. В базис-ном решении свободные неизвестные равны нулю. Обычно эти нули в таблицу не вписывают, оставляя соответствующие клетки пустыми. Таким образом, в таблице перевозок, представляющей опорный план, мы имеем заполненных и · пустых клеток.
Для контроля надо проверять, равна ли сумма чисел в заполнен-ных клетках каждой строки таблицы перевозок запасу груза на соответствующей базе, а в каждом столбце -- потребности заказчика [этим подтверждается, что данный план является решением системы (2.1)].
Замечание 1. Не исключаются здесь и вырожденные случаи, т. е. возможность обращения в нуль одной или нескольких базисных неизвестных. Но эти нули в отличие от нулей свободных неизвест-ных вписываются в соответствующую клетку, и эта клетка считается заполненной.
Замечание 2. Под величинами , очевидно, не обязательно под-разумевать только тарифы. Можно также считать их величинами, пропорциональными тарифам, например, расстояниями от баз до потребителей. Если, например, выражены в тоннах, а в километрах, то величина , определяемая формулой (2.4), является количеством тонно-километров, составляющих объем данного плана перевозок. Очевидно, что затраты на перевозки пропорциональны количеству тонно-километров и, следовательно, будут минимальными при минимуме S. В этом случае вместо матрицы тарифов мы имеем матрицу расстояний.
3. Методы составления начального опорного плана.
Как и в общем случае, решение транспортной задачи начинается с отыскания первого опорного плана (исходного базиса). Мы рас-смотрим два наиболее распространенных метода построения такого базиса. Суть обоих этих методов состоит в том, что базисный план составляется последова-тельно, в несколько шагов (точнее, шагов). На каждом из этих шагов заполняется одна клетка, притом так, что, либо пол-ностью удовлетворяется один из заказчиков (тот, в столбце кото-рого находится заполняемая клетка), либо полностью вывозится весь запас груза с одной из баз (с той, в строке которой находится заполняемая клетка).
В первом случае мы можем исключить столбец, содержащий заполненную на этом шаге клетку, и считать, что задача свелась к заполнению таблицы с числом столбцов, на единицу меньшим, чем было перед этим шагом, но с тем же количеством строк и с соот-ветственно измененным запасом груза на одной из баз (на той базе, которой был удовлетворен заказчик на данном шаге).
Во втором случае исключается строка, содержащая заполняемую клетку, и счи-тается, что таблица сузилась на одну строку при неизменном количестве столбцов и при соответствующем изменении потреб-ности заказчика, в столбце которого находится заполняемая клетка.
Начиная с первоначально данной таблицы и повторив раз описанный шаг, мы придем к “таблице”, состоящей из одной строки и одного столбца (иначе говоря, из одной пустой клетки). Другими словами, мы пришли к задаче с одной базой и с одним потребителем, причем потребности этого единственного заказчика равны запасу груза на этой единственной базе. Заполнив последнюю клетку, мы освобождаем последнюю базу и удовлетворяем потреб-ность последнего заказчика. В результате, совершив шагов, мы и получим искомый опорный план.
Замечание. Может случиться, что уже на некотором (но не на последнем!) шаге потребность очередного заказчика окажется рав-ной запасу груза на очередной базе. Тогда после заполнения оче-редной клетки объем таблицы как бы одновременно уменьшается на одни столбец и на одну строку. Но и при этом мы должны считать, что уменьшение объема таблицы происходит либо на один столбец, а на базе сохраняется “остаток” равный нулю, либо на одну строку, а у заказчика еще осталась неудовлетворенная “потребность” в количестве нуля единиц груза, которая и удовле-творяется на одном из следующих шагов. Этот нуль (“запас” или “потребностью” - безразлично) надо записать в очередную заполняе-мую клетку на одном из последующих шагов. Так как при этом оказывается равной нулю одна из базисных неизвестных, то мы имеем дело с вырожденным случаем.
Различие методов отыскания первого опорного плана состоит в различии способов набора заполняемой клетки.
1.Диагональный метод, или метод северо-западного угла. При этом методе на каждом шаге построения первого опорного плана заполняется левая верхняя клетка (северо-западный угол) остав-шейся части таблицы. При таком методе заполнение таблицы начи-нается с клетки неизвестного и заканчивается в клетке неизвест-ного , т. е. идет как бы по диагонали таблицы перевозок.
Пример.
Пункты Отправления |
Пункты назначения |
Запасы |
||||||||||
70 |
50 |
15 |
80 |
70 |
300 |
|||||||
170 |
110 |
20 |
||||||||||
80 |
90 |
40 |
60 |
85 |
150 |
|||||||
80 |
70 |
|||||||||||
50 |
10 |
90 |
11 |
25 |
250 |
|||||||
50 |
200 |
|||||||||||
Потребности |
170 |
110 |
100 |
120 |
200 |
700 |
||||||
Заполнение таблицы начинается с ее северо-западного угла, т. е. клетки с неизвестным . Первая база может полностью удовле-творить потребность первого заказчика . Полагая , вписываем это значение в клетку и исключаем из рассмотрения первый столбец. На базе остается измененный запас . В оставшейся новой таблице с тремя строками и четырьмя столбцами ; северо-западным углом будет клетка для неизвестного . Первая база с запасом может полностью удовлетворить потребность второго заказчика . Полагаем , вписываем это значе-ние в клетку и исключаем из рассмотрения второй столбец. На базе остается новый остаток (запас) . В оставшейся новой таблице с тремя строками и тремя столбцами северо-западным углом будет клетка для неизвестного . Теперь третий заказчик может принять весь запас с базы . Полагаем , вписываем это значение в клетку и исключаем из рассмотрения первую строку. У заказ-чика из осталась еще не удовлетворенной потребность .
Теперь переходим к заполнению клетки для неизвестного и т.д.
Через шесть шагов у нас останется одна база с запасом груза (остатком от предыдущего шага) и один пункт с потреб-ностью. Соответственно этому имеется одна свободная клетка, которую и заполняем, положив . План составлен. Базис образован неизвестными . Правиль-ность составленного плана легко проверить, подсчитав суммы чисел, стоящих в заполненных клетках по строкам и столбцам.
ПунктыОтправления |
Пункты назначения |
Запасы |
||||||||||
70 |
50 |
15 |
80 |
70 |
300 |
|||||||
20 |
100 |
180 |
||||||||||
80 |
90 |
40 |
60 |
85 |
150 |
|||||||
150 |
||||||||||||
50 |
10 |
90 |
11 |
25 |
250 |
|||||||
110 |
120 |
20 |
||||||||||
Потребности |
170 |
110 |
100 |
120 |
200 |
700 |
||||||
ПунктыОтправления |
Пункты назначения |
Запасы |
||||||||||
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 будем считать равной нулю. Введением фиктивного пункта назначения B n+1 с его заявкой b n+1 мы сравняли баланс транспортной задачи, и теперь ее можно решать, как обычную транспортную задачу с правильным балансом.
Транспортная задача с избытком заявок.
Эту задачу можно свести к обычной транспортной задаче с правильным балансом, если ввести фиктивный пункт отправления Am+1 с запасом am+1 равным недостающему запасу, и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равной нулю.
Задача, двойственная к транспортной.
Построим задачу, двойственную к транспортной. С этой целью вспомним, что каждому пункту отправления и назначения отвечает определенное огра-ничение
В то же время каждому ограничению из (6.1) сопоставляется определенная неизвестная в двойствен-ной задаче. Тем самым устанавливается соответствие между всеми пунктами и и всеми неиз-вестными двойственной задачи.
Обозначим неизвестную в двойственной задаче, отвечаю-щую пункту отправления , через , а пункту назначения - через .
Каждому неизвестному в транспортной задаче соответ-ствует ограничение, связывающее неизвестные в двойственной задаче. Неизвестное входит ровно в два ограничения системы (6.1): одно из них отвечает пункту , а другое - пункту . В обоих этих уравнениях коэффициент при равен 1. Поэтому соответствующее ограничение в двой-ственной задаче имеет вид
.
Правая часть неравенства (6.2) равна , потому что именно с этим коэффициентом неизвестная входит в миними-зируемую формулу (2.4).
(для всех свободных неизвестных )
Тем самым мы убеждаемся, что признак оптимальности в работе по методу потенциалов совпадает с необходимым и достаточ-ным условием оптимальности.
7.Пример решения транспортной задачи.
В городе N имеется 4 склада Аi, на которых хранится ткань (в рулонах) и 5 магазинов Bj, занимающихся продажей ткани. Ниже, в таблице, приведены данные по количеству рулонов на каждом складе, запросы магазинов и стоимость перевозки одного рулона из Аi в Bj. Необходимо составить такой план перевозок, при котором запросы магазинов будут удовлетворены при минимальной суммарной стоимости перевозок.
Магазины Склад |
B1 (b1=40) |
B2 (b2=50) |
B3 (b3=15) |
B4 (b4=75) |
B5 (b5=40) |
|
А1 (а1=50) |
1,0 |
2,0 |
3,0 |
2,5 |
3,5 |
|
А2(а2=20) |
0,4 |
3,0 |
1,0 |
2,0 |
3,0 |
|
А3(а3=75) |
0,7 |
1,0 |
1,0 |
0,8 |
1,5 |
|
А4(а4=80) |
1,2 |
2,0 |
2,0 |
1,5 |
2,5 |
|
В данном случае Уai=225 >Уbj=220 => имеем дело с открытой моделью транспортной задачи. Сведем ее к закрытой введением фиктивного магазина B6 с потребностью b5=225-220=5 и стоимостью перевозок сi6=0.Имеем таблицу:
Магазины Склад |
B1 (b1=40) |
B2 (b2=50) |
B3 (b3=15) |
B4 (b4=75) |
B5 (b5=40) |
B6 (b6=5) |
|
А1 (а1=50) |
1,0 |
2,0 |
3,0 |
2,5 |
3,5 |
0 |
|
А2(а2=20) |
0,4 |
3,0 |
1,0 |
2,0 |
3,0 |
0 |
|
А3(а3=75) |
0,7 |
1,0 |
1,0 |
0,8 |
1,5 |
0 |
|
А4(а4=80) |
1,2 |
2,0 |
2,0 |
1,5 |
2,5 |
0 |
|
Математическая модель: обозначим xij - количество товара, перевозимого из Аi в Bj. Тогда
x11 x12 x13 x14 x15 x16
x21 x22 x23 x24 x25 x26
X = x31 x32 x33 x34 x35 x36 - матрица перевозок.
x41 x42 x43 x44 x45 x46
min(x11+2x12+3x13+2,5x14+3,5x15+0,4x21+3x22+x23+2x24+3x25+0,7x31+x32+x33+0,8x34+1,5x35++1,2x41+2x42+2x43+1,5x44+2,5x45) (1)
x11+x12+x13+x14+x15+x16=50
x21+x22+x23+x24+x25+x26=20
x31+x32+x33+x34+x35+x36=75
x41+x42+x43+x44+x45+x46=80
x11+x21+x31+x41=40 (2)
x12+x22+x32+x42=50
x13+x23+x33+x43=15
x14+x24+x34+x44=75
x15+x25+x35+x45=40
x16+x26+x36+x46=5
xij=0 (i=1,2,3,4 ; j=1,2,3,4,5,6 ) (3)
Двойственная ЗЛП:
max(50u1+20u2+75u3+80u4+40v1+50v2+15v3+75v4+40v5+5v6) (1*)
u1+v1=1
u1+v2=2
u1+v3=3 (2*)
u1+v4=2,5
u1+v5=3,5
u1+v6=0
ui,vj - произвольные (i=1,2,3,4 ; j=1,2,3,4,5,6 ) (3*)
Будем искать первоначальный план по методу наименьшей стоимости:
1) x21=20 и 2-ую строку исключаем.2) x31=20 и 1-ый столбец исключаем.
3) x34=55 и 3-ю строку исключаем.4) x44=20 и 4-ый столбец исключаем.
5) x12=50 и 1-ю строку и 2-ой столбец исключаем и x32=0. 6) x43=150 и 3-ий столбец исключаем.7) x45=40 и 5-ый столбец исключаем.x46=5.Составим таблицу. Здесь и далее в нижнем правом углу записываем значение перевозки.
Магазины Склад |
B1 (b1=40) |
B2 (b2=50) |
B3 (b3=15) |
B4 (b4=75) |
B5 (b5=40) |
B6 (b6=5) |
|
А1 (а1=50) |
1,0 |
2,0 |
3,0 |
2,5 |
3,5 |
0 |
|
А2(а2=20) |
0,4 |
3,0 |
1,0 |
2,0 |
3,0 |
0 |
|
А3(а3=75) |
0,7 |
1,0 |
1,0 |
0,8 |
1,5 |
0 |
|
А4(а4=80) |
1,2 |
2,0 |
2,0 |
1,5 |
2,5 |
0 |
|
Стоимость 1-ого плана:
D1=2*50+0,4*20+0,7*20+0,8*55+2*15+1,5*20+2,5*40=326.
Будем улучшать этот план методом потенциалов: ui- потенциал Аi ,vj- потенциал Bj. Тогда u1+v2=2,u2+v1=0,4, u3+v1=0,7, u3+v2=1, u3+v4=0,8, u4+v3=2, u4+v4=1,5, u4+v5=2,5 ,u4+v6=0.Положим u1=0,тогда v2=2,u3=-1,v1=1,7,v4=1,8, u2=-1,3,u4=-0,3, v3=2,3,v5=2,8,v6=0,3.Составим таблицу:
Магазины Склад |
B1 (b1=40) v1=1,7 |
B2 (b2=50) v2=2 |
B3 (b3=15) v3=2,3 |
B4 (b4=75) v4=1,8 |
B5 (b5=40) v5=2,8 |
B6 (b6=5) v6=0,3 |
|
А1 (а1=50) U1=0 |
1,0 |
2,0 |
3,0 |
2,5 |
3,5 |
0 |
|
А2(а2=20) U2=-1,3 |
0,4 |
3,0 |
1,0 |
2,0 |
3,0 |
0 |
|
А3(а3=75) U3=-1 |
0,7 |
1,0 |
1,0 |
0,8 |
1,5 |
0 |
|
А4(а4=80) U4=-0,3 |
1,2 |
2,0 |
2,0 |
1,5 |
2,5 |
0 |
|
В верхнем левом углу здесь и далее записываем значение ui+vj-cij. Имеем: u1+v1--c11 =0,7>0, u1+v6-c16 =0,3>0, u3+v3-c33 =0,3>0, u3+v5-c35 =0,3>0,
u4+v1-c41 =0,2>0. => По критерию оптимальности, первый план не оптимален. Далее max(0,7;0,3;0,3;0,3;0,2)=0,7. => Поместим перевозку в клетку А1В1, сместив 20=min(20,50) по циклу, указанному в таблице штрихом. Получим новую таблицу. Найдем потенциалы: u1+v1=1,u1+v2=2,u2+v1=0,4,u3+v2=1, u3+v4=0,8, u4+v3=2, u4+v4=1,5, u4+v5=2,5 , u4+v6=0. Положим u1=0,тогда v1=1,u2=-0,6,v2=2,v4=1,8, u3=-1, u4=-0,3,v3=2,3,v5=2,8,v6=0,3. Составим таблицу:
Магазины Склад |
B1 (b1=40) v1=1 |
B2 (b2=50) v2=2 |
B3 (b3=15) v3=2,3 |
B4 (b4=75) v4=1,8 |
B5 (b5=40) v5=2,8 |
B6 (b6=5) v6=0,3 |
|
А1 (а1=50) U1=0 |
1,0 |
2,0 |
3,0 |
2,5 |
3,5 |
0 |
|
А2(а2=20) U2=-0,6 |
0,4 |
3,0 |
1,0 |
2,0 |
3,0 |
0 |
|
А3(а3=75) U3=-1 |
0,7 |
1,0 |
1,0 |
0,8 |
1,5 |
0 |
|
А4(а4=80) U4=-0,3 |
1,2 |
2,0 |
2,0 |
1,5 |
2,5 |
0 |
|
Стоимость 2-ого плана:
D2=1*20+2*30+0,4*20+1*20+0,8*55+2*15+1,5*20+2,5*40=312.
Имеем:u1+v6-c16 =0,3>0, u2+v3-c23 =0,7>0, u3+v3-c33 =0,3>0, u3+v5-c35 =0,3>0. => По критерию оптимальности, второй план не оптимален. Далее max(0,3;0,7;0,3;0,3)=0,7 => Поместим перевозку в клетку А2В3, сместив 15=min(20,30,55,15) по циклу, указанному в таблице штрихом. Получим новую таблицу. Найдем потенциалы: u1+v1=1,u1+v2=2,u2+v1=0,4,u3+v2=1, u3+v4=0,8, u2+v3=1, u4+v4=1,5, u4+v5=2,5 , u4+v6=0. Положим u1=0,тогда v1=1,u2=-0,6,v2=2,v4=1,8, u3=-1, u4=-0,3,v3=1,6, v5=2,8, v6=0,3. Составим таблицу:
Магазины Склад |
B1 (b1=40) v1=1 |
B2 (b2=50) v2=2 |
B3 (b3=15) v3=1,6 |
B4 (b4=75) v4=1,8 |
B5 (b5=40) v5=2,8 |
B6 (b6=5) v6=0,3 |
|
А1 (а1=50) U1=0 |
1,0 |
2,0 |
3,0 |
2,5 |
3,5 |
0 |
|
А2(а2=20) U2=-0,6 |
0,4 |
3,0 |
1,0 |
2,0 |
3,0 |
0 |
|
А3(а3=75) U3=-1 |
0,7 |
1,0 |
1,0 |
0,8 |
1,5 |
0 |
|
А4(а4=80) U4=-0,3 |
1,2 |
2,0 |
2,0 |
1,5 |
2,5 |
0 |
|
Стоимость 3-его плана:
D3=1*35+2*15+0,4*5+1*15+0,8*40+1*35+1,5*35+2,5*40=301,5.
Имеем:u1+v6-c16 =0,3>0,u3+v5-c35 =0,3>0. => По критерию оптимальности, третий план не оптимален. Далее max(0,3;0,3)=0,3. => Поместим перевозку в клетку А3В5, сместив 40=min(40,40) по циклу, указанному в таблице штрихом. Получим новую таблицу. Чтобы 4-ый план был невырожденным, оставим в клетке А4В5 нулевую перевозку. Найдем потенциалы: u1+v1=1,u1+v2=2,u2+v1=0,4,u3+v2=1, u4+v5=2,5, u2+v3=1, u4+v4=1,5, u3+v5=1,5 , u4+v6=0. Положим u1=0,тогда v1=1,u2=-0,6,v2=2,v4=1,5, u3=-1,u4=0, v3=1,6, v5=2,5, v6=0. Составим таблицу:
Магазины Склад |
B1 (b1=40) v1=1 |
B2 (b2=50) v2=2 |
B3 (b3=15) v3=1,6 |
B4 (b4=75) v4=1,5 |
B5 (b5=40) v5=2,5 |
B6 (b6=5) v6=0 |
|
А1 (а1=50) U1=0 |
1,0 |
2,0 |
3,0 |
2,5 |
3,5 |
0 |
|
А2(а2=20) U2=-0,6 |
0,4 |
3,0 |
1,0 |
2,0 |
3,0 |
0 |
|
А3(а3=75) U3=-1 |
0,7 |
1,0 |
1,0 |
0,8 |
1,5 |
0 |
|
А4(а4=80) U4=0 |
1,2 |
2,0 |
2,0 |
1,5 |
2,5 |
0 |
|
Стоимость 4-ого плана: D4=1*35+2*15+0,4*5+1*15+1*35+1,5*40+1,5*75=289,5.
Для всех клеток последней таблицы выполнены условия оптимальности:
1)ui+vj-сij=0 для клеток, занятых перевозками;
2)ui+vj-сij ?0 для свободных клеток.
Несодержательные ответы:
Прямой ЗЛП:
35 15 0 0 0 0
5 0 15 0 0 0
X = 0 35 0 0 40 0
0 0 0 75 0 5
min=289,5.
Двойственной ЗЛП:
U1=0 ; U2=-0,6 ; U3=-1 ; U4=0 ; V1=1 ; V2=2 ; V3=1,6 ; V4=1,5 ; V5=2,5 ; V6=0.
max=289,5.
Так как min=max, то по критерию оптимальности найдены оптимальные решения прямой и двойственной ЗЛП. Содержательный ответ: Оптимально перевозить так:
Из А1 в B1 - 35 рулонов полотна;
Из А1 в B2 - 15 рулонов полотна;
Из А2 в B1 - 5 рулонов полотна;
Из А2 в B3 - 15 рулонов полотна;
Из А3 в B2 - 35 рулонов полотна;
Из А3 в B5 - 40 рулонов полотна;
Из А4 в B4 - 75 рулонов полотна.
При этом стоимость минимальна и составит Dmin=289,5. 5 рулонов полотна необходимо оставить на складе А4 для их последующей перевозки в другие магазины.
8.Выводы.
В курсовой работе изложены основные подходы и методы решения транспортной задачи, являющейся одной из наиболее распространенных задач линейного программирования. Решение данной задачи позволяет разработать наиболее рациональные пути и способы транспортирования товаров, устранить чрезмерно дальние, встречные, повторные перевозки. Все это сокращает время продвижения товаров, уменьшает затраты предприятий и фирм, связанные с осуществлением процессов снабжения сырьем, материалами, топливом, оборудованием и т.д.
Алгоритм и методы решения транспортной задачи могут быть использованы при решении некоторых экономических задач, не имеющих ничего общего с транспортировкой груза. В этом случае величины тарифов cij имеют различный смысл в зависимости от конкретной экономической задачи. К таким задачам относятся следующие:
- оптимальное закрепление за станками операций по обработке деталей. В них cij является таким экономическим показателем, как производительность. Задача позволяет определить, сколько времени и на какой операции нужно использовать каждый из станков, чтобы обработать максимальное количество деталей. Так как транспортная задача требует нахождения минимума, то значения cij берутся с отрицательным знаком;
- оптимальные назначения, или проблема выбора. Имеется m механизмов, которые могут выполнять m различных работ с производительностью cij. Задача позволяет определить, какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности;
- задача о сокращении производства с учетом суммарных расходов на изготовление и транспортировку продукции;
- увеличение производительности автомобильного транспорта за счет минимизации порожнего пробега. Уменьшение порожнего пробега сократит количество автомобилей для перевозок, увеличив их производительность;
- решение задач с помощью метода запрещения перевозок. Используется в том случае, если груз от некоторого поставщика по каким-то причинам не может быть отправлен одному из потребителей. Данное ограничение можно учесть, присвоив соответствующей клетке достаточно большое значение стоимости, тем самым в эту клетку не будут производиться перевозки.
Таким образом, важность решения данной задачи для экономики несомненна. Приятно осознавать, что у истоков создания теории линейного программирования и решения, в том числе и транспортной задачи, стоял русский ученый - Леонид Витальевич Канторович.
Список используемой литературы:
1. Кузнецов А.В., Сакович В.А., Холод Н.И. ”Высшая математика. Математическое программирование ”, Минск, Вышейшая школа, 2001г.
2. Красс М.С., Чупрынов Б.П. ”Основы математики и ее приложения в экономическом образовании”, Издательство “Дело”, Москва 2001г.
3. В.И. Ермаков “Общий курс высшей математики для экономистов”, Москва, Инфра-М, 2000г.
! | Как писать курсовую работу Практические советы по написанию семестровых и курсовых работ. |
! | Схема написания курсовой Из каких частей состоит курсовик. С чего начать и как правильно закончить работу. |
! | Формулировка проблемы Описываем цель курсовой, что анализируем, разрабатываем, какого результата хотим добиться. |
! | План курсовой работы Нумерованным списком описывается порядок и структура будующей работы. |
! | Введение курсовой работы Что пишется в введении, какой объем вводной части? |
! | Задачи курсовой работы Правильно начинать любую работу с постановки задач, описания того что необходимо сделать. |
! | Источники информации Какими источниками следует пользоваться. Почему не стоит доверять бесплатно скачанным работа. |
! | Заключение курсовой работы Подведение итогов проведенных мероприятий, достигнута ли цель, решена ли проблема. |
! | Оригинальность текстов Каким образом можно повысить оригинальность текстов чтобы пройти проверку антиплагиатом. |
! | Оформление курсовика Требования и методические рекомендации по оформлению работы по ГОСТ. |
→ | Разновидности курсовых Какие курсовые бывают в чем их особенности и принципиальные отличия. |
→ | Отличие курсового проекта от работы Чем принципиально отличается по структуре и подходу разработка курсового проекта. |
→ | Типичные недостатки На что чаще всего обращают внимание преподаватели и какие ошибки допускают студенты. |
→ | Защита курсовой работы Как подготовиться к защите курсовой работы и как ее провести. |
→ | Доклад на защиту Как подготовить доклад чтобы он был не скучным, интересным и информативным для преподавателя. |
→ | Оценка курсовой работы Каким образом преподаватели оценивают качества подготовленного курсовика. |
Курсовая работа | Деятельность Движения Харе Кришна в свете трансформационных процессов современности |
Курсовая работа | Маркетинговая деятельность предприятия (на примере ООО СФ "Контакт Плюс") |
Курсовая работа | Политический маркетинг |
Курсовая работа | Создание и внедрение мембранного аппарата |
Курсовая работа | Социальные услуги |
Курсовая работа | Педагогические условия нравственного воспитания младших школьников |
Курсовая работа | Деятельность социального педагога по решению проблемы злоупотребления алкоголем среди школьников |
Курсовая работа | Карибский кризис |
Курсовая работа | Сахарный диабет |
Курсовая работа | Разработка оптимизированных систем аспирации процессов переработки и дробления руд в цехе среднего и мелкого дробления Стойленского ГОКа |
Курсовая работа | Оценка финансового состояния предприятия |
Курсовая работа | Аудит расчетов с персоналом по оплате труда |
Курсовая работа | Договор аренды предприятия |
Курсовая работа | Место и проблемы развивающихся стран в мировом хозяйстве |
Курсовая работа | Стили управления |
Курсовая работа | Правовое регулирование трудового договора |
Курсовая работа | Производственная и общая структура предприятия |
Курсовая работа | Учет и анализ наличных и безналичных денежных потоков |
Курсовая работа | Договор международных перевозок |
Курсовая работа | Нравственное воспитание младших школьников |
Курсовая работа | Сертификация по стандартам системы менеджмента качества |
Курсовая работа | Формирование основ здорового образа жизни у учащихся общеобразовательных школ |
Курсовая работа | Семья как основа развития личности |
Курсовая работа | Прогнозирование и программирование социально-экономического развития региона |
Курсовая работа | Бюджетирование на предприятии |