Инструменты пользователя

Инструменты сайта


examination:mo:question9

Вопрос 9

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

Классическая задача, частный случай задачи линейного программирования, так как в формулировке задачи только линейные зависимости, но методы решения разработаны свои. Формулировка: Предполагается, что имеется m пунктов производства некоторого однородного продукта и n пунктов потребления этого продукта. ai, i = 1,…,m- количество производимого продукта bj, j = 1,…,n- количество потребляемого продукта.

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

- матрица стоимостей перевозок

- количество перевозимого продукта

Если , то пришлось бы ввести фиктивный пункт потребления и ставить очень большие или нулевые издержки на перевозку в него продукции. Если , то пришлось бы ввести фиктивный пункт производства.

Число уравнений – m+n, линейно независимых – m+n-1 (из условия (5))

Число переменных – m*n

Для базисного решения всего m+n-1 переменных будут ненулевыми.

Любая последовательность клеток таблицы называется набором.

Последовательность, в которой две соседние клетки находятся в одном столбце или в одной строке называется цепью.

Если первая и последняя клетка цепи принадлежат одной строке или одному столбцу, то это цикл.

Если набор не содержит ни одного цикла, то он называется ациклическим.

Пусть набор состоит из m+n-1 клетки (базисного решения). Оптимальное решение следует искать среди ациклических наборов из m+n-1 клетки.

Признак оптимальности

X – базисное решение.

X = ||xij||, i = 1,…, m, j = 1,…, n

Это решение будет оптимальным, если

  1. Vj – Ui = cij, xij > 0 - для базисных клеток

Ui - потенциал пунктов производства

Vj – потенциал пунктов потребления

Методы построения начального плана

Метод прикрепления ближайших пунктов

Выбираем клетку с самой маленькой стоимостью и вписываем всё, что можно. Далее выбираем следующую клетку с наименьшей стоимостью и вписываем в неё и так далее.

Метод северо-западного угла

Берем самую северо-западную клетку (верхнюю левую) и вписываем в неё всё, что можно и так далее, вычёркивая по строке или столбцу.

examination/mo/question9.txt · Последние изменения: 2014/01/15 08:19 (внешнее изменение)