ЗАДАЧА О РАСШИВКЕ УЗКИХ МЕСТ ПРОИЗВОДСТВА. При выполнении оптимальной производственной программы второй и третий ресурсы используются полностью, т.е. образуют узкие места производства.
Будем их заказывать дополнительно. Пусть Tt1,t2,t3- вектор дополнительных объемов ресурсов. Так как мы будем использовать найденные двойственные оценки ресурсов, то должно выполняться условие H Q-1T 0. Задача состоит в том, чтобы найти вектор T 0, t2, t3, максимизирующий суммарный прирост прибыли W 8t2 2t3 1 при условии сохранения двойственных оценок ресурсов и, следовательно, структуры производственной программы предполагая, что можно надеяться получить дополнительно не более 13 первоначального объема ресурса каждого вида 3 причем по смыслу задачи t2 0, t3 0. 4 Переписав неравенства 2 и 3 в виде 5 из условия 3 следует t21483, t31583 6 приходим к задаче ЛП максимизировать 1 при условиях 5, 6 и 4. Эту задачу легко решить графически см. рис. 2. Программа расшивки имеет вид t10, t214, t30 и прирост прибыли составит 112. Сводка результатов приведена в таблицe 2. сj36321013bx4iyiti2341103500aij420214808 142870158020xj3112001500112j0043ТРАНСПОР ТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Однородный продукт, сосредоточенный в 3 пунктах производства хранения в количествах 40 60 70 единиц, необходимо распределить между 4 пунктами потребления, которым необходимо соответственно 36 32 40 53 единиц.
Стоимость перевозки единицы продукта из пункта отправления в пункт назначения известна для всех маршрутов и равна С . Необходимо составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства и общие транспортные расходы по доставке продуктов были минимальными.
Для решения транспортной задачи чаще всего применяется метод потенциалов.
Общий объем производства аi 406070170 больше, чем требуется всем потребителям bi 3632 40 53 161, т.е. имеем открытую модель транспортной задачи.
Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом потребления 170-161 9 единиц, причем тарифы на перевозку в этот пункт условимся считать равными нулю, помня, что переменные, добавляемые к левым частям неравенств для превращения их в уравнения, входят в функцию цели с нулевыми коэффициентами. Первое базисное допустимое решение легко построить по правилу северо-западного угла. Потреблениеb1 36b2 32b3 40b4 53b5 9Производство а1 40364p1 0 a2 60 2832 p2 a3 70 8539 p3 q1 q2 q3 q4 q5 Общая стоимость всех перевозок для первого базисного допустимого решения L 36 2 4 3 28 2 32 8 7 53 281 Один из потенциалов можно выбрать произвольно, так как в системе 3, 4 одно уравнение линейно зависит от остальных.
Положим, что р1 0. Остальные потенциалы находим из условия, что для базисных клеток. В данном случае получаем 11 0, p1 q1 - c11 0, 0q1 -2 0, q1 2 12 0, p1 q2 - c12 0, 0q2 -3 0, q2 3 22 0, p2 q2 - c22 0, р2 3-2 0, р2 -1 и т.д получим q32, p35, q4 -4, q5 -5. Затем по формуле 6 вычисляем оценки всех свободных клеток 21 p2 q5 - c21 -12-4 -3 31 p3 q1 - c31 52-2 5 32 1 13 -2 14 -5 24 0 15 -5 25 -6. Находим наибольшую положительную оценку max 5 Для найденной свободной клетки 31 строим цикл пересчета - замкнутую ломаную линию, соседние звенья которой взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы, одна из вершин находится в данной свободной клетке, а все остальные - в занятых клетках.
Это будет 31-11-12-22-23-33. Производим перераспределение поставок вдоль цикла пересчета 36436-42812283228-32204088- 8 Получаем второе базисное допустимое решение bjb1 36 b2 32b3 40b4 53 b59 ai а1 40 2812 p1 0 a2 60 2040p2 -1 a3 70 8539p3 0q1 2q2 3q3 2q4 1q50Находим новые потенциалы, новые оценки. 13 -2 14 0 15 0 21 -3 24 -2 25 -1 32 -4 33 -5, т.е. все ij 0 i 1,m j 1,n Общая стоимость всех перевозок для второго базисного допустимого решения L 28 2 12 3 20 2 40 8 2 53 241 минимальная стоимость.