Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Решение транспортной задачи с помощью метода потенциалов.Стр 1 из 2Следующая ⇒
Министерство образования и науки Российской Федерации (МИНОБРНАУКИ РОССИИ) Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ УПРАВЛЕНИЯ» Институт информационных систем управления Кафедра математических методов в управлении
по дисциплине: «Методы оптимальных решений»
ДОМАШНЯЯ РАБОТА №2 Вариант 20
на тему: «Транспортная задача»
Москва 2014 год
Задача 2. Транспортная задача Решение транспортной задачи с помощью метода потенциалов. Составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства и общие транспортные расходы по доставке продуктов были бы минимальными. Таблица 1. Исходные данные
В правом столбце записаны компоненты вектора a. Каждая i – я компонента его равна максимальному количеству единиц продукта (максимальному предложению), которое может отправить i -й поставщик. В верхней строке находятся компоненты вектора b. Каждая j – я компонента его равна минимальному количеству единиц продукта (максимальному спросу), которое должен получить j -й потребитель. В остальных местах таблицы 1 находятся элементы матрицы С удельных затрат на транспортировку продукта размера .
В матричном виде:
Общий объем производства больше, чем требуется всем потребителям , т.е. имеем открытую модель транспортной задачи. Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом потребления 116 -104 = 12 единиц, причем тарифы на перевозку в этот пункт условимся считать равными нулю, помня, что переменные, добавляемые к левым частям неравенств для превращения их в уравнения, входят в функцию цели с нулевыми коэффициентами.
Первое базисное допустимое решение, построенное по правилу «северо-западного угла», которое состоит в том, чтобы на каждом этапе мы максимально загружали «северо-западную клеточку».
Таблица 2. Первое базисное допустимое решение
Обозначим через потенциалы поставщиков и потребителей соответственно. Полагаем, что а остальные потенциалы находим из следующих условий для базисных неизвестных: Имеем:
Затем по формуле вычисляем оценки всех свободных клеток: Находим наибольшую положительную оценку: Для найденной свободной клетки (2, 5) строим цикл пересчета – замкнутую ломаную линию. Это будет цикл с вершинами в клетках (2, 5), (2, 3), (3, 3), (3, 5). Ниже, на схеме выделены только вершинные клетки цикла пересчета.
Таблица 3. Второе базисное допустимое решение
Имеем: Затем по формуле вычисляем оценки всех свободных клеток:
Находим наибольшую положительную оценку:
Для найденной свободной клетки (1, 3) строим цикл пересчета. Это будет цикл с вершинами в клетках (1, 3), (1, 2), (2, 2), (2, 3).
Таблица 4. Третье базисное допустимое решение
Следующим шагом является нахождение потенциалов:
Оценки для свободных клеток:
Наибольшая положительная оценка: Для найденной свободной клетки (2, 1) строим цикл пересчета. Это будет цикл с вершинами в клетках (2, 1), (2, 3), (1, 3), (1, 1).
Таблица 5. Четвертое базисное допустимое решение
Находим потенциалы:
Далее находим оценки свободных клеток. Наибольшая положительная оценка: Для найденной свободной клетки (1, 2) строим цикл пересчета. Это будет цикл с вершинами в клетках (1, 2), (1, 1), (2, 1), (2, 2).
Таблица 6. Пятое базисное допустимое решение
Имеем:
Оценки свободных клеток: Опорный план является оптимальным, так как все оценки свободных клеток
Итак, оптимальное базисное допустимое решение
2. Решение задачи с помощью инструмента «Поиск решения» программного продукта Microsoft Excel.
|