Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Метод двойного предпочтения.

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

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

Базисное распределение, полученное способом двойного предпочтения, приведено в табл. 11.5.

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

Таблица 11.5

Решение транспортной задачи методом потенциалов.

Известно количество однородного груза в тоннах, которое имеется у поставщиков (А₁,А₂,А₃,А₄,А₅), который нужно в определенном размере доставить потребителям (В₁,В₂,В₃,В₄). Известны также расстояния между всеми поставщиками и потребителями.

Все эти исходные данные записаны в таблицу, называемую «матрицей» (табл. 11.2), в которой в верхнем правом углу соответствующих клеток записаны расстояния в километрах. Кроме того, в этой матрице имеются вспомогательные строка и столбец, клетки которых пока остаются незаполненными.

Необходимо закрепить потребителей за поставщиками так, чтобы среднее расстояние перевозок груза было наименьшим, т. е. найти минимум объема транспортной работы в тонно-километрах.

Порядок вычисления следующий:

Разработка начального плана (опорного решения).

Трудоемкость решения транспортных задач методом потенциалов значительно сокращается, если первоначальное распределение будет ближе к оптимальному. Поэтому предложен ряд способов наилучшего построения первоначального распределения. Одним из них является способ двойного предпочтения, рассмотренный ранее, результаты отражены в таблице 11.6.

После того как указанным способом весь груз будет распределен, можно рассчитать количество тонно-километров, полученных в данном первоначальном распределении. Для этого умножим количество груза в каждой клетке на указанное в ней расстояние и полученные произведения сложим.

Суммарная транспортная работа составит Z= 7625 т·км (смотри выше).

Таблица 11.6

Выполняется условие (11.7) N = m + n – 1 = 5 + 4 – 1 = 8