Автор работы: Пользователь скрыл имя, 30 Декабря 2012 в 22:16, контрольная работа
Цель заданной работы - освоить математическую постановку транспортной задачи линейного программирования и метод решения задач средствами Ms Excel. В работе будут рассмотрены основные понятия транспортных задач, методы определения первоначального опорного плана, распределительный и венгерский методы решения, а также с помощью средств Ms Excel будет подробно рассмотрено в качестве примера решение конкретной транспортной задачи.
Введение. 3
Постановка задачи. 4
Основные свойство транспортной задачи. 6
Двойственная задача. 8
Теоремы двойственности. 9
Построение опорного плана транспортной задачи. 10
Метод северо-западного угла. 11
Метод потенциалов. 12
Вычислительная схема метода потенциалов 13
Заключение. 15
Использованная литература. 16
Ценой цикла называется увеличение стоимости перевозок при перемещении единицы груза по этому циклу. Очевидно, цена цикла равна алгебраической сумме стоимостей, стоящих в вершинах цикла, при этом стоимости в положительных вершинах берутся со знаком " +", а стоимости в отрицательных вершинах берутся со знаком " - ".
Идея метода потенциалов состоит в следующем. Для любой свободной клетки транспортной таблицы всегда существует единственный цикл, положительная вершина которого лежит в этой свободной клетке, а все остальные - в базисных. Если цена такого цикла отрицательна, то план можно улучшить перемещением перевозок по данному циклу. Количество единиц груза, которое можно переместить, определяется минимальным значением перевозок, стоящих в отрицательных вершинах цикла (если переместить большее число единиц груза, возникнут отрицательные перевозки). Если циклов с отрицательной ценой нет, то это означает, что дальнейшее улучшение плана невозможно, т.е. оптимальный план найден.
Для нахождения циклов с отрицательной ценой вводится система
платежей
и определяются величины
называемые "псевдостоимостями" перевозок единицы груза из пункта i
в пункт j. При этом цена цикла пересчета для каждой свободной клетки
равна
если платежи
Шаг 1. Строим опорный план (методом северо-западного угла) с n+m-1 базисными клетками.
Шаг 2. Определяем платежи
для всех базисных клеток. Один из платежей (например a1 ) полагаем равньм нулю.
Шаг 3. Считаем псевдостоимости
для всех свободных клеток.
Если
для всех клеток, то план оптимален.
Вычисляем значение целевой функции
L на этом плане и исследования прекращаем.
Шаг 4. Если есть свободная клетка,
для которой
то улучшаем план, перебрасывая перевозки по циклу этой свободной клетки.
Шаг 5. Возвращаемся к шагу 2 для пересчета платежей нового опорного плана.
Пример
Решить методом потенциалов
транспортную задачу
Опорный план этой задачи найден
методом северо-западного угла.
Приписываем к таблице
добавочную строку для платежей
и добавляем столбец для
платежей
Псевдостоимости записываем в левом углу клетки, а стоимости - в правом углу.
Из условий
в базисных клетках получаем
систему уравнений
Полагая
, находим последовательно платежи
и псевдостоимости для свободных
клеток. Получаем таблицу
Стоимость перевозок по плану этой таблицы
Так как клетка (1,3) имеет
отрицательную цену
то план не является оптимальным. Строим для клетки (1,3) цикл. Цена
цикла
По циклу переносим 20 единиц груза (больше нельзя, чтобы перевозки в клетке (1, 2) не стали отрицательными).При
этом стоимость плана
уменьшается на
Для нового плана вычисляем
новые значения платежей и псевдостоимостей:
Стоимость перевозок по плану
этой таблицы
Полученная таблица имеет
клетку (2,1 ) с отрицательной ценой
По циклу этой клетки переносим 10 единиц груза,
при этом стоимость плана
уменьшается на
единиц, и получаем новый
опорный план с новой системой
платежей и псевдостоимостей:
Стоимость перевозок по плану
этой таблицы
Так как в последней таблице все псевдостоимости не превосходят
соответствующих стоимостей,
то полученный опорный план
является оптимальным. Стоимость
перевозок при этом
Описанная в курсовой работе
транспортная задача и методы ее решения
- только отдельный пример огромного
множества задач линейного
1. Красс М.С., Чупрынов Б.П. ”Основы математики и ее приложения в экономическом образовании”, Издательство “Дело”, Москва 2001г.
2. Акулич И.Л. Математическое программирование в примерах и задачах: учебное пособие для ВУЗов. - М.: Высшая школа, 1986, 319с.
3. Павлова Т.Н., Ракова О.А. Линейное программирование. Учебное пособие. - Димитровград, 2002.
4. Павлова Т.Н., Ракова О.А. Решение задач линейного программирования средствами Excel. Учебное пособие. - Димитровград, 2002.
5. Ермаков В.И. Сборник задач по высшей математике для экономистов. - М.: Издательство Инфра, 2001, 574с.
6. Кузнецов А.В., Сакович В.А., Холод Н.И. ”Высшая математика. Математическое программирование ”, Минск, Вышейшая школа, 2001г.
7. В.И. Ермаков “Общий курс высшей математики для экономистов”, Москва, Инфра-М, 2000г.
8. Гончаров Е.Н., Ерзин А.И., Залюбовский В.В. Исследование операций. Примеры и задачи: Учеб. Пособие / Новосиб. Гос. ун-т. Новосибирск, 2005. 78с.
9. Береснев В.Л., Дементьев В.Т. Исследование операций. Введение. Учебное пособие. НГУ, 1979, I - 92.
10. Авдей А.Н. Анализ данных в Excel: под ред. Проф. А.А. Прихожего. - Мн.: БГПА, 2000