Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ МОЛОДЕЖИ И СПОРТА УКРАИНЫ

Одесский национальный морской университет

Самостоятельная работа

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

Выполнила: студентка ЦПО и ПК

Буюкли Ирина

Приняла: Меркт Елена Витальевна

Одесса 2013

1. Оптимизационные задачи - основа целенаправленного эффективного управления

Любое предприятие - это транспортная система. Среди задач управления наиболее важной является оптимизационная задача. Ее цель - определить наиболее эффективное решение или предложить несколько вариантов эффективных решений.

1.1 Структура оптимизационной модели

Любая оптимизационная задача состоит из трех основных элементов:

Управляющие переменные - параметры, на выбор которых мы можем влиять. Они определяют многовариантность решения.

Система ограничений - определяет область допустимых и оптимальных решений.

Целевая функция - показатель, по которому из допустимых решений выбирается оптимальное, наилучшее.

1.2 Информационная модель задачи

2. Расчет опорных планов транспортной задачи

2.1 Проверка закрытости транспортной задачи

- данная транспортная задача не является закрытой, поэтому для приведения к закрытой введем дополнительную строку а₄ = 8 и с тарифами равными 0.

2.2 Опорный план методом минимального элемента

Значение целевой функции.

Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 7. Следовательно, опорный план является вырожденным.

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность удовлетворена, а план соответствует системе ограничений транспортной задачи.

2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F (x) = 3*18 + 4*4 + 3*16 + 7*8 + 4*15 + 6*1 + 0*8 = 240

Улучшение опорного плана.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

u₁ + v₂ = 3; 0 + v₂ = 3; v₂ = 3

u₁ + v₃ = 4; 0 + v₃ = 4; v₃ = 4

u₃ + v₃ = 4; 4 + u₃ = 4; u₃ = 0

u₃ + v₁ = 7; 0 + v₁ = 7; v₁ = 7

u₄ + v₁ = 0; 7 + u₄ = 0; u₄ = - 7

u₃ + v₄ = 6; 0 + v₄ = 6; v₄ = 6

u₂ + v₄ = 3; 6 + u₂ = 3; u₂ = - 3

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij

(1;1): 0 + 7 > 5; ?₁₁ = 0 + 7 - 5 = 2

(2;1): - 3 + 7 > 3; ?₂₁ = - 3 + 7 - 3 = 1, max (2,1) = 2

Выбираем максимальную оценку свободной клетки (1; 1): 5

Для этого в перспективную клетку (1;

1) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

Цикл приведен в таблице (1,1; 1,3; 3,3; 3,1;).

Из х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1,3) = 4. Прибавляем 4 к объемам грузов, стоящих в плюсовых клетках и вычитаем 4 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

u₁ + v₁ = 5; 0 + v₁ = 5; v₁ = 5

u₃ + v₁ = 7; 5 + u₃ = 7; u₃ = 2

u₃ + v₃ = 4; 2 + v₃ = 4; v₃ = 2

u₃ + v₄ = 6; 2 + v₄ = 6; v₄ = 4

u₂ + v₄ = 3; 4 + u₂ = 3; u₂ = - 1

u₄ + v₁ = 0; 5 + u₄ = 0; u₄ = - 5

u₁ + v₂ = 3; 0 + v₂ = 3; v₂ = 3

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij

(2;1): - 1 + 5 > 3; ?₂₁ = - 1 + 5 - 3 = 1

Выбираем максимальную оценку свободной клетки (2; 1): 3

Для этого в перспективную клетку (2;1) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

Цикл приведен в таблице (2,1; 2,4; 3,4; 3,1;).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 1) = 4. Прибавляем 4 к объемам грузов, стоящих в плюсовых клетках и вычитаем 4 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

u₁ + v₁ = 5; 0 + v₁ = 5; v₁ = 5

u₂ + v₁ = 3; 5 + u₂ = 3; u₂ = - 2

u₂ + v₄ = 3; - 2 + v₄ = 3; v₄ = 5

u₃ + v₄ = 6; 5 + u₃ = 6; u₃ = 1

u₃ + v₃ = 4; 1 + v₃ = 4; v₃ = 3

u₄ + v₁ = 0; 5 + u₄ = 0; u₄ = - 5

u₁ + v₂ = 3; 0 + v₂ = 3; v₂ = 3

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i <= c_ij.

Минимальные затраты составят:

F (x) = 5*4 + 3*18 + 3*4 + 3*12 + 4*19 + 6*5 + 0*8 = 228

транспортная задача опорный план

2.3 Анализ оптимального плана

Из 1-го пункта отправления необходимо груз направить в 1-й пункт назначения (4т) и во 2-й пункт назначения (18т).

Из 2-го пункта отправления необходимо груз направить в 1-й пункт назначения (4т) и в 4-й пункт назначения (12т)

Из 3-го пункта отправления груз направить в 3-й пункт назначения (19т) и в 4-й пункт назначения (5т)

Потребность 1-го пункта назначения остается неудовлетворенной на 8 ед.

Оптимальный план является вырожденным, так как базисная переменная x₄₁=0.

Задача имеет множество оптимальных планов, поскольку оценка для (4;4) равна 0.

Размещено на Allbest.ru