ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.07.2021
Просмотров: 1082
Скачиваний: 2
101
4 x
1
+ x
2
–5x
3
≥
4,
2x
1
+ 3x
2
+ x
3
≥
2,
x
j
≥
0, j=1, 2, 3,
α
0
= (0, 0, 3).
2.2. f(X) = 2x
1
+ x
2
+ 3x
3
(max),
x
1
+ 7 x
2
+ x
3
≤
25,
x
1
+ 2x
2
+ 2x
3
≤
45,
–4x
1
+ x
2
+ x
3
≤
8,
x
j
≥
0, j=1, 2, 3,
α
0
= (5, 0, 20).
2.3. f(X) = 60x
1
+ 21x
2
+ 4x
3
(min),
20 x
1
+ 7 x
2
– 3x
3
≥
4,
15 x
1
+ 2x
2
+x
3
≥
1,
2x
1
+ 2x
2
+ x
3
≥
3,
x
j
≥
0, j=1, 2, 3,
α
0
= (0, 1, 1).
Задача
3.
Найти
оптимальное
решение
данной
задачи
,
решив
двойственную
к
ней
задачу
.
3.1. f(X) = 6x
1
+ 9x
2
+15x
3
(min),
– x
1
+ x
2
+ 3x
3
≥
4,
2 x
1
+ x
2
– x
3
≥
2,
x
j
≥
0, j=1, 2, 3.
3.2.. f(X) = 6x
1
+ 2x
2
+ 5x
3
(min),
–3 x
1
+ x
2
+ x
3
≥
2,
2 x
1
– 4x
2
– x
3
≥
3,
x
j
≥
0, j=1, 2, 3,
3.3 f(X) = 6x
1
+ 2x
2
+ 5x
3
(min),
–3 x
1
+ x
2
+ x
3
≥
1,
2 x
1
– 4x
2
– x
3
≥
2,
x
j
≥
0, j=1, 2, 3,
3.4. f(X) = 2x
1
+ x
2
+5x
3
(min),
x
1
– 2 x
2
+ x
3
≥
3,
2x
1
– 5x
2
+ 3x
3
≥
5,
3x
1
+ x
2
+ 4x
3
≥
7,
x
j
≥
0, j=1, 2, 3,
3.5. f(X) = x
1
+ 11x
2
+3x
3
(min),
3 x
1
– 2 x
2
+ 2x
3
≥
2,
x
1
+ x
2
+2x
3
≥
3,
–2x
1
+ 3x
2
– 3x
3
≥
–5,
x
j
≥
0, j=1, 2, 3,
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
102
Задача
4.
Является
ли
данный
вектор
α
оптимальным
решением
задачи
ЛП
?
4.1. f(X) = 7x
1
+ 2x
2
+ 2x
3
+ 5x
4
(max),
3 x
1
– x
2
+ x
3
+ 2x
4
= 7,
x
1
+ 2x
2
–x
3
+ x
4
= 2,
x
j
≥
0, j=1, 2, 3, 4,
α
= (0, 0, 1, 3).
4.2. f(X) = 4x
1
– 5x
2
+ x
3
– 3x
4
(min),
x
1
+ x
2
+ x
3
+ x
4
= 17,
2x
1
– x
2
+–x
3
– 2x
4
= 7,
x
j
≥
0, j=1, 2, 3, 4,
α
= (0, 5, 18, 0).
4.3. f(X) = x
1
+ 4x
2
+ 3x
3
+ x
4
(min),
8 x
1
+ 7 x
2
+ 6 x
3
+ 28x
4
= 28,
4x
2
+ 3x
3
+ 11x
4
= 11,
3x
2
–x
3
+5x
4
= 5,
x
j
≥
0, j=1, 2, 3, 4,
α
= (1, 2, 1, 0).
4.4. f(X) = x
1
+ 5x
2
–x
3
(max),
4x
1
+ x
2
+ x
3
≤
12,
x
1
+ 3x
2
+ x
3
≥
3,
2x
1
+ x
2
– 4x
3
≤
2,
x
j
≥
0, j=1, 2, 3,
α
= (0, 2, 0) .
4.5. f(X) = 3x
1
+ 2x
2
– x
3
(min),
x
1
– x
2
– 2x
3
≥
–5,
x
1
+ 3x
2
–2x
3
≥
4,
–x
1
+ x
2
+ x
3
≥
5,
x
j
≥
0, j=1, 2, 3,
α
= (0, 5, 0)
4.6. f(X) = 5x
1
– 3x
2
+16x
3
(min),
x
1
+ 2 x
2
+ 3x
3
= 4,
x
1
– 2x
2
+8x
3
≥
5,
x
1
≥
0, x
2
≥
0.
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
103
2.11.
Экономическое
содержание
симплекс
алгоритма
и
двойственности
Экономическую
трактовку
переходов
от
одной
симплекс
таблицы
к
другой
,
элементов
симплексных
таблиц
и
двойственности
проведем
на
примере
рационального
использования
предприятием
технологических
способов
и
ресурсов
при
производстве
некоторой
продукции
.
Пример
.
Предприятие
может
производить
продукцию
,
используя
четыре
технологических
способа
и
три
вида
ресурсов
.
Технологическая
матрица
А
–
затрат
ресурсов
при
производстве
единицы
продукции
за
единицу
времени
использования
технологического
способа
,
вектор
В
-
наличия
ресурсов
и
вектор
С
–
количества
единиц
продукции
,
произведенной
за
единицу
времени
использования
технологических
способов
,
заданы
в
виде
:
).
50
,
25
,
14
,
36
(
,
181
107
208
,
5
2
5
2
1
3
0
5
2
4
3
4
C
B
А
Требуется
составить
производственную
программу
,
обеспечивающую
предприятию
наибольший
выпуск
продукции
при
использовании
имеющихся
технологических
способов
и
наличных
ресурсов
.
Математическая
постановка
.
Найти
вектор
Х
=(x
1
, x
2
, x
3
, x
4
),
доставляющий
наибольшее
значение
целевой
функции
φ
(X) = 36x
1
+ 14x
2
+ 25x
3
+ 50x
4
,
(1)
на
множестве
допустимых
решений
,
заданном
ограничениями
(2)
x
1
0, x
2
0, x
3
0, x
4
0. (3)
Нахождение
оптимального
решения
поставленной
задачи
будем
осуществлять
последовательного
улучшения
плана
для
нахождения
наименьшего
значения
функции
f(X)= -
φ
(X) = -36x
1
- 14x
2
- 25x
3
- 50x
4
(1.1)
на
множестве
допустимых
решений
,
заданном
ограничениями
(2)
и
(3).
Приведем
ограничения
(2)
к
системе
равенств
(2.1)
4x
1
+3x
2
+4x
3
+5x
4
≤
208,
2x
1
+5x
2
+2x
4
≤
107,
x
1
+x
2
+2x
3
+5x
4
≤
181,
4x
1
+3x
2
+4x
3
+5x
4
+x
5
=208,
2x
1
+5x
2
+2x
4
+x
6
=107,
3x
1
+x
2
+2x
3
+5x
4
x
7
=181
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
104
при
помощи
дополнительных
неотрицательных
переменных
х
5
,
х
6
,
х
7
,
которые
,
по
смыслу
,
являются
остатками
ресурсов
после
выполнения
соответствующей
производственной
программы
.
Среди
всех
решений
системы
уравнений
(2.1),
удовлетворяющих
условию
х
1
0,
х
2
0, … ,
х
5
0, … ,
х
7
0,
(3.1)
найдем
решение
,
при
котором
функция
(1.1)
примет
наименьшее
значение
.
Так
как
правые
части
всех
уравнений
системы
(2.1)
неотрицательны
и
каждое
уравнение
содержит
разрешенную
переменную
,
то
приравняв
к
нулю
свободные
переменные
х
1
,
х
2
,
х
3
,
х
4
,
получаем
опорное
решение
x
1
=0, x
2
=0, x
3
=0, x
4
=0, x
5
=208, x
6
=107, x
7
=181, (4.1)
в
котором
первые
четыре
компоненты
x
1
=0, x
2
=0, x
3
=0, x
4
=0 (4.1.1)
соответствуют
программе
,
по
которой
предприятие
ничего
не
производит
.
За
единицу
времени
использования
4-
го
технологического
способа
производится
продукции
[
смотри
(1)]
больше
,
чем
при
использовании
любого
другого
технологического
способа
.
Поэтому
целесообразно
в
первую
очередь
включить
в
план
производства
использование
4-
го
технологического
способа
.
Для
этого
систему
уравнений
(2.1)
перепишем
в
виде
(2.2)
При
х
1
=
х
2
=
х
3
=0
и
не
отрицательности
базисных
переменных
х
5
0,
х
6
0,
х
7
0
получаем
систему
неравенств
0
х
4
181/5.
Таким
образом
,
ресурсы
предприятия
позволяют
увеличить
производство
продукции
при
использовании
4-
го
технологического
способа
максимально
возможное
время
,
т
.
е
.,
при
х
4
= 181/5.
Подставив
его
в
(2.2),
получаем
для
системы
уравнений
(2.1)
новое
опорное
решение
х
1
=0,
х
2
=0,
х
3
=0,
х
4
=
181
5
, x
5
=27, x
6
=
5
173
, x
7
=0,
(4.2)
Это
опорное
решение
определяет
новую
производственную
программу
х
1
=0,
х
2
=0,
х
3
=0,
х
4
=
181
5
. (4.2.1)
x
5
=208 -4x
1
-3x
2
-4x
3
-5x
4
x
6
=107 -2x
1
-5x
2
-2x
4
x
7
=181 -3x
1
-x
2
-2x
3
-5x
4
208 -5x
4
≥
0
107 -2x
4
≥
0
181 -5x
4
≥
0
x
4
≤
208/5
x
4
≤
107/5
x
4
≤
181/5
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
105
Замечание
.
►Чтобы
получить
опорное
решение
(4.2)
достаточно
было
в
системе
(2.1)
неизвестную
х
4
сделать
разрешенной
.
Правые
части
уравнений
остануться
неотрицательными
,
если
разрешающий
элемент
а
34
= 5
выбирается
согласно
критерию
0
4
4
min
i
a
i
i
a
b
, (5)
т
.
е
., min {
5
181
,
2
107
,
5
208
}=
5
181
.
После
преобразования
Жордана
с
выбранным
разрешающим
элементом
,
получаем
общее
решение
системы
уравнений
(2.1)
x
1
+ 2x
2
+ 2x
3
+ x
5
- x
7
= 27
4
5
x
1
+
23
5
x
2
-
4
5
x
3
+ x
6
-
2
5
x
7
=
173
5
(2.3)
3
5
x
1
+
1
5
x
2
+
2
5
x
3
+ x
4
+
1
5
x
7
=
181
5
Приравняв
к
нулю
свободные
переменные
х
1
,
х
2
,
х
3
,
х
7
,
получаем
опорное
решение
,
совпадающее
с
(4.2),
в
котором
первые
4-
е
компоненты
определяют
производственную
программу
(4.2.1),
т
.
е
.
х
1
=0,
х
2
=0,
х
3
=0,
х
4
=
181
5
.
◄
Далее
необходимо
ответить
на
вопрос
,
обеспечивает
ли
программа
(4.2.1)
наибольшее
производство
продукции
при
существующих
ограничениях
.
Для
этого
выразим
из
последнего
уравнения
системы
(2.3)
разрешенную
переменную
х
4
через
свободные
переменные
х
1
,
х
2
,
х
3
,
х
7
,
т
.
е
.
х
4
=
181
5
-
3
5
x
1
-
1
5
x
2
-
2
5
x
3
-
1
5
x
7
,
и
подставив
в
целевую
функцию
(1.1),
получим
f(x)
=
-1810-6
х
1
-4
х
2
-5
х
3
+10
х
7
.
(1.2)
В
целевой
функции
(1.2)
переменные
,
характеризующие
производство
продукции
по
1-
му
, 2-
му
и
3-
му
технологическим
способам
,
имеют
отрицательные
коэффициенты
.
Следовательно
,
производственную
программу
(4.2.1)
можно
улучшить
,
если
использовать
1-
й
,
или
2-
й
,
или
3-
й
технологические
способы
.
Наибольшее
уменьшение
функции
f(x)
возможно
при
использовании
1-
го
технологического
способа
,
т
.
е
.
при
увеличении
переменной
х
1
.
Поэтому
,
используя
критерий
(5),
находим
1
27
5
3
5
181
;
5
4
5
137
;
1
27
min
0
1
i
a
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.