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

СОДЕРЖАНИЕ
ВВЕДЕНИЕ
АЛГОРИТМЫ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ
Формулировка транспортной задачи
Математическая модель транспортной задачи
Необходимое и достаточное условия разрешимости транспортной задачи
Свойство системы ограничений транспортной задачи
Опорное решение транспортной задачи
Методы построения начального опорного решения.
Метод северо-западного угла
Метод минимальной стоимости
Переход от одного опорного решения к другому
Означенный цикл
Распределительный метод
Метод потенциалов
Особенности решения транспортных задач с неправильным балансом
Алгоритм решения транспортной задачи методом потенциалов
Транспортная задача с ограничениями на пропускную способность
Транспортная задача по критерию времени
Применение транспортной задачи для решения экономических задач
Задача о размещении производства с учетом транспортных затрат
Задача о назначениях, или проблема выбора
ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ МАТЕМАТИЧЕСКОЙ ТЕОРИИ
Описание турфирмы «Мир путешествий»
Описание диалога «Поиск решений»
Приложение процедур Excel к деятельности турфирмы «Мир путешествий»
Ввод данных
Заполнение окна процедуры «Поиск решения»
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ

Запишем целевую функцию задачи. Обозначим через Т(Х) наибольшее значение элементов матрицы Т=(), i=1,2,,…,m, j=1,2,…,n, соответствующих клеткам таблицы, занятым опорным решением: Т(Х)=. Таким образом, за время Т(Х) план перевозок будет выполнен полностью. Математическая модель имеет вид
Т(Х)= (26)
, i=1,2,…,m , (27)

, j=1, 2, … , n, (28)
, i=1,2,,…,m+1, j=1,2,…,n. (29)
Задача решается в следующем порядке. Находится начальное опорное решение Х1. определяется значение целевой функции Т(Х1)==. Все свободные клетки, которым соответствует значения >T(X1), исключаются из рассмотрения (перечеркиваются). Занимать эти клетки нецелесообразно, так как повысится значение целевой функции. Чтобы понизить ее значение, необходимо освободить клетку (l1, k1), в которой достигает максимума. Для этого строят так называемые разгрузочные циклы, которые могут включать в свой состав несколько свободных клеток. В каждом разгрузочном цикле, начиная с разгружаемой клетки (l1, k1), расставляются поочередно знаки «-» и «+» и осуществляется сдвиг на величину =. Если удается эту клетку разгрузить, то она исключается из рассмотрения (зачеркивается). Получается новое опорное решение Х2, на котором значение целевой функции меньше, чем на Х1. далее снова пытаются разгрузить клетку, соответствующую Т(Х2)= =. Процесс продолжается до тех пор, пока возможность разгрузить соответствующую клетку не исчезнет.
Применение транспортной задачи для решения экономических задач

Задача о размещении производства с учетом транспортных затрат
Имеется (проектируется) m пунктов производства с объемами производства и n пунктов потребления с объемами потребления . Затраты на производство единицы продукции в каждом i-м пункте производства известны и равны , i=1,2,…,m. Стоимости перевозки единицы груза от каждого i–го производителя каждому j–му потребителю известны и равны , i=1,2,,…,m, j=1,2,…,n. Суммарные объемы производства превосходят суммарные объемы потребления. Требуется составить план сокращения (размещения) производства, обеспечивающий минимальные производственно-транспортные затраты ([7]. Стр 152).
Задача решается как транспортная задача, матрица стоимостей которой составляется как сумма матриц:
С=()=(+), i=1,2,,…,m, j=1,2,…,n.
Вводится фиктивный потребитель. Затем задача решается обычным способом. Далее сокращается производство в пунктах, продукция которых в оптимальном плане перевозок поставляется фиктивному потребителю.
Задача о назначениях, или проблема выбора
Имеется m групп людей (станков) численностью , которые должны выполнять n видов работ (операций) объемом . Известна производительность каждой i–й группы людей (станков) при выполнении каждого j–го вида работ (операций) , i=1,2,,…,m, j=1,2,…,n. . Требуется так распределить людей (станки) для выполнения работ (операций), чтобы суммарный объем производства работ (операций) был максимальным.
Составим математическую модель данной задачи по аналогии с транспортной задачей. Обозначим - число людей (станков) i–й группы, занятых j–го вида работ (операций). Запишем математическую модель
, (30)
, i=1,2,…,m , (31)

, j=1, 2, … , n, (32)
, i=1,2,,…,m, j=1,2,…,n. (33)
Для использования алгоритмов, разработанных для транспортной задачи, можно перейти от нахождения максимума к нахождению минимума. Для этого нужно умножить коэффициенты целевой функции на (-1), тогда целевая функция будет иметь вид
-.
Можно также изменить критерий оптимальности. Например, вместо (i,j) использовать новый критерий оптимальности (i,j).
Практическое применение математической теории
Описание турфирмы «Мир путешествий»
Внедрим вышеописанные математические методы в деятельность туристической фирмы «Мир путешествий». Для начала, дадим координаты и реквизиты фирмы:
ЗАО «Группа Туристических Агенств Мир Путешествий»
Адрес: 107497, Россия, г.Москва, ул.Иркутская 11/17, корпус 1-3, офисный центр "Щелковский", офис 223
Телефоны: (495) 462-39-59, 502-13-44
Факс: (495) 462-39-59
Лицензия агентства - ТД №0027418
ИНН 7718508851
КПП 771801001
Р/с 40702810838290106844, Стромынский ОСБ № 5281 СБ РФ
К/с 30101810400000000225
БИК 044525225
http://www.mirput.ru/
Фирма, в частности, является совладельцем гостиниц Речной, Лунный, Победа, Интурист в Сочи, куда и организует большую часть туров. Важная транспортная проблема фирмы – развозка туристов от железнодорожного вокзала до гостиниц. На данный момент в турфирме нет логистического отдела и указанные проблемы решаются только основываясь на опыте нескольких водителей автобусов, при этом не применяется никакая математическая теория. Наша цель – выработать доступный алгоритм оптимизации транспортных расходов и разработать наиболее удобный, оперативный и быстрый метод решения. Заметим, что в разгар туристического сезона каждый день приходится совершать несколько развозок туристов от вокзала до отелей, поэтому быстрота принятия транспортных решений очень важна. Нет времени каждый раз решать вручную задачи.
Перейдем теперь к конкретике. Турфирма «Мир путешествий» обслуживающая туристов прибывающих на отдых, должна разместить их в 4 отелях: “Речной ”, “Лунный”, “Победа” и “Интурист”, в которых забронировано соответственно 5, 15, 15 и 10 мест. Пятнадцать туристов прибывают по железной дороге, двадцать пять прилетают очередным рейсом в аэропорт, а пять человек прибудут на теплоходе на морской вокзал. Транспортные расходы при перевозке из пунктов прибытия в отели приведены в таблице 2.
Таблица 2
Исходный пункт, i Пункт назначения (отели), j Речной Лунный Победа Интурист 1 2 3 4 Железнодо-рожный вокзал
1
10
0
20
11 Аэропорт 2 12 7 9 20 Морской вокзал 3 0 14 16 18
В условиях жесткой конкуренции фирма должна минимизировать свои расходы, значительную часть которых составляет именно транспортные расходы. Требуется определить такой план перевозки туристов из пункта прибытия в отели при котором суммарные транспортные расходы будут минимальны и все туристы будут размещены в отелях.
Конечно, можно для этой развозки применить описанный выше математический аппарат и получить оптимальное решение. Но, заметим, что очень часто о количестве туристов сотрудники фирмы узнают незадолго до их приезда в Сочи, или вообще непосредственно во время приезда поезда. Поэтому, зная, что решение транспортных задач трудоемко и долговременно, надо искать иные способы организации развозки. Наша цель – оперативность решения транспортных вопросов, обеспечивающих при этом и снижение издержек. Решение этой проблемы заключается в алгоритмизации математических алгоритмов или использование готовых программных средств. Наиболее постой, дешевый и удобный выход в использовании табличного редактора Excel. Отвлечемся от нашей турфирмы и обратимся к Excel.
Описание диалога «Поиск решений»
Инструмент Поиск решения может быть использован для решения задач, которые включают много изменяемых ячеек, и помогает найти комбинации переменных, которые максимизируют или минимизируют значение в целевой ячейке. Он также позволяет задать одно или несколько ограничений - условий, которые должны выполняться при поиске решения. Поиск решения является надстройкой.
Поля ввода и кнопки в этом окне выполняют следующие функции:
Установить целевую ячейку служит для указания целевой ячейки, значение которой необходимо максимизировать, минимизировать или установить равным заданному числу. Эта ячейка должна содержать формулу.
Равной служит для выбора варианта оптимизации значения целевой ячейки (максимизация, минимизация или подбор заданного числа). Чтобы установить число, введите его в поле.
Изменяя ячейки служит для указания ячеек, значения которых изменяются в процессе поиска решения до тех пор, пока не будут выполнены наложенные ограничения и условие оптимизации значения ячейки, указанной в поле Установить целевую ячейку. Используется для автоматического поиска ячеек, влияющих на формулу, ссылка на которую дана в поле Установить целевую ячейку. Результат поиска отображается в поле Изменяя ячейки.
Ограничения служит для отображения списка граничных условий поставленной задачи.
Добавить служит для отображения диалогового окна Добавить ограничение.
Ссылка на ячейку служит для указания ячейки или диапазона, на значения которых необходимо наложить ограничение.
Ограничение служит для задания условия, которое накладывается на значения ячейки или диапазона, указанного в поле Ссылка на ячейку. Выберите необходимый условный оператор и введите ограничение число, формулу, ссылку на ячейку или диапазон в поле справа от раскрывающегося списка.
Добавить. Нажатие на эту кнопку позволяет, не возвращаясь в окно диалога Параметры поиска решения, наложить новое условие на поиск решения задачи.
Изменить служит для отображения диалогового окна Изменить ограничение. Содержание данного окна в точности повторяет содержание окна Добавить ограничение.
Удалить служит для снятия указанного ограничения.
Выполнить служит для запуска поиска решения поставленной задачи.
Закрыть служит для выхода из окна диалога без запуска поиска решения поставленной задачи. При этом сохраняются установки сделанные в окнах диалога, появлявшихся после нажатий на кнопки Параметры, Добавить, Изменить или Удалить.
Параметры служит для отображения диалогового окна Параметры поиска решения, в котором можно загрузить или сохранить оптимизируемую модель и указать предусмотренные варианты поиска решения.
Восстановить служит для очистки полей окна диалога и восстановления значений параметров поиска решения, используемых по умолчанию.
Решение транспортных задач большой размерности весьма трудоемко. Хотя Excel и не является профессиональной математической программой, она успешно используется. Хотя, она гарантирует нахождение наименьшей стоимости перевозки, решение может не удовлетворять условиям метода потенциалов. Дело в том, что, как ранее было сказано, оптимальных решений может быть несколько. Они могут давать одну и ту же стоимость перевозки, но одни удовлетворяют достаточным условиям, а другие – нет. Но на практике достаточные условия не столь важны – главное стоимость перевозки. Вернемся теперь к нашей турфирме.
Приложение процедур Excel к деятельности турфирмы «Мир путешествий»
Используем диалоговое окно Excel для оптимизации деятельности турфирмы. Для начала введем данные, потом получим решение
Ввод данных
Вводим данные таблицы 1 и 2 в ячейки EXCEL (рис.3).
В ячейках B3 : E5 введены стоимости перевозок (табл. 2).
В ячейках F3 : F5 находится число прибывающих туристов. А в ячейках B6 : E6 находится число мест в отелях. Ячейки B8 : E10 – рабочие (изменяемые) ячейки, в которых будут вычисляться значения переменных задачи Xij.
В ячейках F8 : F10 нужно записать формулы для вычисления левых частей ограничений (3)(5):
в F8 должна быть сумма ячеек B8 : E8;
в F9 должна быть сумма ячеек B9 : E9;
в F10 должна быть сумма ячеек B10 : E10.
Формулы для вычисления левых частей ограничений (6)(9) введем в ячейки B11 : E11:
в B11 должна быть сумма ячеек B8 : B10;
в C11 должна быть сумма ячеек C8 : C10;
в D11 должна быть сумма ячеек D8 : D10;
в E11 должна быть сумма ячеек E8 : E10;
Целевую функцию поместим в ячейку G3:
G3: СУММПРОИЗВ (B3 : E5; B8 : E10).
Таблица исходных данных имеет вид:
Рис.3
Заполнение окна процедуры «Поиск решения»
целевая функция : G3;
значение целевой функции : min;
изменяемые ячейки : B8 : E10;
ограничения задачи :
F8 : F10 = F3 : F5 (формулы (3)(5))
B11 : E11 = B6 : E6 (формулы (6)(9))
B8 : E10 0 (1) и B8 : E10 – целые числа (2)
В окне «Параметры» установить «Линейная модель», что соответствует решению задачи симплекс-методом. Результаты заполнения окна показаны на рисунке 4:
Рис.4
Выполнив процедуру «Поиск решения» получим следующие результаты:
Рис.5
Таким образом, с железнодорожного вокзала (исходный пункт 1) следует 10 туристов отвезти в отель «Интурист» (пункт 4) и 5 туристов в отель «Лунный» (пункт назначения 2); из аэропорта (исходный пункт 2) 10 туристов отвезти в отель «Лунный» (пункт назначения 2) и 15 туристов в отель «Победа» (пункт назначения 3); туристов прибывающих на морской вокзал (исходный пункт 3) нужно отправить в отель «Речной» (пункт назначения 1). Все эти результаты видны в конечной таблице (рис.5) При этом суммарная стоимость транспортных расходов составит 315 рублей (ячейка G3).
Таким образом, мы показали наиболее дешевый способ доставки туристов.
Заключение
В условиях перехода на рыночные основы экономики структура производственно-хозяйственной деятельности промышленности и транспорта страны коренным образом изменилась. Планово-распределительная экономика и командно-административная система управления активно замещаются практикой прямых договорных отношений, ориентированных на потребности рынка. В результате процессов разгосударствления, приватизации и демонополизации транспортного комплекса, либерализации тарифной политики ускоренно формируется рынок транспортных услуг, обеспечивающий производственные и межрегиональные связи, сферу обращения товаров и услуг. Резко возросло количество судоходных компаний, агентских, брокерских, транспортно-экспедиторских предприятий. Если ранее перевозка грузов и пассажиров полностью обеспечивалась 17-ю судоходными компаниями, бывшими морскими пароходствами СССР, а перевалка грузов производилась в нескольких десятках морских портов, то в настоящее время существует огромное количество коммерческих компаний занимающихся непосредственно деятельностью морского транспорта. С точки зрения рыночной экономики, все эти процессы носят, несомненно, позитивный характер, однако протекают они на фоне существенного сокращения промышленного производства, ухудшения экономического состояния товаропроизводителей и потребителей продукции, разрыва сложившихся транспортно - экономических связей, неустойчивой тарифной и налоговой политики. Фактически транспортный комплекс, который представляет собой совокупность, состоящую из иерархически зависимых, сложных подсистем, с целенаправленной деятельностью в сфере удовлетворения потребностей общества в транспортных услугах, долгие годы развивался под воздействием движущих сил, присущих плановой экономике. При этом существовали адекватные этому способу хозяйствования критерии и методы анализа деятельности этих систем. С началом перестройки существующий комплекс сил прекратил свое существование и система начала переходить под влияние движущих сил, характерных для рыночной экономики, которые до конца еще не сложились. Рыночные механизмы активно внедряются в деятельность транспортных предприятий. В связи с этим очевидным становится необходимость применения математических методов минимизации транспортных расходов.
Данная работа содержит как математическую теорию, необходимую для решения задач, так и описание программных средств решения задач. Но стоит заметить, что не следует применять компьютерные средства не зная математической теории – это путь к ошибочным решениям. Ни один компьютер не заменит человека!
В проекте разработан файл Excel, который может с легкостью быть использован турфирмой. Достаточно всего лишь ввести необходимое количество туристов и иногда менять стоимость доставки. При этом уже нет необходимости в трудоемком расчете математических алгоритмов. Любой сотрудник фирмы непосредственно на месте может с легкостью теперь организовывать доставку туристов до места назначения.

Список литературы
Акулич И.Л. Математическое программирование в примерах и задачах. -М.: Высшая школа, 1986.
Алексеев В.М., Галеев Э.М., Тихомиров В.М. Сборник задач по оптимизации. - М.: Наука, 1984.
Банди Б. Методы оптимизации. Вводный курс. - М.: Радио и связь, 1988.
Боборыкин В.А. Математические методы решения транспортных задач. Л.: СЗПИ, 1986
Васильев Ф.П. Численные методы решения экстремальных задач. - М.:Наука, 1980.
Геронимус Б.А. Экономико-математические методы в планировании на автомобильном транспорте. М.: Транспорт, 1982
Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. - М.: Мир, 1985.
Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. - М.: Наука, 1982.
Заславский Ю.Л. Сборник задач по линейному программированию. М., «Наука», 1969.
Капустин В. Ф. Практические занятия по курсу математического программирования. Л., Изд-во Ленингр. Ун - та, 1976.
Карманов В.Г. Математическое программирование. - М.: Наука, 1975.
Кузнецов Ю.Н., Кузубов В.И., Волощснко А. Б. Математическое программирование. М.: Высшая школа, 1980
Колесников A. Excel 7.0 для Windows 95. Русифицированная версия. Киев: BHV, 1996.
Курицкий Б. Поиск оптимальных решений средствами Excel 7.0 СПб.: «BHV -Санк-Петербург, 1997.
Лесин В.В., Лисовец Ю.П. Основы методов оптимизации. - М.: Изд-во МАИ, 1995.
Летова Т.А., Пантелеев А.В. Экстремум функций в примерах и задачах. M.: Изд-во МАИ, 1998.
Моисеев Н.Н., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. Наука. М. 1978. Стр. 325
Пробитюк A. Excel 7.0 в бюро. Киев: BHV, 1996
Пшеничный Б.И., Данилин Ю.М. Численные методы в экстремальных задачах. - М.: Наука, 1975.
Федоров В.В. Численные методы максимина. - М.: Наука, 1979.
Химмельбау Д. Прикладное нелинейное программирование. М., «Мир», 1975.
30