Применение графического метода и симплекс-метода для решения задач линейного программирования
Начальные затраты: Рнач = 500 + 800 + 50 + 650 + 500 + 1350 + 200 = 4050. Проведем поэтапное улучшение опорного плана с помощью метода потенциалов. Добавим к опорному плану дополнительные строку и столбец (см. рисунок 1). Примем значение одной из получившихся дополнительных ячеек за 0. Рассчитаем по формуле: «значение издержки» = «значение в ячейке дополнительной строки» + «значение ячейки дополнительного столбца» остальные значения дополнительных ячеек. После этого, составим вспомогательную матрицу, значения в которой рассчитываются по следующей формуле: «значение в матрице» = «значение издержки» - («значение в ячейке дополнительной строки» + «значение ячейки дополнительного столбца»). 0 -1 -1 -1 0 0 0 8 -3 -1 0 0 В данной вспомогательной матрице присутствуют отрицательные числа. Так как каждое число в матрице показывает на сколько изменятся общие транспортные затраты при загрузке данной клетки единицей груза, то данный план можно улучшить переместив в соответствующую клетку некоторое количество продукции (если число отрицательное, затраты уменьшаются). Из всех отрицательных значений выбираем наибольшее по модулю, так как ее воздействие на общие затраты является максимальным. Отметим знаком «+» в транспортной таблице ячейку соответствующую положению максимального по модулю отрицательного числа в вспомогательной матрице. Кроме нее мы пометим знаками «-» и «+» другие занятые числами ячейки таким образом, что в каждой строке и каждом столбце транспортной таблицы число знаков «+» будет равно числу знаков «-». Это всегда можно сделать единственным образом, причем в каждой строке и каждом столбце содержится по одному «+» и «-». То есть помеченные знаками клетки должны образовывать цикл (см. рисунок 1). Затем мы определим минимум из всех элементов, помеченных знаком «-», и выберем одну ячейку, где этот минимум достигается. В нашем случае таковой является ячейка, содержащая 25 единиц груза. Следовательно, данная ячейка при пересчете должна стать свободной.
Р1 = 500 + 800 + 75 + 650 + 625 + 1125 + 200 = 3975. 4 минимальное количество груза в ячейке: 100 0 0 -4 -4 - 8 3 0 0 8 0 -1 0 0
|
