Лекции 6
.docТипичные задачи линейного программирования
Задача №1 (об использовании ресурсов).
Для осуществления n различных процессов Тj, j=1..n, требуется m видов ресурсов Si, i=1..m, запасы которых ограничены и равны bi, i=1..m. Известен расход ресурсов Si на каждую единицу процесса Тj в виде матрицы значений аij и доход от реализации единицы продукции Тj в виде вектора сj. Требуется найти распределение процессов Тj, при котором доход будет максимальным.
Решение. Пусть хj, j=1…n, распределение процессов (количество единиц продукции), W – доход. Тогда W = cj xj - целевая функция.
Система ограничений – неравенств:
aij xj ≤ bj i =1…m, которая переводится в систему равенств введением переменных xn+i, i=1…m, означающих не использованные ресурсы Si.
Получаем: aijxj + xn+i = bi , i=1…m.
Начальное решение xj = 0, j = 1…n, базисные переменные xn+j = bi , i = 1…m. Решается задача максимума целевой функции W.
Замечание. Если есть ограничения в виде неравенства «больше или равно», то используем двух этапный симплекс - метод.
Пусть имеется дополнительно k неравенств
aij xj ≥ bi , i = (m +1)…(m + k).
Вводятся по 2 дополнительные переменные
xm+n+i и xm+n+k+i , i = 1…k,
а неравенства представляются в виде следующих уравнений:
ai +m,j xj – xm+n+i +xm+n+k+i = bm+i , i = 1…k.
Начальное решение xj = 0, j =1…n, xm+n+i = 0, i = 1…k, базисные переменные xi+n , i =1…m, xm+n+k+i , i = 1…k.
Целевая функция первого этапа xn+m+k+i, необходимо найти минимум .
После первого этапа решения обращается в ноль и находится начальное решение для второго этапа, при этом xn+m+k+i = 0 для всех i = 1…k. Если этого не получится, то требования противоречивы.
При решении второго этапа искусственные переменные xn+m+k+i не рассматриваются.
Задача №2 (о распределении выпуска изделий).
За время Т необходимо изготовить m видов продукции Аi, i=1..m, в количестве Ni каждое.
Эти виды продукции выпускаются на n предприятиях (цехах, станках и т.д.) Пj, j=1..n. Известно аij количество продукции Аi, выпускаемое на предприятии Пj за единицу времени, bij – стоимость единицы продукции Аi, выпущенное на предприятии Пj. Требуется найти xij – время работы предприятия Пj над продукцией Аi (одновременно на предприятии может выпускаться только один вид продукции), при котором стоимость выпускаемой продукции будет минимальной.
Решение.
Ограничения:
1. Время работы каждого предприятия не может превышать Т.
xij ≤Т , j =1…n.
2. Количество выпускаемой продукции должно соответствовать номенклатуре
aij xij =Ni , i = 1…m.
Целевая функция – общая стоимость выпускаемой продукции
W = aij bij xij - должна быть минимальной.
Вводим дополнительные переменные и записываем неравенства в виде равенств:
xi j + yj = Т, j=1…n. Дополнительные переменные yj означают время простоя предприятия Пj.
Во второе ограничение вводим искусственные переменные yj .
aij xij + yn+i = Ni , i = 1…m (yn+i – искусственные переменные).
Необходимо использовать двухэтапный симплекс-метод.
Этап1. Ищется минимум yn+i , и добиваются, чтобы yn+i = 0 при всех i = 1…m.
Этап2. Потом решается основная задача: ищется минимум целевой функции
W= aijbijxij.
Задача №3 (транспортная задача).
В пунктах Рi имеется однородный груз в количестве аi, i=1..m. Его необходимо перевести в пункты Qi в количестве bj, j=1..n, так чтобы стоимость перевозок была минимальна. При этом количество требуемого груза равно имеющимся запасам . Известна cij – стоимость перевозки единицы груза из Рi в Qi.
Решение. Пусть хij – количество груза, перевозимого из Рi в Qj.
Ограничения:
1. Количество груза из Pi на все пункты должно быть равно имеющимся запасам
xij = ai , i =1…m
2. Количество груза, пребываемого в Qj со всех пунктов, равно потребностям
xij = bj , j = 1…n.
Целевая функция W =cij xij, требуется найти её минимум.
P.S. Если груз превышает потребности, вводится фиктивный пункт Qn+1 , на которую переводится остаток груза bn+1 со стоимостью перевозок ci,n+1 = 0.
Для решения можно ввести искусственные переменные yi и zj, тогда
xij + yi = ai , i = 1…m,
xij + zj = bj , j = 1…n.
На первом этапе минимизируем y i + zj. После того, как все yi и zj будут равны нулю, находим допустимое базисное решение. Далее (на втором этапе) находим минимум основной целевой функции W.
А можно системы уравнений
xij = ai и xij = bj , i =1…m , j =1…n,
преобразовать так, что бы хij – входили в уравнения по одному разу с коэффициентом +1. Это избавит нас от введения искусственных переменных yi и zi и позволит использовать одноэтапный симплекс-метод.
Задача №4 (о выборе оптимального варианта аппаратуры).
Требуется спроектировать устройство, состоящее из m последовательных блоков (i = 1…m). Имеется n различных вариантов выполнения каждого модуля
(j = 1…n). Заданы ограничения в виде максимальной стоимости (X), габаритов (Y) и максимального времени производства операций (z).
Требуется выбрать оптимальный вариант.
Пусть xi , yi, zi – стоимость, габариты и время операций для каждого блока.
xi ≤X, yi ≤Y, zi ≤Z,причем xi{ xi1…xin}, yi {yi1…yin}, zi{zi1…zin}, где xij , yij , zij – стоимость, габариты, время операций i - блока при j –ом варианте его исполнения.
Пусть c1, c2, c3 – коэффициенты, характеризующую относительную ценность уменьшение стоимости, габаритов и времени.
Целевую функцию W = с1 xi + c2 yi + c3zi необходимо сделать минимальной.
Т.к. xi, yi, zi могут принимать только дискретные значения из {xi1…xin}, {yi1…yin}, {zi1… zin}, то задача решается методами дискретного программирования.