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

Курсовая работа по дисциплине экономико–математические методы


Международный университет

Калининградский филиал

Специальность-менеджмент

1.История зарождения и создания линейного программирования.

Каждый человек ежедневно, не всегда осознавая это, решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда ограничены. Жизнь была бы менее интересной, если бы это было не так. Не трудно выиграть сражение, имея армию в 10 раз большую, чем у противника. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий. Раньше план в таких случаях составлялся “на глазок” (теперь, впрочем, зачастую тоже). В середине XX века был создан специальный математический аппарат, помогающий это делать “по науке”. Соответствующий раздел математики называется математическим программированием. Слово “программирование” здесь и в аналогичных терминах (“линейное программирование, динамическое программирование” и т.п.) обязано отчасти историческому недоразумению, отчасти неточному переводу с английского. По-русски лучше было бы употребить слово “планирование”. С программированием для ЭВМ математическое программирование имеет лишь то общее, что большинство возникающих на практике задач математического программирования слишком громоздки для ручного счета, решить их можно только с помощью ЭВМ, предварительно составив программу. Временем рождения линейного программирования принято считать 1939г., когда была напечатана брошюра Леонида Витальевича Канторовича “Математические методы организации и планирования производства”. Поскольку методы, изложенные Л.В.Канторовичем, были мало пригодны для ручного счета, а быстродействующих вычислительных машин в то время не существовало, работа Л.В.Канторовича осталась почти не замеченной.

Свое второе рождение линейное программирование получило в начале пятидесятых годов с появлением ЭВМ. Тогда началось всеобщее увлечение линейным программированием, вызвавшее в свою очередь развитие других разделов математического программирования. В 1975 году академик Л.В.Канторович и американец профессор Т.Купманс получили Нобелевскую премию по экономическим наукам за “вклад в разработку теории и оптимального использования ресурсов в экономике”.

В автобиографии, представленной в Нобелевский комитет, Леонид Витальевич Канторович рассказывает о событиях, случившихся в 1939 году. К нему, 26-летнему профессору-математику, обратились за консультацией сотрудники лаборатории планерного треста, которым нужно было решить задачу о наиболее выгодном распределении материала между станками. Эта задача сводилась к нахождению максимума линейной функции, заданной на многограннике. Максимум такой функции достигался в вершине, однако число вершин в этой задаче достигало миллиарда. Поэтому простой перебор вершин не годился. Леонид Витальевич писал: “оказалось, что эта задача не является случайной. Я обнаружил большое число разнообразных по содержанию задач, имеющих аналогичный математический характер: наилучшее использование посевных площадей, выбор загрузки оборудования, рациональный раскрой материала, распределение транспортных грузопотоков… Это настойчиво побудило меня к поиску эффективного метода их решения”. И уже летом 1939 года была сдана в набор книга Л.В.Канторовича “Математические методы организации и планирования производства”, в которой закладывались основания того, что ныне называется математической экономикой.

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

Американский математик А.Данциг в 1947 году разработал весьма эффективный конкретный метод численного решения задач линейного программирования (он получил название симплекс метода). Идеи линейного программирования в течение пяти шести лет получили грандиозное распространение в мире, и имена Купманса и Данцига стали повсюду широко известны.

Примерно в это время Купманс узнал, что еще до войны в далекой России уже было сделано нечто похожее на разработку начал линейного программирования. Как легко было бы Данцигу и Купмансу проигнорировать эту информацию! Маленькая книжица, изданная ничтожным тиражом, обращенная даже не к экономистам, а к организаторам производства, с минимумом математики, без четко описанных алгоритмов, без доказательств теорем – словом, стоит ли принимать такую книжку во внимание… Но Купманс настаивает на переводе и издании на западе книги Канторовича. Его имя и идеи становятся известны всем. Воздадим должное благородству американского ученого!

А самому Леониду Витальевичу – как естественно было бы ему, испытав первые грозные удары ретроградов, остеречься от “грехов” молодости, забыть про всю эту экономику и вернуться к математике. Но Л.В.Канторович продолжает писать математические работы, навеянные экономическими идеями, участвует и в конкретных разработках на производстве. При этом (одновременно с Данцигом, но, не зная его работ) он разрабатывает метод, позже названный симплекс-методом. Как только в 50-е годы образуется маленький просвет, и кое-что из запретного становится возможным, он организует группу студентов на экономическом факультете ЛГУ для обучения методам оптимального планирования. А, начиная с 1960 года, Леонид Витальевич занимается только экономической и связанной с нею математической проблемами. Его вклад в этой области был отмечен Ленинской премией в 1965 году (присуждена ему совместно с В.С.Немчиновым и В.В.Новожиловым) и, как уже говорилось, Нобелевской премией в 1975 году.

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

Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.

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

Различают два типа транспортных задач: но критерию стоимости (план перевозок оптимален, если достигнут минимум затрат на его реализацию) и по критерию времени (план оптимален, если на его реализацию затрачивается минимум времени).

(1.1)
Обозначим количество груза, имеющегося на каждой из Транспортная задача линейного программирования баз (запасы), соответственно Транспортная задача линейного программирования,а общее количество имеющегося в наличии груза–Транспортная задача линейного программирования:

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

(1.2)
заказы каждого из потребителей (потребности) обозначим соответственноТранспортная задача линейного программирования, а общее количество потребностей – Транспортная задача линейного программирования:

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

(1.3)
Тогда при условии

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

(1.4)
мы имеем закрытую модель, а при условии

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

– открытую модель транспортной задачи.

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

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

План перевозок с указанием запасов и потребностей удобно записывать в виде следующей таблицы, называемой таблицей перевозок:

Пункты

Отправления

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Потребности

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

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

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

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

или

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

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

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

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

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

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

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

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

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

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

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

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

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

или короче

(2.2)

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

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

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

Так как для закрытой модели транспортной задачи Транспортная задача линейного программирования, то полученные нами уравнения (2.2) и (2.2’) одинаковы и, исключив из одного из них неизвестное Транспортная задача линейного программирования, мы получим уравнение-тождество 0=0, которое из системы вычеркивается.

Транспортная задача линейного программированияИтак, преобразование системы (2.1) свелось к замене двух уравнений (первого горизонтального и первого вертикального) уравнением (2.2). Остальные уравнения остаются неизменными. Система приняла вид

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

В системе (2.3) выделен указанный выше базис: базисные неизвестные из первых т уравнений образуют первый столбец матрицы перевозок, а базисные неизвестные остальных уравнений образуют первую строку матрицы перевозок без первого неизвестного Транспортная задача линейного программирования [она входит в первое уравнение системы (2.3)]. В системе (2.3) имеется Транспортная задача линейного программирования уравнений, выделенный базис содержит Транспортная задача линейного программирования неизвестных, а, следовательно, и ранг системы (2.1) Транспортная задача линейного программирования.

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

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

Пункты

Отправления

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Потребности

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

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

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

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

или

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

Сумма всех затрат, т. е. стоимость реализации данного плана перевозок, является линейной функцией переменных Транспортная задача линейного программирования:

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

Требуется в области допустимых решений системы уравнений (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

Заполнение таблицы начинается с ее северо-западного угла, т. е. клетки с неизвестным Транспортная задача линейного программирования. Первая база Транспортная задача линейного программирования может полностью удовлетворить потребность первого заказчика Транспортная задача линейного программирования Транспортная задача линейного программирования. Полагая Транспортная задача линейного программирования, вписываем это значение в клетку Транспортная задача линейного программирования и исключаем из рассмотрения первый столбец. На базе Транспортная задача линейного программирования остается измененный запас Транспортная задача линейного программирования. В оставшейся новой таблице с тремя строками Транспортная задача линейного программирования и четырьмя столбцами Транспортная задача линейного программирования; северо-западным углом будет клетка для неизвестного Транспортная задача линейного программирования. Первая база с запасом Транспортная задача линейного программированияможет полностью удовлетворить потребность второго заказчика Транспортная задача линейного программирования Транспортная задача линейного программирования. Полагаем Транспортная задача линейного программирования, вписываем это значение в клетку Транспортная задача линейного программирования и исключаем из рассмотрения второй столбец. На базе Транспортная задача линейного программирования остается новый остаток (запас) Транспортная задача линейного программирования. В оставшейся новой таблице с тремя строками Транспортная задача линейного программирования и тремя столбцами Транспортная задача линейного программирования северо-западным углом будет клетка для неизвестного Транспортная задача линейного программирования. Теперь третий заказчик Транспортная задача линейного программирования может принять весь запас с базы Транспортная задача линейного программирования Транспортная задача линейного программирования. Полагаем Транспортная задача линейного программирования, вписываем это значение в клетку Транспортная задача линейного программирования и исключаем из рассмотрения первую строку. У заказчика из Транспортная задача линейного программирования осталась еще не удовлетворенной потребность Транспортная задача линейного программирования.

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

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

Общий объем перевозок в тонно-километрах для этого плана составит

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

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

Пример.

Пункты

Отправления

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

тогда как по исходному плану он составил Транспортная задача линейного программирования. Имеем снижение объема перевозок на 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)

А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

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

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

50
2,0

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

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

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

0
А2(а2=20)

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

20

3,0 1,0 2,0 3,0 0
А3(а3=75)

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

20

0
1,0

1,0

55
0,8

1,5 0
А4(а4=80) 1,2 2,0

15
2,0

20
1,5

40
2,5

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

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

  0,7

А1 (а1=50)

U1=0

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

0
1,0

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

- 0,7
50
2,0

- 0,7
3,0

- 0,7
2,5

 0,3

3,5

0

0
А2(а2=20)

U2=-1,3

- 2,3
20
0,4

0
3,0

- 1,5
1,0

- 1,5
2,0

- 1
3,0

0

0
А3(а3=75)

U3=-1

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

0
0,7

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

20

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

  0,3

0
1,0

0
1,0

  0,3

55
0,8

- 0,7
1,5

0

  0,2

А4(а4=80)

U4=-0,3

- 0,3
1,2

0
2,0

0
15
2,0

0
20
1,5

0
40
2,5

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

0
А1 (а1=50)

U1=0

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

0
1,0

20

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

- 0,7
30
2,0

- 0,7
3,0

- 0,7
2,5

 0,3

3,5

0

0
А2(а2=20)

U2=-0,6

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

- 1,6
20
0,4

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

  0,7

3,0

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

- 0,8
1,0

- 0,8
2,0

- 0,3
3,0

0

-0,7
А3(а3=75)

U3=-1

0
0,7

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

  0,3

20
1,0

0
1,0

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

  0,3

55
0,8

- 0,7
1,5

0

-0,5
А4(а4=80)

U4=-0,3

- 0,3
1,2

0
2,0

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

0
15
2,0

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

0
20
1,5

0
40
2,5

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

0
А1 (а1=50)

U1=0

0
1,0

35

-1,4
15
2,0

- 0,7
3,0

- 0,7
2,5

 0,3

3,5

0

0
А2(а2=20)

U2=-0,6

- 1,6
5
0,4

0
3,0

15
- 0,8
1,0

- 0,8
2,0

- 0,3
3,0

0

-0,7
А3(а3=75)

U3=-1

0
0,7

-0,4
35
1,0

0
1,0

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

  0,3

40
0,8

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

- 0,7
1,5

0

-0,5
А4(а4=80)

U4=-0,3

- 0,3
1,2

-0,7
2,0

0
2,0

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

0
35
1,5

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

0
40
2,5

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

0
А1 (а1=50)

U1=0

0
1,0

35

- 1,4
15
2,0

- 1
3,0

- 1
2,5

0
3,5

0

0
А2(а2=20)

U2=-0,6

- 1,6
5
0,4

0
3,0

15
- 1,1
1,0

- 1,1
2,0

- 0,6
3,0

0

-0,7
А3(а3=75)

U3=-1

0
0,7

-0,4
35
1,0

-0,3
1,0

0
0,8

40
- 1
1,5

0

-0,2
А4(а4=80)

U4=0

0
1,2

-0,4
2,0

0
2,0

0
75
1,5

0
0
2,5

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г.