Автор: Пользователь скрыл имя, 17 Апреля 2012 в 20:51, курсовая работа
Цели работы: изучить методы решения транспортной задачи и их реализацию при решении практической задачи.
Каждый человек ежедневно, не всегда осознавая это, решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда ограничены. Жизнь была бы менее интересной, если бы это было не так. Не трудно выиграть сражение, имея армию в 10 раз большую, чем у противника. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий. Раньше план в таких случаях составлялся “на глазок”. В середине XX века был создан специальный математический аппарат, помогающий это делать “по науке”. Соответствующий раздел математики называется математическим программированием. Слово “программирование" здесь и в аналогичных терминах (“линейное программирование, динамическое программирование” и т.п.) обязано отчасти историческому недоразумению, отчасти неточному переводу с английского.
Введение
Транспортная задача
Математическая модель
Постановка классической транспортной задачи
Способы составления первого допустимого плана перевозок
Способ северо-западного угла
Способ наименьшего элемента в матрице
Способ двойного предпочтения
Способ аппроксимации Фогеля
Решение транспортных задач, имеющих некоторые дополнительные условия
Задача с распределением резерва (спрос не равен предложению)
Запрещение корреспонденции
Обязательная (директивная) корреспонденция
Открытая модель распределительного метода
Признаки наличия альтернативных решений в различных способах распределительного метода
Закрепление потребителей за поставщиками неоднородного взаимозаменяемого продукта
Усложнённая задача перевозки разнородной продукции
Транспортная задача по критерию времени
Заключение
Использованная литература
Содержание
Введение
Заключение
Использованная литература
Введение
Цели работы: изучить методы решения транспортной задачи и их реализацию при решении практической задачи.
Задания:
Каждый
человек ежедневно, не всегда осознавая
это, решает проблему: как получить
наибольший эффект, обладая ограниченными
средствами. Наши средства и ресурсы
всегда ограничены. Жизнь была бы менее
интересной, если бы это было не так.
Не трудно выиграть сражение, имея армию
в 10 раз большую, чем у противника.
Чтобы достичь наибольшего
Под
названием “транспортная
Целью транспортной задачи является обеспечение получения (доставки) продукции (товара) потребителю в нужное время и место при минимально возможных совокупных затратах трудовых, материальных, финансовых ресурсов.
Цель транспортной деятельности считается достигнутой при выполнении шести условий:
Линейные
транспортные задачи составляют особый
класс задач линейного
Далее,
где ai есть количество продукции, находящееся на складе i , и bj - потребность потребителя j.
Замечание.
1. Если сумма запасов в пунктах отправления превышает сумму поданных заявок то количество продукции, равное остается на складах. В этом случае мы введем "фиктивного" потребителя n+1 с потребностью и положим транспортные расходы pi,n +1 равными 0 для всех i.
2. Если сумма поданных заявок превышает наличные запасы то потребность не может быть покрыта. Эту задачу можно свести к обычной транспортной задаче с правильным балансом, если ввести фиктивный пункт отправления m + 1 с запасом и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равным нулю.
где xij количество продукции, поставляемое со склада i потребителю j, а С i j издержки (стоимость перевозок со склада i потребителю j).
Распределительный
метод широко применяется главным
образом при решении различных
транспортных задач (оптимальное закрепление
потребителей груза за поставщиками,
маршрутизация перевозок
Классическая транспортная задача заключается в нахождении оптимальных грузопотоков, т.е. в оптимальном закреплении поставщиков однородного груза за потребителями. В математической форме условия транспортной задачи выглядят следующим образом:
Потребителям В1, В2, ..., Вj, ..., Вn требуется однородный продукт (груз) в количествах соответственно b1, b2, ..., bj ,…, bn тонн, который производится (или хранится) у поставщиков А1, А2, ..., Аi, ....Аm в количествах а1, а2, ...,аi, ..., аm тонн. Так как все поставщики производят одну и ту же продукцию, каждый из них может удовлетворять запросы любого потребителя. Расстояния между отправителями и получателями груза известны и составляют 1ц километров. Требуется составить такой план перевозок грузов, который обеспечит удовлетворение запросов всех потребителей при минимальной транспортной работе (минимальной сумме тонно-километров). Очевидно, что для решения рассматриваемой задачи необходимо равенство общей потребности получателей наличию груза у отправителей.
Условия задачи удобно записывать в виде табл. 1, называемой матрицей условий.
Таблица 1
Пункт отправления |
Пункт назначения |
Наличие груза, т | |||||
В1 |
В2 |
… |
Вj |
… |
Вn | ||
А1 |
111 |
112 |
… |
11j |
… |
11n |
а1 |
А2 |
111 |
122 |
… |
12j |
… |
12n |
а2 |
… |
…. |
… |
… |
… |
… |
… |
… |
Аi |
1j1 |
1i2 |
… |
1ij |
… |
1in |
аi |
… |
… |
… |
… |
… |
… |
… |
… |
Аm |
1m |
1m2 |
… |
1mj |
… |
1mn |
аm |
Потребность в грузе, т |
b1 |
b2 |
… |
bj |
… |
bn |
bj = аi |