![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Выбор клетки, в которую необходимо послать перевозкуТранспортная задача является частным случаем задачи линейного программирования, поэтому алгоритм ее решения также следует общим принципам алгоритма симплексного метода решения задач на минимум. Если отождествлять занятые клетки с переменными, входящими в базис, а незанятые - с независимыми, варьируемыми переменными, то в транспортной задаче загрузке (ввод в базис) подлежит та клетка, которой соответствует max[(Ui+Vj)-Сij]. В рассматриваемом примере mах(1;6;1) = 6, клетку А2В4 необходимо сделать занятой. Для этого сначала надо определить, сколько единиц груза может быть в нее перераспределено (аналог – определить максимально допустимое увеличение выбранной независимой переменной). Построение цикла и определение величины перераспределения груза. Основной принцип перераспределения – неизменность построчных и постолбцовых сумм. Основная задача – построить цикл и найти максимальною величину груза Отыскиваем цикл (алгоритмически самостоятельная задача) и, начиная движение от клетки, отмеченной знаком «+», поочередно проставляем знаки «-» и «+» (принцип неизменности сумм). Затем находим В рассматриваемом примере знаком «-» помечены клетки (А3В4), (А4В5), (А2В2). Отсюда В рассматриваемом примере нулевую перевозку необходимо переместить в клетку А2B4, остальные числа при вычитании и прибавлении нуля, очевидно, не изменятся. В ячейке А3B4 ноль, как значимая цифра, отменяется. В результате перераспределения Таблица 8.7
Интересно заметить, что на втором этапе (табл. 8.7) загрузка ячейки А1В5 составляет 50 ед. Эти 50 ед. выводят из базы сразу две ячейки А4В5, и А2В2, то в одной из них, например А2В2 устанавливается активный ноль. Окончательная таблица имеет вид табл. 8.8. Полученный план является оптимальным. Его стоимость равна 4150 ед. Таблица 8.8
|