- •Задачи линейного программирования
- •Постановка задачи
- •Задачи для решения
- •1.2. Свойства решений задач линейного программирования
- •Графический метод решения задач линейного программирования Случай двух переменных
- •Случай многих переменных
- •1.4.2.Симплексный метод
- •Этап 1. Определение начального опорного плана.
- •Случай вырождения
- •Задачи для решения
- •Метод искусственного базиса
- •Задачи для решения
- •1.5. Теория двойственности в линейном программировании
- •1.5.1. Постановка задачи
- •Некоторые частные случаи
- •1.5.2. Основные теоремы двойственности
- •Задачи для решения
- •1.5.3. Геометрическая интерпретация двойственных задач
- •1.5.4. Двойственный симплекс – метод
- •Этап 1. Определение начального опорного плана (псевдоплана).
- •Этап 2. Определение оптимального плана.
- •Задачи для решения
- •1.6. Экономическая интерпретация двойственности
- •1.6.1. Анализ моделей на чувствительность.
- •Использование графического метода.
- •Использование симплекс-метода.
- •Использование графического метода.
- •Использование симплекс-таблицы.
- •Использование графического метода.
- •Использование симплекс-таблицы.
- •Использование графического метода.
- •Использование симплекс-таблицы.
- •Использование графического метода.
- •Использование симплекс-таблицы.
- •Применение компьютера Инструкция по использованию надстройки «Поиск решения»
- •1.10. Решение задачи с использованием
Использование симплекс-таблицы.
Пусть доход, получаемый с единицы продукции П2 изменился на величину 2. Тогда последняя строка результирующей симплекс-таблицы примет вид
Таблица 1.44
Базис |
Решение |
x1 |
x2 |
x3 |
x4 |
x5 |
Fmax |
15,2 + 2,42 |
0 |
0 |
0 |
0,3 + 0,12 |
0,8 – 0,42 |
Для сохранения оптимальности решения необходимо, чтобы в последней строке симплекс-таблицы отсутствовали отрицательные элементы. Следовательно, должно выполняться
0,3 + 0,12 ³ 0;
0,8 – 0,42 ³ 0.
Откуда –3 £ 2 £ 2.
Таким образом, при изменении c2 – коэффициента целевой функции при переменной х2 – от 0 (3 – 3 = 0) до 5 (3 + 2 = 5) оптимальные значения переменных остаются неизменными.
Т и п о в ы е к о н т р о л ь н ы е з а д а н и я
Производственное предприятие может изготавливать два вида продукции П1 и П2, для изготовления которой используются три типа ресурсов Р1, Р2, Р3. Максимально допустимые суточные запасы ресурсов предприятия ограничены соответственно величинами b1, b2, b3. Удельный расход i-го типа ресурса для изготовления j-го вида продукции составляет aij единиц. Отпускная цена единицы продукции j-го вида равна cj ден. ед. Найти объем выпуска продукции каждого вида, максимизирующий суммарный доход производственного предприятия, если необходимые числовые данные приведены в таблице 1.45.
1. Построить математическую модель и найти симплексным методом оптимальное решение следующей задачи линейного программирования.
2. Построить математическую модель двойственной задачи и найти ее оптимальное решение.
3. Указать статус ресурсов.
4. Определить, на сколько можно уменьшить запасы недефицитных ресурсов (если они имеются).
5. Определить максимальное приращение дефицитных ресурсов.
6. Определить наиболее выгодный ресурс.
7. Оценить целесообразность приобретения bk единиц k-го ресурса стоимостью rk ден. ед.
8. Установить целесообразность ввода в производство нового вида продукции П3, удельный расход ресурсов Р1, Р2, Р3 на изготовление которой составляет a13, a23, a33 единиц, а отпускная цена готовой продукции равна c3 ден. ед.
9. Привести пример анализа на чувствительность оптимального решения к изменению произвольного коэффициента целевой функции.
Таблица 1.45. Исходные данные для различных вариантов задания №1
|
Номер варианта |
|||||||||
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
c1 |
5 |
1 |
5 |
5 |
1 |
1 |
5 |
2 |
3 |
4 |
c2 |
4 |
4 |
2 |
1 |
2 |
3 |
3 |
3 |
2 |
3 |
a11 |
1 |
4 |
1 |
8 |
4 |
2 |
4 |
3 |
24 |
4 |
a12 |
2 |
3 |
1 |
5 |
5 |
4 |
4 |
0 |
15 |
10 |
a21 |
1 |
4 |
2 |
1 |
0 |
8 |
10 |
0 |
8 |
4 |
a22 |
1 |
8 |
1 |
1 |
1 |
6 |
20 |
2 |
12 |
3 |
a31 |
2 |
4 |
4 |
1 |
2 |
1 |
4 |
4 |
0 |
2 |
a32 |
1 |
2 |
6 |
4 |
1 |
0 |
2 |
2 |
6 |
1 |
b1 |
8 |
12 |
8 |
40 |
20 |
20 |
20 |
15 |
120 |
40 |
b2 |
6 |
32 |
8 |
5 |
2 |
48 |
80 |
6 |
36 |
24 |
b3 |
7 |
12 |
24 |
8 |
6 |
3 |
16 |
16 |
24 |
8 |
k |
1 |
1 |
2 |
2 |
3 |
3 |
1 |
2 |
3 |
1 |
bk |
2 |
3 |
4 |
3 |
2 |
2 |
4 |
1 |
4 |
3 |
rk |
3 |
4 |
3 |
2 |
2 |
4 |
3 |
2 |
5 |
4 |
a13 |
2 |
3 |
1 |
5 |
2 |
4 |
5 |
5 |
10 |
2 |
a23 |
5 |
4 |
2 |
1 |
1 |
4 |
8 |
3 |
4 |
6 |
a33 |
3 |
2 |
3 |
2 |
1 |
0 |
2 |
8 |
4 |
1 |
c3 |
7 |
5 |
4 |
8 |
3 |
2 |
4 |
6 |
4 |
7 |
Продолжение таблицы 1.45
|
Номер варианта |
|||||||||
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
|
c1 |
6 |
5 |
2 |
2 |
2 |
2 |
5 |
1 |
3 |
2 |
c2 |
1 |
10 |
3 |
5 |
4 |
3 |
2 |
3 |
2,5 |
4 |
a11 |
8 |
14 |
4 |
2 |
6 |
9 |
6 |
2 |
4 |
5 |
a12 |
2 |
8 |
7 |
0 |
0 |
18 |
3 |
8 |
3 |
6 |
a21 |
12 |
20 |
0 |
1 |
0 |
5 |
4 |
4 |
2 |
1 |
a22 |
15 |
25 |
2 |
0 |
3 |
0 |
3 |
2 |
3 |
0 |
a31 |
0 |
2 |
5 |
4 |
0 |
0 |
0 |
2 |
0 |
0 |
a32 |
3 |
0 |
4 |
8 |
8 |
2 |
1 |
1 |
1 |
1 |
b1 |
16 |
56 |
28 |
8 |
24 |
36 |
18 |
16 |
24 |
30 |
b2 |
60 |
100 |
5 |
5 |
15 |
15 |
24 |
12 |
18 |
6 |
b3 |
9 |
4 |
20 |
32 |
24 |
4 |
2 |
8 |
5 |
5 |
k |
2 |
1 |
2 |
3 |
1 |
3 |
3 |
3 |
2 |
1 |
bk |
4 |
5 |
4 |
2 |
4 |
4 |
5 |
2 |
2 |
3 |
rk |
5 |
3 |
7 |
2 |
3 |
1 |
2 |
1 |
6 |
4 |
a13 |
2 |
7 |
4 |
2 |
8 |
6 |
3 |
4 |
4 |
3 |
a23 |
6 |
10 |
1 |
0 |
5 |
5 |
3 |
3 |
2 |
3 |
a33 |
3 |
0 |
5 |
8 |
3 |
0 |
0 |
2 |
1 |
1 |
c3 |
5 |
4 |
6 |
3 |
7 |
8 |
6 |
4 |
5 |
3 |
Окончание таблицы 1.45
|
Номер варианта |
|||||||||
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
|
c1 |
3 |
4 |
1 |
3 |
1 |
2 |
2 |
1 |
2 |
4 |
c2 |
2 |
2 |
3 |
1 |
3 |
3 |
4 |
3 |
6 |
2 |
a11 |
1 |
0 |
1 |
0 |
4 |
12 |
4 |
3 |
2 |
1 |
a12 |
1 |
2 |
1 |
2 |
2 |
6 |
6 |
4 |
2 |
1 |
a21 |
9 |
1 |
4 |
1 |
0 |
3 |
0 |
0 |
0 |
0 |
a22 |
3 |
0 |
2 |
1 |
3 |
6 |
2 |
6 |
2 |
1 |
a31 |
0 |
4 |
0 |
2 |
1 |
1 |
4 |
3 |
1 |
2 |
a32 |
1 |
5 |
1 |
1 |
2 |
0 |
3 |
2 |
0 |
0 |
b1 |
5 |
10 |
6 |
8 |
16 |
36 |
36 |
12 |
16 |
6 |
b2 |
27 |
8 |
14 |
4 |
9 |
18 |
10 |
12 |
8 |
4 |
b3 |
1 |
40 |
3 |
6 |
7 |
4 |
24 |
12 |
6 |
10 |
k |
2 |
2 |
2 |
1 |
3 |
2 |
2 |
3 |
2 |
1 |
bk |
2 |
2 |
2 |
1 |
1 |
2 |
1 |
2 |
3 |
1 |
rk |
5 |
3 |
2 |
2 |
3 |
4 |
3 |
4 |
2 |
3 |
a13 |
1 |
5 |
3 |
2 |
2 |
4 |
6 |
2 |
4 |
3 |
a23 |
3 |
2 |
2 |
2 |
3 |
3 |
5 |
3 |
2 |
1 |
a33 |
0 |
8 |
1 |
2 |
2 |
2 |
4 |
4 |
3 |
2 |
c3 |
4 |
6 |
4 |
2 |
4 |
1 |
3 |
2 |
5 |
3 |