Тема 3. Симплекс–метод
Найти все базисные планы канонической задачи ЛП. Построить множество планов эквивалентной задачи ЛП с двумя переменными и указать на нем угловые точки, соответствующие базисным планам.
|
1. f(x) = 2x1+ x2 max x1 – x2 – x3 = – 2 , x1 +2x2 + x4 = 7 , xj 0 , j = 1,…,4.
|
2. f(x) = x1 – x2 max x1 + x2 + 3 x3 + x4 = 3 , x1 – x2 + x3 + 2 x4 = 1 , xj 0 , j = 1,…,4.
|
|
3. f(x) = 2 x1 + 2 x2 +x3 +5x4 max x1 – x2 + x4 = 3 , 2 x2 + x3 + 2 x4 = 6 , xj 0 , j = 1,…,4. |
4. f(x) = 4 x1 + 3 x2 – x3 max x1 + x2 + x3 = 3 , x1 – x2 = 1 , xj 0 , j = 1,2,3. |
Решить симплекс–методом следующие задачи ЛП.
|
5. f(x) = – x1+ x2 min – 2x1+ x2 2 x1 – 2 x2 2 x1 + x2 5 xj 0, j =1,2 |
6. f(x) = 2 x1+ 3 x2 max 3x1 – x2 – 3 x1 – 2 x2 2 xj 0, j =1,2 |
|
7. f(x) = 2x1+ x2 max x1 – x2 – x3 = – 2 , x1 +2x2 + x4 = 7 , xj 0 , j = 1,…,4. |
8 f(x) = 2 x1 + 2 x2 +x3 +5x4 max x1 – x2 + x4 = 3 , 2 x2 + x3 + 2 x4 = 6 , xj 0 , j = 1,…,4. |
9. Фирма производит три вида продукции P1 , P2 , P3 используя для этого два вида сырья R1 и R2 . Расход сырья на одно изделие, его запасы и цена реализации единицы продукции приведены в таблице:
-
Вид сырья
Расход сырья на единицу
Запас сырья
P1
P2
P3
R1
4
2
4
32
R2
1
1
3
30
цена
4
3
5
Найти план выпуска продукции, при котором суммарный доход фирмы наибольший.
10. Фирма специализируется на производстве компьютерных столов трех типов A, B, C, что требует различных затрат труда на каждой стадии производства:
-
Пpоизводственный участок
Затpаты тpуда (чел–час.)
A
B
C
Лесопилка
Сбоpочный цех
Отделочный цех
1
2
1
2
4
1
4
2
2
В течении недели можно планировать работу на лесопилке на 360 чел–час. в сборочном цехе – на 520 чел–час. и в отделочном цехе– на 220 чел–час. Прибыль от продажи каждого стола типов A, B, C составляет соответственно 9, 11, 15 долларов.
Составить и решить задачу линейного программирования, считая целью максимизацию суммарной прибыли.
Решить следующие задачи ЛП методом больших штрафов (М–методом).
|
11. f(x) = x1 – x2 max x1 + x2 + 3 x3+ x4 = 3, x1 – x2 + x3 + 2x4 = 1, xj 0 , j = 1,2,3. |
12. f(x) = x1 – x2 – x3 + x4 min x1 +6 x2 – x3 + x4 = –5, 3 x1 – 2 x2 + 2 x3 – x4 = 2, xj 0, j =1,...,4 |
|
13. f(x) = 2 x1+ 3 x2 max x1 + 5 x2 10, 3 x1 – 2 x2 15, xj 0, j =1,2 |
14. f(x) = x1 + 3 x2 + x3 max x1 + x2 = 6, x1 – x2 – x3 = –2, xj 0 , j = 1,2,3. |
|
15.
|
16. f(x) = 9x1+2x2+3x3+2x4 min –x1+ x2+ x3– x4 = 2, 3x1+x2 – x3– x4 = –1, xj 0, j=1,2,3,4 |
,
,
.Дополнительно решить задачи 13 и 15 геометрически.
Тема: Динамическое программирование
В следующих задачах
найти оптимальное распределение средств
между
предприятиями при условии, что прибыль
,
полученная от каждого предприятия,
является функцией от вложенных в него
средств
.
Вложения кратны
,
в функции
заданы таблично.
1.
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
|
|
5 |
9 |
12 |
14 |
15 |
18 |
20 |
24 |
27 |
|
|
|
7 |
9 |
11 |
13 |
16 |
19 |
21 |
22 |
25 |
|
|
|
6 |
10 |
13 |
15 |
16 |
18 |
21 |
22 |
25 |
|
2.
|
|
1 |
2 |
3 |
4 |
5 |
|
|
|
0,2 |
0,9 |
1 |
1,2 |
2 |
|
|
|
1 |
1,1 |
1,3 |
1,4 |
1,8 |
|
|
|
2,1 |
2,5 |
2,9 |
3,9 |
4,9 |
|
|
|
0 |
2 |
2,5 |
3 |
4 |
|
3. В условиях
задачи 1 найти оптимальное распределение
средств для
.
4. В условиях
задачи 1 найти оптимальное распределение
средств
между четырьмя, если функция прибыли
для четвертого предприятия задана
таблицей:
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
|
3 |
5 |
7 |
11 |
13 |
15 |
20 |
22 |
24 |
5. В условиях
задачи 2 найти оптимальное распределение
средств для
между четырьмя предприятиями.
6. В условиях задачи 2 найти оптимальное распределение средств между 2-м, 3-м и 4-м предприятиями.
7. Найти оптимальный маршрут переезда из пункта 1 в пункт 10 по схеме движения:
8. Найти оптимальный маршрут переезда из пункта 1 в пункт 10 по схеме движения:
9. Перечислить 14 возможных маршрутов из пункта 1 в пункт 10.
10. Найти оптимальный маршрут, если между пунктами 7 и 9 не существует сообщения.
11. Найти оптимальный маршрут переезда из пункта 1 в пункт 10 по схеме движения:
