Транспортная задача. Применение транспортных моделей

Министерство общего и профессионального образования Ростовской области

ГОУ СПО «Вешенский педагогический колледж им. М.А. Шолохова»

Курсовая работа

по дисциплине «Математические методы»

на тему: «Транспортная задача. Применение транспортных моделей»

Специальность: 230105 «Программное обеспечение вычислительной техники и автоматизированных систем»

   Выполнил студент 3 курса группы Б

   Павлов Павел

        Руководитель: Говоровская Т.А.

Ст-ца Вешенская

2011 г.

Введение

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

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

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

Цель транспортной деятельности считается достигнутой при выполнении шести условий:

нужный товар;

необходимого качества;

в необходимом количестве доставлен;

в нужное время;

в нужное место;

с минимальными затратами.

Объектом изучения являются материальные и соответствующие им финансовые, информационные потоки, сопровождающие производственно-коммерческую деятельность.

В данной курсовой работе будут рассмотрены понятие транспортной задачи, ее типы, различные методы решения. Решена задача по заданию 4.1 с помощью MS Excel и приложена компьютерная программа по решению задачи данного типа.

Транспортная задача

Линейные транспортные задачи составляют особый класс задач линейного программирования. Задача заключается в отыскании такого плана перевозок продукции с m складов в пункт назначения n который, потребовал бы минимальных затрат. Если потребитель j получает единицу продукции (по прямой дороге) со склада i, то возникают издержки Сij. Предполагается, что транспортные расходы пропорциональны перевозимому количеству продукции, т.е. перевозка k единиц продукции вызывает расходы k С i j.

Далее,

где ai есть количество продукции, находящееся на складе i , и bj - потребность потребителя j.

Замечание.

1. Если сумма запасов в пунктах отправления превышает сумму поданных заявок то количество продукции, равное остается на складах. В этом случае мы введем "фиктивного" потребителя n +1 с потребностью и положим транспортные расходы pi,n +1 равными 0 для всех i.

2. Если сумма поданных заявок превышает наличные запасы то потребность не может быть покрыта. Эту задачу можно свести к обычной транспортной задаче с правильным балансом, если ввести фиктивный пункт отправления m + 1 с запасом и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равным нулю.

Математическая модель

где xij количество продукции, поставляемое со склада i потребителю j, а С i j издержки (стоимость перевозок со склада i потребителю j).

Опорный план

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

Условия транспортной задачи заданы транспортной таблицей.

Таблица № 1

Будем заполнять таблицу перевозками постепенно начиная с левой верхней ячейки ("северо-западного угла" таблицы). Будем рассуждать при этом следующим образом. Пункт В1 подал заявку на 18 единиц груза. Удовлетворим эту заявку за счёт запаса 48, имеющегося в пункте А1, и запишем перевозку 18 в клетке (1,1). После этого заявка пункта В1 удовлетворена, а в пункте А1 осталось ещё 30 единиц груза. Удовлетворим за счёт них заявку пункта В2 (27 единиц), запишем 27 в клетке (1,2); оставшиеся 3 единицы пункта А1 назначим пункту В3. В составе заявки пункта В3 остались неудовлетворёнными 39 единиц. Из них 30 покроем за счёт пункта А2, чем его запас будет исчерпан, и ещё 9 возьмём из пункта А3. Из оставшихся 18 единиц пункта А3 12 выделим пункту В4; оставшиеся 6 единиц назначим пункту В5, что вместе со всеми 20 единицами пункта А4 покроет его заявку. На этом распределение запасов закончено; каждый пункт назначения получил груз, согласно своей заявки. Это выражается в том, что сумма перевозок в каждой строке равна соответствующему запасу, а в столбце - заявке.

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

Таблица № 2

Составленный нами план перевозок, не является оптимальным по стоимости, так как при его построении мы совсем не учитывали стоимость перевозок Сij.

Другой способ - способ минимальной стоимости по строке - основан на том, что мы распределяем продукцию от пункта Ai не в любой из пунктов Bj, а в тот, к которому стоимость перевозки минимальна. Если в этом пункте заявка полностью удовлетворена, то мы убираем его из расчетов и находим минимальную стоимость перевозки из оставшихся пунктов Bj. Во всем остальном этот метод схож с методом северо-западного угла. В результате, опорный план, составленный способом минимальной стоимости по строке выглядит, так как показано в таблице № 3. При этом методе может получиться, что стоимости перевозок Cij и Cik от пункта Ai к пунктам Bj

и Bk равны. В этом случае, с экономической точки зрения, выгоднее распределить продукцию в тот пункт, в котором заявка больше. Так, например, в строке 2: C21 = C24, но заявка b1 больше заявки b4, поэтому 4 единицы продукции мы распределим в клетку (2,1).

Таблица № 3