1118 логистика. Оглавление 1 Основные направления расширения комплекса услуг сбытовой деятельности предприятия
 Скачать 59.77 Kb.
|
|
Искомый элемент равен c31=6. Для этого элемента запасы равны 400, потребности 200. Поскольку минимальным является 200, то вычитаем его. x31 = min(400,200) = 200.
Искомый элемент равен c38=0. Для этого элемента запасы равны 200, потребности 200. Поскольку минимальным является 200, то вычитаем его. x38 = min(200,200) = 200.
Далее, согласно алгоритму, ищем элементы среди не вычеркнутых.
Искомый элемент равен c58=0, но т.к. ограничения выполнены, то x58=0.
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи. 2. Подсчитаем число занятых клеток таблицы, их 12, а должно быть m + n - 1 = 12. Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно: F(x) = 9*200 + 9*500 + 11*100 + 6*200 + 7*400 + 0*200 + 12*550 + 13*350 + 10*350 + 9*400 + 8*450 = 33250 Этап II. Улучшение опорного плана. Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v7 = 9; 0 + v7 = 9; v7 = 9 На данном этапе возникла ситуация, когда для оставшихся занятых клеток не известно ни одного из потенциалов. Это результат вырожденности решения. Для его преодоления в одну из клеток нужно внести нулевую поставку, таким образом, такая клетка станет условно занятой. Для неизвестного потенциала u2 нулевую поставку можно разместить в клетках: (2;7), v7=9 Для неизвестного потенциала u3 нулевую поставку можно разместить в клетках: (3;7), v7=9 Для неизвестного потенциала u4 нулевую поставку можно разместить в клетках: (4;7), v7=9 Для неизвестного потенциала u5 нулевую поставку можно разместить в клетках: (5;7), v7=9 Для неизвестного потенциала v1 нулевую поставку можно разместить в клетках: (1;1), u1=0 Для неизвестного потенциала v2 нулевую поставку можно разместить в клетках: (1;2), u1=0 Для неизвестного потенциала v3 нулевую поставку можно разместить в клетках: (1;3), u1=0 Для неизвестного потенциала v4 нулевую поставку можно разместить в клетках: (1;4), u1=0 Для неизвестного потенциала v5 нулевую поставку можно разместить в клетках: (1;5), u1=0 Для неизвестного потенциала v6 нулевую поставку можно разместить в клетках: (1;6), u1=0 Для неизвестного потенциала v8 нулевую поставку можно разместить в клетках: (1;8), u1=0 Среди этих клеток, в которых может быть размещена нулевая поставка, наименьший тариф имеет клетка (1, 8) с c18 = 0. Следовательно, нулевую поставку размещаем в клетку (1, 8), и она становится условно занятой. u1 + v8 = 0; 0 + v8 = 0; v8 = 0 Ранее поставленный псевдоноль из ячейки (5;8) убираем. u3 + v8 = 0; 0 + u3 = 0; u3 = 0 u3 + v1 = 6; 0 + v1 = 6; v1 = 6 u2 + v1 = 9; 6 + u2 = 9; u2 = 3 u2 + v2 = 11; 3 + v2 = 11; v2 = 8 u4 + v2 = 12; 8 + u4 = 12; u4 = 4 u4 + v6 = 13; 4 + v6 = 13; v6 = 9 u3 + v5 = 7; 0 + v5 = 7; v5 = 7 u5 + v5 = 8; 7 + u5 = 8; u5 = 1 u5 + v3 = 10; 1 + v3 = 10; v3 = 9 u5 + v4 = 9; 1 + v4 = 9; v4 = 8
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij (1;1): 0 + 6 < 8; ∆11 = 0 + 6 - 8 = -2 > 0 (3;2): 0 + 8 < 10; ∆32 = 0 + 8 - 10 = -2 > 0 max(2,2) = -2 Выбираем максимальную оценку свободной клетки (1;1): 8 Для этого в перспективную клетку (1;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (1,1 → 1,8 → 3,8 → 3,1). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 8) = 0. Прибавляем 0 к объемам грузов, стоящих в плюсовых клетках и вычитаем 0 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
Проверим оптимальность опорного плана. Найдем |