Методика решения задач линейного программирования
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
76 ед. продукции П3, продукцию вида П1 производить не следует. При этом предприятие получит максимальную прибыль, которая составит 395,3 денежных единиц.
Останутся неиспользованными 99,529 ед. ресурса Р3, а ресурсы Р1 и Р2 будут израсходованы полностью.
Двойственная задача
Чтобы составить модель двойственной задачи, запишем матрицу исходной задачи (1) - (5) в следующем виде:
.(9)
Транспонируем матрицу (9) и получим матрицу (10) двойственной задачи.
.(10)
По исходной матрице (10) запишем модель задачи, двойственной исходной задаче:
? = 360y1 + 192y2 + 180y3 > min(11)
18y1 + 6y2 + 5y3 9;
15y1 + 4y2 + 3y3 10;
y1 + 8y2 + 3y3 16;
yi 0 (i =).(13)
Из теорем двойственности следует, что если решена одна из пары двойственных задач, то одновременно найдено решение и другой задачи. Компоненты оптимального плана этой задачи находятся в строке целевой функции последней симплекс-таблицы решенной задачи,
В п. 2 найден оптимальный план исходной задачи, его компоненты находятся в табл. 3. В f-строке этой же таблицы содержатся и компоненты уi* оптимального плана двойственной задачи (11) - (13). Выписать компоненты уi* поможет соответствие между переменными двойственных задач
Чтобы установить это соответствие, преобразуем ограничения-неравенства (12) в эквивалентные уравнения, вычитая из левых частей дополнительные неотрицательные переменные у1*, у2*, у3*, равные разностям между левыми и правыми частями этих неравенств. Тогда модель (11) - (13) запишется в виде:
? = 360y1 + 192y2 + 180y3 > min;
18y1 + 6y2 + 5y3 - y4 = 9;
y1 + 4y2 + 3y3 - y5 = 10;
3y1 + 8y2 + 3y3 - y6 = 16;
yi 0 (i =).
В этой записи переменные у4, у5, у6 являются базисными, а у1, у2, у3 - свободными. В исходной задаче (6) - (8) переменные x1, x2, x3 являются свободными, а x4, x5, x6 - базисными. Сопоставим базисным переменным одной задачи свободные переменные другой и наоборот, т.е.
СПБП
x1 x2 x3x4 x5 x6
у4 у5 у6у1 у2 у3(14)
БПСП
Воспользуемся соответствием (14) для нахождения компонентов оптимального плана двойственной задачи. Находим их в табл. 3 в f-строке
.x1x2x3x4x5х6f395,34,941000,2351,6180у4у5у6у1у2у3
Получим оптимальный план двойственной задачи:
Y* = (0,235; 1,618; 0; 4,941; 0; 0).(15)
Как следует из теорем двойственности, экстремальные значения функций разрешимых двойственных задач совпадают:
fmax = ?min = 395,3.
Величины y1* = 0,235, y2* = 1,618 и y3* = 0 ден. ед. являются теневыми ценами на ресурсы S1, S2, S3 соответственно и в данном случае служат мерой их дефицитности.
Как следует из оптимального плана (15) двойственной задачи, избыточным является ресурс S3 (y3* = 0). Ресурс S2 является наиболее дефицитным (y2* = 1,618), ресурс S1 менее дефицитным (y1* = 0,235).
2. Решение транспортной задачи методом потенциалов
Постановка задачи
В пункте Аi (i = 1,2,3) находится однородная продукция в количестве ai единиц. Себестоимость единицы продукции в пункте Аi равна ci. Готовая продукция поставляется в пункт Вj (j = 1,2,3,4), потребности которого составляют bj единиц. Стоимость сij перевозки единицы продукции из пункта Ai в пункт Bj известна. Требуется:
составить экономико-математическую модель задачи, позволяющую найти план перевозки готовой продукции из пункта Аi производства в пункт В; потребления при полном удовлетворении спроса на продукцию в этих пунктах, обеспечивающего минимальные суммарные затраты, вызванные производством и доставкой продукции;
найти оптимальный план перевозки продукции при дополнительном условии, что продукция пункта Аk, в котором себестоимость ее производства наименьшая, должна быть распределена полностью;
вычислить величину fmin минимальных суммарных затрат на производство и доставку продукции;
назвать пункты, в которых остается нераспределенная продукция, и указать объемы такой продукции.
А = ; с = (4 2 1); В = (180 720 360 480); С = .
Построение экономико-математической модели
Запишем начальные условия задачи в форме табл. 1.
Таблица 1
ПоставщикиМощности поставщиковСебестоимость продукцииПункты потребления и их спросВ1В2В3В4180720360480А154043+4=76+4=105+4=91+4=5x11x12x13x14А266028+2=105+2=710+2=126+2=8x21x22x23x24А378019+1=107+1=84+1=56+1=7x31x32x33x34
Обозначим через xij (i =; j =) количество продукции, которое планируется перевезти от поставщика Ai потребителю Bj, а через f - суммарные затраты на производство и перевозку.
Непосредственно в таблице подсчитываем суммарные тарифы на производство и перевозку продукции из пункта Ai (i =) в пункт Bj (j =).
Целевая функция задачи запишется в виде:
f = 7x11 + 10x12 + 9x13 + 5x14 + 10x21 + 7x22 + 12x23 + 8x24 +
+ 10x31 + 8x32 + 5x33 + 7x34.(1)
Запишем ограничения, накладываемые мощностями поставщиков:
x11 + x12 + x13 + x14 540;
x21 + x22 + x23 + x24 660;(2)
x31 + x32 + x33 + x34 780.
Спрос пунктов потребления выражаем в виде равенств:
x11 + x21 + x31 = 180;
x12 + x22 + x32 = 720;(3)
x13 + x23 + x33 = 360;
x14 + x24 + x34 = 480.
Если исключить обратные перевозки, должны выполняться ограничения:
xij 0 (i =; j =).(4)
Соотношения (1) - (4) образуют экономико-математическую модель рассматриваемой задачи: целевая функция (1), описывающая транспортные затраты, минимизируется при ограничениях (2) - (4).
Сравнивая суммарную мощность поставщиков 540 + 660 + 780 = 1980 с суммарным спросом пунктов потребления 180 + 720 + 360 + 480 = 1740, видим, что эти суммы не совпадают. Имеем открытую транспортную задачу.
Час?/p>