Транспортная задача линейного программирования
Международный университет
Калининградский филиал
Заочное отделение
Специальность-менеджмент
Курсовая работа
по дисциплине экономико–математические методы
Транспортная задача
линейного программирования
![]()

Курсовая работа
по высшей математике
Тема:
”Транспортная задача линейного программирования”
Содержание:
История зарождения и создания линейного программирования.
Транспортная задача. Общая постановка, цели, задачи. Основные типы, виды моделей.
Методы составления начального опорного плана.
Понятие потенциала и цикла.
Критерий оптимальности базисного решения транспортной задачи. Методы отыскания оптимального решения.
Задача, двойственная к транспортной.
Пример решения транспортной задачи.
Выводы.
1.История зарождения и создания линейного программирования.
Каждый человек ежедневно, не всегда осознавая это, решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда ограничены. Жизнь была бы менее интересной, если бы это было не так. Не трудно выиграть сражение, имея армию в 10 раз большую, чем у противника. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий. Раньше план в таких случаях составлялся “на глазок” (теперь, впрочем, зачастую тоже). В середине XX века был создан специальный математический аппарат, помогающий это делать “по науке”. Соответствующий раздел математики называется математическим программированием. Слово “программирование” здесь и в аналогичных терминах (“линейное программирование, динамическое программирование” и т.п.) обязано отчасти историческому недоразумению, отчасти неточному переводу с английского. По-русски лучше было бы употребить слово “планирование”. С программированием для ЭВМ математическое программирование имеет лишь то общее, что большинство возникающих на практике задач математического программирования слишком громоздки для ручного счета, решить их можно только с помощью ЭВМ, предварительно составив программу. Временем рождения линейного программирования принято считать 1939г., когда была напечатана брошюра Леонида Витальевича Канторовича “Математические методы организации и планирования производства”. Поскольку методы, изложенные Л.В.Канторовичем, были мало пригодны для ручного счета, а быстродействующих вычислительных машин в то время не существовало, работа Л.В.Канторовича осталась почти не замеченной.
Свое второе рождение линейное программирование получило в начале пятидесятых годов с появлением ЭВМ. Тогда началось всеобщее увлечение линейным программированием, вызвавшее в свою очередь развитие других разделов математического программирования. В 1975 году академик Л.В.Канторович и американец профессор Т.Купманс получили Нобелевскую премию по экономическим наукам за “вклад в разработку теории и оптимального использования ресурсов в экономике”.
В автобиографии, представленной в Нобелевский комитет, Леонид Витальевич Канторович рассказывает о событиях, случившихся в 1939 году. К нему, 26-летнему профессору-математику, обратились за консультацией сотрудники лаборатории планерного треста, которым нужно было решить задачу о наиболее выгодном распределении материала между станками. Эта задача сводилась к нахождению максимума линейной функции, заданной на многограннике. Максимум такой функции достигался в вершине, однако число вершин в этой задаче достигало миллиарда. Поэтому простой перебор вершин не годился. Леонид Витальевич писал: “оказалось, что эта задача не является случайной. Я обнаружил большое число разнообразных по содержанию задач, имеющих аналогичный математический характер: наилучшее использование посевных площадей, выбор загрузки оборудования, рациональный раскрой материала, распределение транспортных грузопотоков… Это настойчиво побудило меня к поиску эффективного метода их решения”. И уже летом 1939 года была сдана в набор книга Л.В.Канторовича “Математические методы организации и планирования производства”, в которой закладывались основания того, что ныне называется математической экономикой.
Однако идеи Л.В.Канторовича не встретили понимания в момент их зарождения, были объявлены ересью, и его работа была прервана. Концепции Леонида Витальевича вскоре после войны были переоткрыты на западе. Американский экономист Т.Купманс в течение многих лет привлекал внимание математиков к ряду задач, связанных с военной тематикой. Он активно способствовал тому, чтобы был организован математический коллектив для разработки этих проблем. В итоге было осознано, что надо научиться решать задачи о нахождении экстремумов линейных функций на многогранниках, задаваемых линейными неравенствами. По предложению Купманса этот раздел математики получил название линейного программирования.
Американский математик А.Данциг в 1947 году разработал весьма эффективный конкретный метод численного решения задач линейного программирования (он получил название симплекс метода). Идеи линейного программирования в течение пяти шести лет получили грандиозное распространение в мире, и имена Купманса и Данцига стали повсюду широко известны.
Примерно в это время Купманс узнал, что еще до войны в далекой России уже было сделано нечто похожее на разработку начал линейного программирования. Как легко было бы Данцигу и Купмансу проигнорировать эту информацию! Маленькая книжица, изданная ничтожным тиражом, обращенная даже не к экономистам, а к организаторам производства, с минимумом математики, без четко описанных алгоритмов, без доказательств теорем – словом, стоит ли принимать такую книжку во внимание… Но Купманс настаивает на переводе и издании на западе книги Канторовича. Его имя и идеи становятся известны всем. Воздадим должное благородству американского ученого!
А самому Леониду Витальевичу – как естественно было бы ему, испытав первые грозные удары ретроградов, остеречься от “грехов” молодости, забыть про всю эту экономику и вернуться к математике. Но Л.В.Канторович продолжает писать математические работы, навеянные экономическими идеями, участвует и в конкретных разработках на производстве. При этом (одновременно с Данцигом, но, не зная его работ) он разрабатывает метод, позже названный симплекс-методом. Как только в 50-е годы образуется маленький просвет, и кое-что из запретного становится возможным, он организует группу студентов на экономическом факультете ЛГУ для обучения методам оптимального планирования. А, начиная с 1960 года, Леонид Витальевич занимается только экономической и связанной с нею математической проблемами. Его вклад в этой области был отмечен Ленинской премией в 1965 году (присуждена ему совместно с В.С.Немчиновым и В.В.Новожиловым) и, как уже говорилось, Нобелевской премией в 1975 году.
2.Транспортная задача. Общая постановка, цели, задачи. Основные типы, виды моделей.
Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.
В
общей постановке
транспортная
задача состоит
в отыскании
оптимального
плана перевозок
некоторого
однородного
груза с
баз
потребителям
.
Различают два типа транспортных задач: но критерию стоимости (план перевозок оптимален, если достигнут минимум затрат на его реализацию) и по критерию времени (план оптимален, если на его реализацию затрачивается минимум времени).
Обозначим
количество
груза, имеющегося
на каждой из
баз (запасы),
соответственно
,а
общее количество
имеющегося
в наличии груза–
:
;
заказы
каждого из
потребителей
(потребности)
обозначим
соответственно
,
а общее количество
потребностей
–
:
,
Тогда
при условии
![]()
мы
имеем закрытую
модель, а при
условии
![]()
– открытую модель транспортной задачи.
Очевидно,
в случае закрытой
модели весь
имеющийся в
наличии груз
развозится
полностью, и
все потребности
заказчиков
полностью
удовлетворены;
в случае же
открытой модели
либо все заказчики
удовлетворены
и при этом на
некоторых базах
остаются излишки
груза
,
либо весь груз
оказывается
израсходованным,
хотя потребности
полностью не
удовлетворены
.
Так же существуют одноэтапные модели задач, где перевозка осуществляется напрямую от, например, базы или завода изготовителя к потребителю, и двухэтапные, где между ними имеется “перевалочный пункт”, например – склад.
План перевозок с указанием запасов и потребностей удобно записывать в виде следующей таблицы, называемой таблицей перевозок:
|
Пункты Отправления |
Пункты назначения | Запасы | |||
|
|
|
… |
|
||
|
|
|
|
… |
|
|
|
|
|
|
… |
|
|
| … | … | … | … | … | … |
|
|
|
|
… |
|
|
| Потребности |
|
|
… |
|
или
|
Условие
или
означает, с
какой задачей
мы имеем дело,
с закрытой
моделью или
открытой моделью
транспортной
задачи. Переменное
означает количество
груза, перевозимого
с базы
потребителю
:
совокупность
этих величин
образует матрицу
(матрицу
перевозок).
Очевидно,
переменные
должны удовлетворять
условиям:
![]()
![]()
![]()

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

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

При
этом легко
заметить, что
под символами
такого суммирования
объединяются
только свободные
неизвестные
(здесь
,
).
В
рассматриваемой
нами системе
только два
уравнения, а
именно первое
горизонтальное
и первое вертикальное,
содержат более
одного неизвестного
из числа выбранных
нами для построения
базиса. Исключив
из первого
горизонтального
уравнения
базисные неизвестные
с помощью
вертикальных
уравнений, мы
получаем уравнение
![]()
или
короче
![]()
где
символ
означает сумму
всех свободных
неизвестных.
Аналогично,
исключив из
первого вертикального
уравнения
базисные неизвестные
с помощью
горизонтальных
уравнений, мы
получаем уравнение
![]()
![]()
Так
как для закрытой
модели транспортной
задачи
,
то полученные
нами уравнения
(2.2) и (2.2’) одинаковы
и, исключив из
одного из них
неизвестное
,
мы получим
уравнение-тождество
0=0,
которое из
системы вычеркивается.
Итак,
преобразование
системы (2.1) свелось
к замене двух
уравнений
(первого горизонтального
и первого
вертикального)
уравнением
(2.2). Остальные
уравнения
остаются неизменными.
Система приняла
вид
![]()

В
системе (2.3) выделен
указанный выше
базис: базисные
неизвестные
из первых т
уравнений
образуют первый
столбец матрицы
перевозок, а
базисные неизвестные
остальных
уравнений
образуют первую
строку матрицы
перевозок без
первого неизвестного
[она входит в
первое уравнение
системы (2.3)]. В
системе (2.3) имеется
уравнений,
выделенный
базис содержит
неизвестных,
а, следовательно,
и ранг системы
(2.1)
.
Для
решения транспортной
задачи необходимо
кроме запасов
и потребностей
знать также
и тарифы
,
т. е. стоимость
перевозки
единицы груза
с базы
потребителю
.
Совокупность
тарифов
также образует
матрицу, которую
можно объединить
с матрицей
перевозок и
данными о запасах
и потребностях
в одну таблицу:
|
Пункты Отправления |
Пункты назначения | Запасы | ||||||||
|
|
|
… |
|
|||||||
|
|
|
|
… |
|
|
|||||
|
|
|
|
||||||||
|
|
|
|
… |
|
|
|||||
|
|
|
|
||||||||
| … | … | … | … | … | … | |||||
|
|
|
Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.),
обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus.
Помогаем в публикации. Правки вносим бесплатно.
Похожие рефераты: | ||||||||