Материал: УП - Методы оптимальных решений
Задания для самостоятельной работы
Задание 1. Для изготовления двух видов продукции P1 и P2 используют три вида сырья (S1, S2, S3).
На изготовление единицы продукции P1 используют сырье S1 – a1 (ед.), S2 – a2 (ед.), S3 - a3 (ед.). На изготовление единицы продукции P2 используют сырье S1 – b1 (ед.), S2 – b2 (ед.), S3 – b3 (ед.). Запасы сырья S1 составляют не более чем k1 , сырья S2 – не более чем k2 , сырья S3 – не более чем k3.
Прибыль от единицы продукции P1 составляет руб., от P2 составляет руб.
Необходимо составить такой план выпуска продукции, чтобы при ее реализации получить максимальную прибыль.
Данные для выполнения задания соответствующего варианта представлены в табл. 21.
Таблица 21
Вар. |
A1 |
a2 |
a3 |
b1 |
b2 |
b3 |
k1 |
k2 |
k3 |
|
|
1 |
2 |
3 |
4 |
2 |
3 |
3 |
305 |
676 |
400 |
5 |
6 |
2 |
9 |
7 |
4 |
5 |
8 |
16 |
143 |
122 |
132 |
3 |
2 |
3 |
2 |
7 |
5 |
3 |
3 |
6 |
576 |
344 |
570 |
4 |
7 |
4 |
6 |
7 |
2 |
3 |
5 |
4 |
421 |
567 |
321 |
5 |
7 |
5 |
2 |
6 |
3 |
10 |
3 |
5 |
900 |
540 |
700 |
4 |
5 |
6 |
2 |
4 |
9 |
4 |
6 |
2 |
720 |
300 |
422 |
3 |
2 |
7 |
4 |
5 |
6 |
2 |
7 |
9 |
279 |
756 |
674 |
6 |
2 |
8 |
3 |
7 |
9 |
2 |
9 |
3 |
279 |
392 |
549 |
4 |
7 |
9 |
2 |
4 |
5 |
6 |
7 |
8 |
320 |
440 |
550 |
3 |
4 |
10 |
5 |
4 |
9 |
2 |
1 |
4 |
422 |
516 |
312 |
5 |
7 |
11 |
3 |
4 |
12 |
9 |
8 |
2 |
550 |
600 |
472 |
2 |
8 |
12 |
2 |
3 |
6 |
7 |
4 |
8 |
330 |
410 |
520 |
3 |
2 |
13 |
5 |
4 |
9 |
2 |
3 |
4 |
212 |
512 |
400 |
4 |
5 |
14 |
6 |
4 |
2 |
6 |
7 |
2 |
715 |
472 |
128 |
7 |
8 |
15 |
7 |
2 |
3 |
2 |
4 |
5 |
572 |
244 |
560 |
2 |
3 |
16 |
2 |
3 |
4 |
2 |
4 |
5 |
672 |
567 |
322 |
3 |
4 |
17 |
2 |
4 |
7 |
2 |
3 |
3 |
572 |
322 |
496 |
3 |
7 |
18 |
2 |
3 |
7 |
5 |
6 |
8 |
219 |
300 |
420 |
5 |
6 |
19 |
4 |
2 |
1 |
8 |
7 |
2 |
500 |
617 |
650 |
4 |
4 |
20 |
3 |
4 |
6 |
2 |
3 |
5 |
200 |
215 |
400 |
6 |
2 |
21 |
2 |
3 |
2 |
3 |
6 |
8 |
428 |
672 |
672 |
3 |
8 |
22 |
4 |
3 |
3 |
3 |
4 |
5 |
440 |
393 |
450 |
6 |
5 |
23 |
4 |
3 |
2 |
4 |
3 |
4 |
480 |
144 |
546 |
2 |
4 |
24 |
2 |
4 |
2 |
2 |
5 |
6 |
520 |
670 |
720 |
5 |
4 |
Окончание табл. 21
25 |
3 |
4 |
2 |
4 |
5 |
4 |
672 |
344 |
520 |
3 |
2 |
26 |
2 |
3 |
2 |
4 |
6 |
5 |
505 |
212 |
470 |
4 |
3 |
27 |
4 |
5 |
4 |
3 |
4 |
3 |
320 |
318 |
415 |
4 |
5 |
28 |
3 |
3 |
4 |
2 |
2 |
6 |
550 |
312 |
202 |
4 |
3 |
29 |
8 |
6 |
3 |
2 |
3 |
2 |
340 |
680 |
300 |
3 |
4 |
30 |
6 |
4 |
3 |
2 |
3 |
4 |
600 |
520 |
700 |
4 |
7 |
Заданеи 2. Задана каноническая модель задачи линейного программирования.
Z = CX, AX = A0, X 0, A = (aij)3х5.
Требуется найти max Z М-методом.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
4. Двойственность в линейном программировании
4.1. Понятие двойственности
С каждой задачей линейного программирования тесно связана другая линейная задача, называемая двойственной по отношению к первой (или сопряженной). Первоначальная задача называется исходной.
Связь исходной и двойственной задач заключается в том, что решение одной из них может быть получено непосредственно из решения другой.
Понятие двойственности рассмотрим на примере использования ресурсов: предприятие имеет m видов ресурсов в количестве bi ед. (I = ), из которых производится n видов продукции. Для производства единицы j-ой продукции расходуется аi,j единиц i-го ресурса, а ее стоимость составляет сj единиц. Составить план max выпуска продукции, в стоимостном выражении.
Пусть
хj
(j =
)
– количество единиц j-й продукции,
запланированной
для производства. Тогда исходную задачу
линейного можно сформулировать следующим
образом: найти план (вектор)
который
удовлетворяет ограничениям:
и доставляет максимальное значение целевой функции
max z = с1x1 + с2х2 +…+ сn хn.
Оценим
ресурсы, необходимые для изготовления
продукции. Для этого за единицу стоимости
ресурсов примем единицу стоимости
выпускаемой продукции. Обозначим через
уi
(i
=
)
стоимость единицы i-го ресурса. Тогда
стоимость всех затраченных ресурсов,
идущих на изготовление j
продукции, будет равна
аijyi,
и она должна быть не меньше стоимости
окончательного продукта,
т. е.
аijyi
≥ cj,
(j
=
),
а
стоимость всех имеющихся ресурсов будет
равна f(y)
= b1y1
+ b2y2+
… + bmym=
biyi
и она должна быть min.
Данная задача называется двойственной для исходной. Переменные уi – называются оценками или неявными ценами (в зарубежной литературе – теневыми ценами)
Итак,
двойственную задачу можно сформулировать
следующим образом: найти план (вектор)
который
удовлетворяет ограничениям:
|
|
