2631761_42.1412840525.10196
.pdf4.Решите данные задачи линейного программирования методом искусственного базиса:
|
3x1 − 5x2 + 5x3 + 16x4 − 2x5 → min, |
||
а) |
−2x1 + x2 + 3x3 − x4 + 2x5 = 2, |
||
|
x1 + x2 − 2 x3 |
− x5 = 1, |
|
|
|
||
|
|
x1 0, x2 0, …, x5 0; |
|
|
x1 + 2x2 + 6x3 + 2x4 + 4x5 → min |
||
б) |
2x1 + x2 + 4x3 − x4 |
= 4, |
|
|
x2 + 2x3 + x4 |
− 2x5 = 2, |
|
|
|
x1 0, x2 0, …, x5 0.
5.Для каждой из данных задач линейного программирования сформулируйте двойственную задачу и решите ее графически, а затем с помощью теоремы о дополняющей нежесткости найдите решение исходной задачи:
2x1 + 3x2 + 2x4 → min, |
|||
x1 − x2 + 2x3 + 3x4 9, |
|||
а) x + 2x − x + 2x 8, |
|||
1 |
2 |
3 |
4 |
|
|
|
x1 0, x2 0, …, x4 0; |
|
||||
|
15x1 + 15x2 + 14x3 + 15x4 + 17x5 + 20x6 → min, |
|||||||
|
|
3x1 |
+ x2 |
+ 2x3 + |
x4 + 5x5 + 3x6 |
75, |
||
б) |
|
x + x |
− 2x + 2x + |
x |
+ 2x |
36, |
||
|
|
1 |
2 |
3 |
4 |
5 |
6 |
|
x1 0, x2 0, …, x6 0.
6.Для каждой из данных задач линейного программирования сформулируйте двойственную задачу и найдите оптимальные решения обеих задач:
|
9x1 + 8x2 → max, |
|
10x1 +12x2 → min |
|||||
|
7x1 + 2x2 14, |
|
|
6x1 |
+ 2x2 = 8, |
|||
а) |
|
|
|
10, |
б) |
|
|
+ 3x2 4, |
−x1 + 3x2 |
−2x1 |
|||||||
|
5x − 4x |
2 |
= 13, |
|
|
5x − x 15, |
||
|
|
1 |
|
|
|
1 |
2 |
|
|
x1 0, |
x2 − любого знака; |
|
x1 − любого знака, x2 0. |
7.Решите данные задачи целочисленного программирования методом ветвей и границ:
|
x1 + 2x2 → max, |
|
x1 + 3x2 → max, |
||||||
|
1 |
2 |
|
21, |
|
|
1 |
2 |
51, |
|
5x |
+ 7x |
|
|
14x |
+ 9x |
|||
а) |
−x + 3x |
|
8, |
б) |
−6x + 3x |
1, |
|||
|
1 |
2 |
|
|
|
1 |
2 |
||
|
x1 0, x2 0, |
|
|
x1 0, x2 0, |
|||||
|
x1, x2 ; |
|
|
|
x1, x2 . |
121
ГЛАВА 4. ОПТИМАЛЬНЫЕ РЕШЕНИЯ В ЛИНЕЙНЫХ ЗАДАЧАХ УПРАВЛЕНИЯ ПРОИЗВОДСТВОМ И ЦЕПЯМИ ПОСТАВОК
§ 4.1. ЛИНЕЙНАЯ ЗАДАЧА ПЛАНИРОВАНИЯ ПРОИЗВОДСТВА
Мы уже неоднократно рассматривали задачу оптимального планирования производства. Проведем подробное исследование конкретного примера такой задачи с использованием всей изученной теории.
ПРИМЕР 4.1.1. Предприятие может выпускать четыре вида продукции, используя для этого три вида ресурсов. Известна технологическая матрица A затрат каждого из ресурсов на единицу каждой продукции, вектор b объемов ресурсов и вектор c цен продукции:
|
4 |
3 |
4 |
5 |
|
|
|
208 |
|
|
A = |
2 |
5 |
0 |
2 |
|
, |
b = |
107 |
|
, c = (36 14 25 50). |
|
|
|
|
|
|
|
|
|
|
|
|
3 |
1 |
2 |
5 |
|
|
|
181 |
|
|
|
|
|
|
|
|
Требуется определить производственную программу, обеспечивающую предприятию наибольшую выручку при имеющихся ограниченных ресурсах.
Решение. Математическая модель задачи такова: требуется найти производственную программу
x1 x = x2 ,x3x4
максимизирующую выручку
z = 36x1 +14x2 + 25x3 +50x4 → max
при ограничениях по ресурсам
4x1 + 3x2 |
+ 4x3 + 5x4 |
208, |
|||
|
|
+ 5x2 |
|
+ 2x4 |
107, |
2x1 |
|
||||
3x |
+ x |
+ 2x |
+ 5x |
181, |
|
|
1 |
2 |
3 |
4 |
|
122