Контрольная работа по "Математическим методам"

 
 

     Искомый элемент равен 0

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

     x46 = min(10,10) = 10.

 
 
 

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

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

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

     5*100 + 5*30 + 5*100 + 2*10 + 5*130 + 7*60 + 13*30 + 11*80 + 0*10  = 3510

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

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

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

     Проверим  возможность уменьшения суммарных  затрат на поставку продукции. С этой целью для каждой свободной от поставки клетки определяется величина Δij, характеризующая изменение суммарных  затрат на поставку (в расчете на единицу перераспределяемой продукции), при условии включения в план единичной поставки хij=1 от поставщика Аi к потребителю Вj.

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

     Величина  Δij называется оценкой свободной  клетки (или характеристика).

     В исходном решении задачи имеются  клетки свободные от поставок.

     Необходимо  вычислить значение оценок Δij для  этих свободных от поставок клеток. С этой целью для каждой свободной  клетки составляется означенный цикл перерасчета (или замкнутая цепь, круг, кольцо, контур и т.д.).

     Под циклом пересчета (цепью) понимается замкнутая  ломаная линия. Вершинами цикла (цепи) являются клетки таблицы, проще –  вершины лежат в клетках таблицы.

     Причем  одна из вершин находится в свободной  от поставки клетке, в той, для которой  определяется оценка Δij. Все другие вершины находятся в базисных клетках, т.е. клетках, занятых поставками.

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

     В цикле знаки по вершинам расставляют  начиная с вершины, лежащей в  свободной клетке, для которой  определяется Δij. В нее записывают знак плюс, затем знаки по вершинам чередуются: минус, плюс , минус, плюс и  т. д., независимо от того, расставляют  ли их по часовой стрелке или в  обратном направлении. Таким образом, в цикле всегда насчитывается  одинаковое число положительных  и отрицательных вершин.

     Следующий этап решения транспортной задачи заключается  в улучшении опорного плана.

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

     Шаг 1. Определяем оценку для каждой свободной  клетки.

     (1;1): В свободную клетку (1;1) поставим  знак «+», а в остальных вершинах  многоугольника чередующиеся знаки  «-», «+», «-». 

 

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

     Оценка  свободной клетки равна Δ11 = (11) - (5) + (7) - (13) + (5) - (5) = 0.

     (1;3): В свободную клетку (1;3) поставим  знак «+», а в остальных вершинах  многоугольника чередующиеся знаки  «-», «+», «-». 

 

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

     Оценка  свободной клетки равна Δ13 = (13) - (5) + (7) - (13) = 2.

     (1;4): В свободную клетку (1;4) поставим  знак «+», а в остальных вершинах  многоугольника чередующиеся знаки  «-», «+», «-». 

 

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

     Оценка  свободной клетки равна Δ14 = (4) - (5) + (7) - (11) + (5) - (2) = -2.

     (1;5): В свободную клетку (1;5) поставим  знак «+», а в остальных вершинах  многоугольника чередующиеся знаки  «-», «+», «-». 

 

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

     Оценка  свободной клетки равна Δ15 = (5) - (5) + (7) - (11) = -4.

     (1;6): В свободную клетку (1;6) поставим  знак «+», а в остальных вершинах  многоугольника чередующиеся знаки  «-», «+», «-».