ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.07.2021
Просмотров: 1081
Скачиваний: 2
106
и
соответствующий
ему
разрешающий
элемент
а
11
=1.
Исключаем
переменную
х
1
из
всех
уравнений
системы
(2.3),
кроме
1-
го
уравнения
.
Получим
очередное
общее
решение
системы
(2.1)
и
соответствующее
ему
опорное
решение
,
для
проверки
оптимальности
которого
выразим
переменную
х
1
через
новые
свободные
переменные
х
2
,
х
3
,
х
5,
х
7
и
подставим
в
целевую
функцию
(1.2)
и
т
.
д
.
Замечание
.
►Тот
же
результат
можно
получить
иначе
,
а
именно
,
вернутся
к
началу
решения
поставленной
задачи
и
представить
соотношение
(1.1)
в
виде
уравнения
36
х
1
+ 14
х
2
+ 25
х
3
+ 50
х
4
= –
f(x).
(1.3)
Затем
добавить
уравнение
(1.3)
к
системе
(2.3)
и
получить
систему
уравнений
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.1)
3
5
x
1
+
1
5
x
2
+
2
5
x
3
+ x
4
+
1
5
x
7
=
181
5
,
36
х
1
+ 14
х
2
+ 25
х
3
+ 50
х
4
= –
f(x).
В
последнем
уравнении
системы
(2.3.1)
положительный
наибольший
коэффициент
,
равный
4
= 50,
соответствует
переменной
х
4
.
Исключим
переменную
х
4
из
последнего
уравнения
.
Для
этого
,
умножив
третье
уравнение
системы
(2.3.1)
на
(-50)
и
прибавив
к
четвертому
уравнению
,
получим
систему
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.2)
3
5
x
1
+
1
5
x
2
+
2
5
x
3
+
x
4
+
1
5
x
7
=
181
5
,
6x
1
+ 4x
2
+ 5x
3
-10x
7
= -1810 –
f(x).
Первые
3-
и
уравнения
системы
(2.3.2)
представляют
общее
решение
системы
уравнений
(2.1)
и
определяют
опорное
решение
(4.2),
соответствующее
производственной
программе
(4.2.1).
Последнее
уравнение
системы
(2.3.2)
соответствует
функции
цели
(1.2),
выраженной
через
свободные
переменные
х
1
,
х
2
,
х
3
,
х
7
.
Наличие
положительных
коэффициентов
j
при
переменных
в
последнем
уравнении
системы
(2.3.2),
указывает
на
то
,
что
производственная
программа
не
является
оптимальной
и
необходимо
продолжить
ее
улучшение
.
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
107
Для
этого
в
план
производства
дополнительно
вводится
1-
й
технологический
способ
,
так
как
с
помощью
уравнения
(1.2),
которое
соответствует
последнему
уравнению
системы
(2.3.2),
был
установлен
положительный
наибольший
коэффициент
,
равный
j
max
{
j
}= max{6, 4, 5} = 6 =
1
.
Поэтому
свободную
переменную
х
1
делаем
разрешенной
,
используя
преобразование
Жордана
с
разрешающим
элементом
а
11
=1,
выбранному
согласно
критерию
(5),
и
получаем
систему
x
1
+ 2x
2
+ 2x
3
+ x
5
- x
7
= 27,
3x
2
-
5
12
x
3
-
5
4
x
5
+ x
6
+
2
5
x
7
= 13 , (2.3.3)
- x
2
-
5
4
x
3
+ x
4
-
3
5
x
5
+
5
4
x
7
= 20,
8x
2
-7x
3
-6x
5
-4x
7
= -1972 –
f(x),
Первые
3-
и
уравнения
системы
(2.3.3)
являются
общим
решением
системы
уравнений
(2.1)
и
соответствуют
опорному
решению
x
1
=27, x
2
=0, x
3
=0, x
4
=20, x
5
=0, x
6
=13, x
7
=0,
(4.3)
которое
определяет
производственную
программу
с
использованием
1-
го
и
4-
го
технологических
способов
x
1
=27,
x
2
=0, x
3
=0, x
4
=20.
(4.3.1)
При
производстве
продукции
по
этой
программе
полностью
используются
ресурсы
1-
го
и
3-
го
видов
(
х
5
=0,
х
7
=0)
и
остаются
не
использованными
ресурсы
2-
го
вида
(
х
6
=13).
Среди
коэффициентов
при
неизвестных
в
левой
части
последнего
уравнения
системы
(2.3.3)
нет
ни
одного
положительного
.
Это
соответствует
тому
,
что
целевая
функция
f(x)
= -1972 + 8
х
2
+ 7
х
3
+ 6
х
5
+ 4
х
7
(1.3)
не
может
быть
уменьшенной
и
ее
наименьшее
значение
равно
f
min
(
х
)
= -1972
при
x
2
=0, x
3
=0, x
5
=0, x
7
=0.
Следовательно
,
возвращаясь
к
исходной
задаче
,
можно
утверждать
,
что
использование
программы
(4.3.1)
обеспечит
наибольшее
значение
функции
(1)
φ
max
(x) =1972
,
т
.
е
.
наибольшее
производство
продукции
.
◄
Таким
образом
,
направленный
перебор
опорных
решений
(
последовательное
улучшение
плана
)
системы
условий
задачи
привел
к
оптимальной
программе
использования
имеющихся
технологических
способов
и
ресурсов
,
с
указанием
неиспользованных
ресурсов
и
максимального
объема
производства
продукции
.
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
108
Рассмотренный
процесс
решения
можно
записать
в
виде
набора
симплексных
таблиц
1, 2, 3,
в
которых
представлены
матрицы
систем
уравнений
(2.3.1)
(2.3.2)
(2.3.3).
Табл
.1
А
1
А
2
А
3
А
4
А
5
А
6
А
7
В
4 3 4 5 1 0 0
208
2 5 0 2 0 1 0
107
3
1
2
5 0 0 1
181
-
γ
36 14
25
50 0
0 0
0
Табл
.2 1 2 2 0 1 0 -1
27
4/5 23/5 -4/5 0 0 1 -2/5
173/5
3/5 1/5 2/5 1 0 0 1
181/5
δ
6
4
5
0 0
0 -10
-1810
Табл
.3 1 2
2
0 1
0 -1
27
0
3
-12/5 0
-4/5 1 2/5
13
0
-1/5
-4/5
1
-3/5 0 1/5
20
δ
0
-8
-7
0 -6
0 -4
-1972
Каждый
элемент
симплексной
таблицы
имеет
экономический
смысл
.
Например
,
во
2-
ой
симплекс
таблице
при
использовании
в
производстве
1-
го
технологического
способа
,
что
соответствует
переменной
х
1
,
в
векторе
А
1
элемент
а
31
=3/5
показывает
насколько
единиц
необходимо
уменьшить
производство
продукции
с
использованием
4-
го
технологического
способа
,
элементы
а
11
=1
и
а
21
= 4/5 –
показывают
сколько
потребуется
единиц
ресурсов
1-
го
и
2-
го
видов
,
при
этом
общее
производство
продукции
увеличится
на
1
=6
единиц
..
Элементы
строки
оценок
оптимального
опорного
решения
в
последней
симплексной
таблице
также
имеют
экономический
смысл
.
Например
,
оценки
2
= -8
и
δ
3
= -7
векторов
А
2
и
А
3
,
соответствующие
переменным
х
2
и
х
3
,
показывают
,
что
за
одну
единицу
времени
использования
2-
го
и
3-
го
технологических
способов
,
не
входящих
в
оптимальную
программу
,
производство
продукции
уменьшится
на
8
единиц
и
на
7
единиц
соответственно
.
В
заключение
заметим
,
что
в
рассмотренном
примере
возможна
проверка
результата
.
Так
как
,
в
оптимальной
производственной
программе
х
2
=0,
х
3
=0,
то
предположим
,
что
предприятие
при
производстве
продукции
не
обладало
2-
м
и
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
109
3-
м
технологическими
способами
.
Тогда
математическая
модель
задачи
с
1-
м
и
2-
м
технологическими
способами
,
соответствующими
переменным
х
1
,
х
4
,
примет
следующий
вид
:
Решив
эту
задачу
графически
(
рис
.1),
можно
убедиться
в
совпадении
с
ранее
полученными
результатами
.
При
этом
последовательное
улучшение
производственной
программы
при
переходе
от
одного
опорного
решения
к
другому
,
т
.
е
.
Х
1
=
(x
1
=0,x
4
=0)
Х
2
=
(x
1
=0, x
4
=181/5)
Х
3
=
(x
1
=27, x
4
=20)
соответствует
движению
от
одной
вершины
выпуклого
множества
[
Х
1
Х
2
Х
3
Х
4
]
допустимых
решений
к
соседней
вершине
по
соединяющей
их
стороне
.
Для
формирования
двойственной
задачи
к
исходной
задаче
введем
вектор
оценки
ресурсов
Y=(
у
1
,
у
2
,
у
3
) ,
в
котором
отражаются
условия
производства
продукции
,
т
.
е
.
использование
предприятием
технологических
способов
и
ресурсов
.
Из
матрицы
А
векторов
условий
исходной
задачи
следует
,
что
для
производства
единицы
продукции
по
1-
му
технологическому
способу
необходимо
затратить
4-
е
единицы
ресурса
1-
го
вида
, 2-
е
единицы
ресурса
2-
го
вида
и
3-
и
единицы
ресурсов
3-
го
вида
.
В
двойственных
оценках
(
у
1
,
у
2
,
у
3
)
затраты
всех
видов
ресурсов
за
единицу
времени
использования
1-
го
технологического
способа
составят
4
у
1
+ 2
у
2
+ 3
у
3
и
при
этом
будет
произведено
36
единиц
продукции
.
Так
как
ценность
затраченных
ресурсов
не
меньше
ценности
произведенной
продукции
,
то
4
у
1
+ 2
у
2
+ 3
у
3
36.
Аналогично
рассуждая
,
получим
оценку
затрат
всех
ресурсов
за
единицу
времени
использовании
2-
го
технологического
способа
3
у
1
+ 5
у
2
+
у
3
,
которая
не
может
быть
меньше
ценности
произведенной
продукции
,
т
.
е
. 3
у
1
+ 5
у
2
+
у
3
14,
и
т
.
д
.
по
всем
технологическим
способам
.
Оценка
всех
имеющихся
для
производства
ресурсов
равна
208
у
1
+ 107
у
2
+ 181
у
3
.
Определение
расчетных
оценок
ресурсов
c
водит
c
я
к
нахождению
вектора
Y =
(
у
1
, y
2
, y
3
),
которому
соответствует
наименьшее
значение
оценки
всех
ресурсов
,
т
.
е
.
х
4
53,5
grad f(x)
41,6
36,2
Х
2
20
Х
3
Х
1
Х
4 53,5
27 52 60,3
х
1
Рис
.1
X=(x
1
,x
4
)- ?
f(X) 36x
1
+50x
4
→
max
4x
1
+5x
4
≤
208,
2x
1
+2x
4
≤
107,
3x
1
+5x
4
≤
181,
x
1
≥
0, x
4
≥
0.
Х
0
=(27;20)
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
110
ψ
(Y) = 208y
1
+ 107y
2
+181y
3
min
(1
д
)
4y
1
+2y
2
+3y
3
≥
36,
3y
1
+5y
2
+y
3
≥
14,
4y
1
+2y
3
≥
25,
5y
1
+2y
2
+5y
3
≥
50,
(2
д
)
y
1
≥
0 y
2
≥
0 y
3
≥
0 (3
д
)
Решение
полученной
задачи
легко
найти
с
помощью
2-
й
теоремы
двойственности
,
согласно
которой
для
оптимальных
решений
X
o
= (
х
1
o
,
х
2
o
,
х
3
o
,
х
4
o
)
и
Y
o
=(y
1
o
, y
2
o
, y
3
o
)
пары
двойственных
задач
необходимо
и
достаточно
выполнение
условий
x
1
о
(4y
1
о
+ 2y
2
о
+ 3y
3
о
- 36) = 0
y
1
о
(4x
1
о
+ 3x
2
о
+ 4x
3
о
+ 5x
4
о
- 208) = 0
x
2
о
(3y
1
о
+ 5y
2
о
+ y
3
о
- 14) = 0
y
2
о
(2x
1
о
+ 5x
2
о
+ 2x
4
о
- 107) = 0
x
3
о
(4y
1
о
+ 2y
3
о
- 25) = 0
y
3
о
(3x
1
о
+ x
2
о
+ 2x
3
о
+ 5x
4
о
- 181) = 0
. x
4
о
(5y
1
о
+ 2y
2
о
+ 5y
3
о
- 50) = 0
Из
решения
исходной
задачи
следует
,
что
X
o
=(27;0;0;20),
т
.
е
.,
х
1
о
>0,
x
4
о
>0.
Поэтому
4y
1
о
+ 2y
2
о
+ 3y
3
о
- 36 =0, 5y
1
о
+ 2y
2
о
+ 5y
3
о
- 50 = 0.
Т
.
к
. 2x
1
о
+5x
2
о
+ 2x
4
о
< 107,
то
двойственная
оценка
2-
го
ресурса
равна
нулю
,
т
.
е
.
у
2
о
=0.
Следовательно
,
приходим
к
системе
уравнений
4y
1
о
+ 2y
2
о
+ 3y
3
о
- 36 =0,
5y
1
о
+ 2y
2
о
+ 5y
3
о
- 50 = 0,
у
2
о
=0,
решением
которой
будет
вектор
Y
o
=(6, 0, 4)
двойственных
оценок
ресурсов
,
доставляющий
общей
оценке
ресурсов
наименьшее
значение
,
равное
1972,
что
соответствует
1-
й
теореме
двойственности
.
Замечание
.
►
Решение
двойственной
задачи
Y
o
=(6, 0, 4)
совпадает
с
противоположенными
оценками
,
содержащимися
в
4-
й
строке
последней
симплексной
таблицы
3,
векторов
условий
А
5
,
А
6
,
А
7
,
соответствующих
разрешенным
переменным
в
системе
(1.1),
Двойственные
оценки
имеют
определенный
экономический
смысл
.
Например
,
двойственная
оценка
третьего
ресурса
у
3
= 4
показывает
,
что
добавление
одной
единицы
третьего
ресурса
обеспечит
прирост
производства
продукции
на
4
единицы
.
◄
В
оптимальной
производственной
программе
используются
полностью
1-
й
и
3-
й
ресурсы
.
Возможное
уменьшение
исходных
объемов
этих
ресурсов
может
оказать
влияние
на
программу
использования
технологических
способов
,
ресурсов
и
на
общее
количество
производимой
продукции
.
Следовательно
,
такое
использование
ресурсов
создает
в
производстве
«
узкие
места
».
Поэтому
желательно
иметь
некоторый
запас
таких
ресурсов
,
чтобы
сохранить
структуру
использования
технологических
способов
и
иметь
возможность
для
увеличения
производства
продукции
.
Ведем
вектор
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.