Каждый человек ежедневно, не всегда осознавая это, решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда ограничены. Жизнь была бы менее интересной, если бы это было не так. Не трудно выиграть сражение, имея армию в 10 раз большую, чем у противника. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий. Раньше план в таких случаях составлялся на глазок. В середине XX века был создан специальный математический аппарат, помогающий это делать по науке. Соответствующий раздел математики называется математическим программированием. Слово программирование» здесь и в аналогичных терминах (линейное программирование, динамическое программирование и т.п.) обязано отчасти историческому недоразумению, отчасти неточному переводу с английского. По-русски лучше было бы употребить слово планирование. С программированием для ЭВМ математическое программирование имеет лишь то общее, что большинство возникающих на практике задач математического программирования слишком громоздки для ручного счета, решить их можно только с помощью ЭВМ, предварительно составив программу. Временем рождения линейного программирования принято считать 1939 г., когда была напечатана брошюра Леонида Витальевича Канторовича Математические методы организации и планирования производства.
Под названием транспортная задача объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.
Целью транспортной задачи является обеспечение получения (доставки) продукции (товара) потребителю в нужное время и место при минимально возможных совокупных затратах трудовых, материальных, финансовых ресурсов.
Цель транспортной деятельности считается достигнутой при выполнении шести условий:
- Øнужный товар;
- Øнеобходимого качества;
- Øв необходимом количестве доставлен;
- Øв нужное время;
- Øв нужное место;
- Øс минимальными затратами.
Объектом изучения являются материальные и соответствующие им финансовые, информационные потоки, сопровождающие производственно-коммерческую деятельность.
План дипломной работы по туризму (примеры)
... И В МИРЕ Примерный план ВВЕДЕНИЕ ГЛАВА 1. ПОНЯТИЕ РЫНКА ТУРИЗМА И НОРМАТИВНО-ПРАВОВОЕ РЕГУЛИРОВАНИЕ В РОССИИ Общее понятие и классификация туристических предприятий Основные виды услуг туристических ... работы и Статьи. Примеры различных тем дипломных работ и примерные планы к дипломным проектам по различным экономическим и гуманитарным дисциплинам, а также примеры целей и задач, примеры объекта и ...
Глава I. Постановка транспортной задачи и методы нахождения первоначального опорного решения
1 Транспортная задача
Линейные транспортные задачи составляют особый класс задач линейного программирования. Задача заключается в отыскании такого плана перевозок продукции с m складов в пункт назначения n, который потребовал бы минимальных затрат. Если потребитель j получает единицу продукции (по прямой дороге) со склада i, то возникают издержки Сij. Предполагается, что транспортные расходы пропорциональны перевозимому количеству продукции, т.е. перевозка k единиц продукции вызывает расходы k Сij.
Далее,
где ai-есть количество продукции, находящееся на складе i, и bj — потребность потребителя j.
Замечание.
— Если сумма запасов в пунктах отправления превышает сумму поданных заявок то количество продукции, равное остается на складах. В этом случае мы введем «фиктивного» потребителя +1 с потребностью и положим транспортные расходы pi,n +1 равными 0 для всех i.
- Если сумма поданных заявок превышает наличные запасы
то потребность не может быть покрыта. Эту задачу можно свести к обычной транспортной задаче с правильным балансом, если ввести фиктивный пункт отправления m+1 с запасом
и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равным нулю.
2 Математическая модель транспортной задачи
где xij количество продукции, поставляемое со склада i потребителю j, а Сij издержки (стоимость перевозок со склада i потребителю j).
3 Опорный план
Решение транспортной задачи начинается с нахождения опорного плана. Для этого существуют различные способы. Например, способ северо-западного угла, способ минимальной стоимости по строке, способ минимальной стоимости по столбцу и способ минимальной стоимости таблицы. Рассмотрим простейший, так называемый способ северо-западного угла. Пояснить его проще всего будет на конкретном примере:
Условия транспортной задачи заданы транспортной таблицей.
Таблица № 1
ПН ПОВ1В2В3В4В5Запасы аiА110856948А26786530А387108727А47546820Заявки bj1827421226125
Будем заполнять таблицу перевозками, постепенно начиная с левой верхней ячейки («северо-западного угла» таблицы).
Будем рассуждать при этом следующим образом. Пункт В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 покроет его заявку. На этом распределение запасов закончено; каждый пункт назначения получил груз, согласно своей заявке. Это выражается в том, что сумма перевозок в каждой строке равна соответствующему запасу, а в столбце — заявке.
Чартерные перевозки
... и целевой чартер являются наиболее распространенными видами авиаперевозок на чартерном рынке. Блок-чартер. Этот вариант предполагает покупку заказчиком только части коммерческой емкости самолета (20-30 мест) на регулярном рейсе. ...
Таким образом, нами сразу же составлен план перевозок, удовлетворяющий балансовым условиям. Полученное решение является опорным решением транспортной задачи:
Таблица № 2
ПН ПОВ1В2В3В4В5Запасы аiА110 188 275 36948А2678 306530А38710 98 127 627А475468 2020Заявки bj1827421226125
Составленный нами план перевозок, не является оптимальным по стоимости, так как при его построении мы совсем не учитывали стоимость перевозок Сij.
Другой способ — способ минимальной стоимости по строке — основан на том, что мы распределяем продукцию от пункта Ai не в любой из пунктов Bj, а в тот, к которому стоимость перевозки минимальна. Если в этом пункте заявка полностью удовлетворена, то мы убираем его из расчетов и находим минимальную стоимость перевозки из оставшихся пунктов Bj. Во всем остальном этот метод схож с методом северо-западного угла. В результате, опорный план, составленный способом минимальной стоимости, по строке выглядит, так как показано в таблице № 3. При этом методе может получиться, что стоимости перевозок Cij и Cik от пункта Ai к пунктам Bj и Bk равны. В этом случае, с экономической точки зрения, выгоднее распределить продукцию в тот пункт, в котором заявка больше. Так, например, в строке 2: C21 = C24, но заявка b1 больше заявки b4, поэтому 4 единицы продукции мы распределим в клетку (2,1).
Таблица № 3
ПН ПОВ1В2В3В4В5Запасы аiА11085 426 6948А26 47865 2630А387 271087 027А47 14546 6820Заявки bj1827421226125
Способ минимальной стоимости по столбцу аналогичен предыдущему способу. Их отличие состоит в том, что во втором способе мы распределяем продукцию от пунктов Bi к пунктам Aj по минимальной стоимости Cji.
Опорный план, составленный способами минимальных стоимостей, обычно более близок к оптимальному решению. Так в нашем примере общие затраты на транспортировку по плану, составленному первым способом F0 = 1039, а по второму F0 = 723. Клетки таблицы, в которых стоят ненулевые перевозки, являются базисными. Их число должно равняться m+n-1. Необходимо отметить также, что встречаются такие ситуации, когда количество базисных клеток меньше чем m+n-1. В этом случае распределительная задача называется вырожденной. И следует в одной из свободных клеток поставить количество перевозок равное нулю. Так, например, в таблице № 3:+ n — 1 = 4 + 5 — 1 = 8,
а базисных клеток 7, поэтому нужно в одну из клеток строки 3
