![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Транспортная задача. Задание 4.Решить транспортную задачу.
Задание 4. Решить транспортную задачу. Транспортная задача - это задача о перевозке некоторого груза от m поставщиков к n потребителям. Обычно условия транспортной задачи задаются в таблице.
В этой таблице:
потребителю (тариф перевозки). Если суммарный запас равен суммарным потребностям, т.е. Рассмотрим решение закрытой модели транспортной задачи. 1. Как и при решении ЗЛП симплексным методом, определение оптимального плана транспортной задачи начинают с нахождения исходного опорного плана. Этот план наиболее рационально находить методом минимального элемента (существуют и другие методы его нахождения). Для этого в таблице тарифов выбираем минимальный (например 2. Для проверки найденного плана на оптимальность используется метод потенциалов. 2.1 Для «заняты х» клеток составляем систему уравнений 2.2 Для «свободных» клеток находим числа Если все Перераспределение поставок в таблице условий транспортной задачи производится по циклу. Цикл – это цепь, многоугольник, все вершины которого находятся в занятых клетках, углы прямые, число вершин четное. После того как цикл пересчета построен, в вершинах цикла, начиная со свободной клетки Этот новый план распределения поставок проверяем на оптимальность (переходим к пункту 2). Процесс продолжаем до тех пор, пока не получим, что все Пример. Имеются четыре пункта поставки однородного груза
Решение. По условию задачи составим таблицу:
1. Найдем суммарный запас и суммарные потребности: Так как суммарный запас равен суммарным потребностям, т.е. 2. Находим исходный опорный план методом минимального элемента. Число занятых клеток должно равняться:
Среди всех тарифов перевозки 3. Проверяем найденный план на оптимальность методом потенциалов: 3.1 Для «занятых» клеток составляем уравнения 3.2 Для «свободных» клеток находим Строим в таблице цикл пересчета относительно клетки (3, 1). Он пойдет следующим образом (3, 1) Расставляем знаки «+» и «–» в вершинах цикла, начиная с клетки (3, 1). В «–» клетках ищем минимальный груз
4. Проверяем найденный план на оптимальность методом потенциалов. 4.1 Для «занятых» клеток: 4.2 Для «свободных» клеток: Строим в таблице цикл пересчета относительно клетки (2, 5). Он пойдет следующим образом (2, 5) Расставляем знаки «+» и «–» в вершинах цикла, начиная с клетки (2, 5). В «–» клетках ищем минимальный груз
5. Проверяем найденный план на оптимальность. 5.1 Для «занятых» клеток:
5.2 Для «свободных» клеток:
Строим в таблице цикл пересчета относительно клетки (1, 2). Он пойдет следующим образом (1, 2) Расставляем знаки «+» и «–» в вершинах цикла, начиная с клетки (1, 2). В «–» клетках ищем минимальный груз
6. Проверяем найденный план на оптимальность. 6.1 Для «занятых» клеток: 6.2 Для «свободных» клеток: Строим в таблице цикл пересчета относительно клетки (3, 3). Он пойдет следующим образом (3, 3) Расставляем знаки «+» и «–» в вершинах цикла, начиная с клетки (3, 3). В «–» клетках ищем минимальный груз
7. Проверяем найденный план на оптимальность. 7.1 Для «занятых» клеток: 7.2 Для «свободных» клеток: Так как все 8. Найдем минимальную стоимость перевозок: Ответ:
|