- •И.Л. Корнилова, н.Н. Парамонова, а.П. Табурчак транспортные задачи в экономико-математическом моделировании
- •Введение
- •3.2 Разрешимость транспортной задачи
- •3.3 Открытая и закрытая модели транспортной задачи
- •3.4 Задача о распределении специалистов, как пример альтернативной экономической интерпретации транспортной задачи
- •3.5 Опорный план транспортной задачи
- •3.5.1 Метод северо-западного угла построения опорного плана транспортной задачи
- •3.5.2 Метод наименьшей стоимости
- •3.5.3 Метод аппроксимации Фогеля
- •3.6 Метод потенциалов
- •3.7 Пример решения задачи методом потенциалов
- •3.8 Модификации транспортной задачи
- •3.9 Порядок выполнения работы
- •4 Оформление результатов работы
- •5 Контрольные вопросы
- •Лабораторная работа 2 решение транспортной задачи с помощью надстройки «поиск решения» в microsoft excel
- •3.2 Отчет по результатам для транспортной задачи
- •3.3 Отчет по устойчивости для транспортной задачи
- •3.3.1 Отчет по устойчивости для переменных
- •3.3.2 Отчет по устойчивости для ограничений
- •3.4 Отчет по пределам для транспортной задачи
- •3.5 Порядок выполнения работы
- •4 Оформление результатов работы
- •5 Контрольные вопросы
- •Литература
- •Приложение а (рекомендуемое) Задача о назначениях
- •Приложение б (обязательное) Введение в "Систему деловых задач"
- •Содержание
- •Транспортные задачи в экономико-математическом моделировании
- •190013, Санкт-Петербург, Московский пр., 26
Федеральное агентство по образованию
Государственное образовательное учреждение
высшего профессионального образования
Санкт-Петербургский государственный технологический институт
(Технический университет)
Кафедра финансов и статистики
Кафедра менеджмента и маркетинга
И.Л. Корнилова, н.Н. Парамонова, а.П. Табурчак транспортные задачи в экономико-математическом моделировании
Методические указания к лабораторным работам
Санкт-Петербург
2007
УДК 519.8
Корнилова И.Л. Транспортные задачи в экономико-математическом моделировании: Метод. указания/ И.Л. Корнилова, Н.Н. Парамонова, А.П. Табурчак - СПб.: СПбГТИ(ТУ), 2007. – 48 c.
Настоящие методические указания посвящены изложению теоретических основ построения транспортных моделей, а также способам их применения в экономике. Описаны разнообразные примеры экономических ситуаций, моделируемых с их помощью и методы их решения. Приведены примеры расчетов, иллюстрирующие теорию. При решении задач используются средства электронной таблицы Excel, входящей в стандартное программное обеспечение MicrosoftOffice, а также другие программы.
Методические указания предназначены для обучения студентов II–IV курсов специальности 080502 “Экономика и управление на предприятии” и соответствуют рабочей программе дисциплины «Экономико-математические методы». Также могут быть использованы для обучения студентов по другим дисциплинам, включающим изучение экономико-математических моделей.
Рис. 4, табл. 4, библиог. 15 назв.
Рецензент: Е.Ю. Безукладова, канд. экон. наук, доцент, заведующий кафедрой экономики и организации производства СПбГТИ(ТУ)
Утверждены на заседании учебно-методической комиссии факультета экономики и менеджмента 20.12.06.
Рекомендованы к изданию РИСо СПбГТИ(ТУ).
Введение
Настоящие методические указания посвящены изложению теоретических основ построения транспортных моделей, а также способам их применения в экономике. Описаны разнообразные примеры экономических ситуаций, моделируемых с их помощью и методы их решения. Приведены примеры расчетов, иллюстрирующие теорию. При решении задач используются средства электронной таблицы Excel, входящей в стандартное программное обеспечение MicrosoftOffice, а также другие программы.
ЛАБОРАТОРНАЯ РАБОТА 1 ПОСТАНОВКА ТРАНСПОРТНОЙ ЗАДАЧИ И ЕЕ РЕШЕНИЕ МЕТОДОМ ПОТЕНЦИАЛОВ
1 ЦЕЛЬ РАБОТЫ
Изучить постановку транспортной задачи, способы построения опорного плана этой задачи, основы алгоритма метода потенциалов, научиться решать этим методом транспортные задачи, в том числе с использованием программных средств.
2 ПРИБОРЫ И МАТЕРИАЛЫ
Для выполнения лабораторной работы необходим персональный компьютер, функционирующий под управлением операционной системы семейства Windows.. Программное обеспечение экономических расчетов – ППП «Quantitative Systems for Business», также можно использовать средства электронной таблицы.
3 ОПИСАНИЕ РАБОТЫ
3.1 Постановка транспортной задачи
Большое число разнообразных экономических ситуаций может быть смоделировано с помощью транспортной задачи.
Модель в общем виде
Требуется перевезти с наименьшими затратами однородную продукцию от n поставщиков к m потребителям. Заданы объемы запасов продукции у каждого из поставщиков ai, , и объемы потребностей у каждого из потребителей bj, .
Затраты на перевозку единицы продукции от i-го поставщика к j-му потребителю равны cij; , .
Составить план перевозок. |
Пример
Компания производит коммерческие холодильные установки на трех основных производствах (n = 3) – в Стокгольме, Триесте и Руане – соответственно по 120, 40 и 90 шт. (a1 = 120, a2 = 40, a3 = 90). Основными центрами сбыта являются Лейпциг и Лион (m = 2), которые нуждаются в поставках соответственно 150 и 90 установок (b1 = 150, b2 = 90). Перевозка одной установки в эти города из Стокгольма обходится соответственно в 25 и 14, из Триеста – в 18 и 8, и из Руана – в 12 и 6 ф.ст. (c11 = 25, c12 = 14, …, c32 = 6). Составить наиболее дешевый план перевозок. |
Введем переменные хij –
- количество продукции, перевозимой от i-го поставщика к j-му потребителю; , . Тогда cijхij - затраты на перевозку продукции от i-го поставщика к j-му потребителю. Просуммировав их по всем i и j, получим общие затраты, которые необходимо минимизировать: min От i-го поставщика к различным потребителям вывозится продукции. При этом нельзя увезти большее количество продукции, чем имеется у него в запасе, и это должно выполняться для всех n поставщиков ():
К j-му потребителю привозят продукции, и эта сумма должна быть не меньше его потребностей (для любого потребителя ):
По смыслу задачи . |
- число установок, перевозимых из i-го центра производства в j-й центр сбыта; , . Тогда в 25х11 ф.ст. обходятся перевозки из Стокгольма в Лейпциг, в 14х12 ф.ст. - из Стокгольма в Лион и т.д. Минимизируем все затраты на перевозку:
min (25x11 + 14x12 + 18x21 + 8x22 + 12x31 + 6x32)
В два центра сбыта из Стокгольма будет вывезено x11 + x12 установок. Эта сумма не может превысить 120, т.е. числа установок, производимых в Стокгольме: x11 + x12 120
Аналогичные условия должны выполняться для Триеста и Руана: x21 + x22 40 x31 + x32 90 Из трех центров производства в Лейпциг поставляют x11 + x21+ x31 установок. Так как Лейпцигу необходимо по крайней мере 150 установок, x11 + x21+ x31 150 Аналогично для Лиона x12 + x22+ x32 90 По смыслу задачи , так как количество установок не может быть отрицательным или дробным. |
Итак, модель транспортной задачи в общем виде строится следующим образом:
(1)
Построенная модель является задачей линейного программирования, включающей m+nограничений наm*nнеотрицательных переменных.
Для рассмотренного примера – задачи о холодильных установках – транспортная модель примет вид:
min (25x11+ 14x12+ 18x21+ 8x22+ 12x31+ 6x32)
x11 + x12 120
x21 + x22 40
x31 + x32 90
x11 + x21+ x31 150
x12 + x22+ x32 90
Построенная задача линейного программирования включает 5 = 3 + 2 ограничений на 6 = 3 * 2 неотрицательных переменных.
Отметим, что перевозка продукции - не единственная экономическая ситуация, которая может быть смоделирована с помощью такой задачи. Транспортные задачи имеют более широкую область применения и представляют собой отдельный класс задач линейного программирования, для которого разработаны специальные методы решения. Конечно, ее можно решить и симплекс-методом, но в связи с большой размерностью (особенно с большим числом переменных) это бывает невыгодно. В самом деле, в симплексной таблице будет храниться более чем m*n*(m+n) значений (даже если размерность задачи всего 5 х 5, то это 10 ограничений на 25 основных переменных).
Пример использования транспортной модели в экономической ситуации, не связанной с перевозками, будет рассмотрен далее.