ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.10.2023
Просмотров: 350
Скачиваний: 11
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Базис
Переменные
b
i
x
1
x
2
... x
n
x
n+1
...
x
n+m
x
n+1
a
11
a
12
... a
1n
1 0 0
b
1
x
n+2
a
21
a
22
... a
2n
0 ... 0
b
2
...
... ... ... ... ... ... ... ...
x
n+m
a
m1
a
m2
... a
mn
0 0 1
b
m
c
j
c
1
c
2
... c
n
0 0 0
L
Таблица 2.5
Исходная симплекс-таблица для задачи о хоккейных клюшках и шахматных наборах
Базис
Переменные
b
i
x
1
x
2
x
3
x
4
x
5
x
3
4
6
1
0
0
120
x
4
2
6
0
1
0
72
x
5
0
1
0
0
1
10
c
j
2
4
0
0
0
0
В нашей задаче последняя строка содержит два положительных элемен- та, следовательно, необходимо перейти к шагу 5.
Шаг 5. Выбор разрешающего столбца (переменной, вводимой в базис).
Разрешающий столбец выбирается в соответствии со следующим условием:
Электронный архив УГЛТУ
33
{
}
̅̅̅̅̅̅̅̅̅̅̅ (2.5) где r – номер разрешающего столбца.
Таким образом, при определении разрешающего столбца просматрива- ется последняя строка симплексной таблицы и в ней отыскивается наиболь- ший положительный элемент.
В нашей задаче в качестве разрешающего выберем второй столбец (со- ответствующий переменной x
2
), поскольку в последней строке для этого столбца содержится 4.
Шаг 6. Проверка условия: все a
ir
≤ 0. Если «ДА» - целевая функция не ограничена и решения нет, если «НЕТ» - переход к шагу 7.
Таким образом, необходимо проверить элементы разрешающего столб- ца. Если среди них нет положительных, то задача неразрешима.
В нашем примере все элементы разрешающего столбца положительны
(6, 6 и 1), следовательно, необходимо перейти к шагу 7.
Шаг 7. Выбор разрешающей строки (переменной, выводимой из базиса) по условию:
{
}
̅̅̅̅̅̅
(2.6) где s - номер разрешающей строки.
Таким образом, для тех строк, где элементы разрешающего столбца по- ложительны, необходимо найти частное от деления элемента b
i
(последний столбец таблицы) на элемент, находящийся в разрешающем столбце. В каче- стве разрешающей выбирается строка, для которой результат такого деления будет наименьшим.
Проиллюстрируем выполнение шага 7, обратившись к нашему примеру.
Для первой строки: D
1
= 120 / 6 = 20.
Для второй строки: D
2
= 72 / 6 = 12.
Для третьей строки: D
3
= 10 / 1 = 10.
Наименьший результат деления - в третьей строке, значит именно эту строку мы выбираем в качестве разрешающей, т.е. исключать из базисного решения будем переменную x
5
Элемент, стоящий на пересечении разрешающей строки и разрешающе- го столбца, называется разрешающим элементом. В нашем случае таковым является единица, стоящая на пересечении третьей строки и второго столбца.
Исходная симплекс-таблица нашего примера с выделенными цветом разре- шающей строкой и разрешающим столбцом представлена ниже (табл. 2.6).
Шаг 8. Пересчет элементов симплекс-таблицы (переход к новому базис- ному решению).
Порядок пересчета различных элементов таблицы несколько отличается.
Для элементов разрешающей строки используются следующие формулы:
Электронный архив УГЛТУ
34
(2.7)
где s – номер разрешающей строки,
r – номер разрешающего столбца,
– новые значения пересчитываемых элементов,
a
sj
, b
s
– старые значения пересчитываемых элементов,
a
sr
– старое значение разрешающего элемента.
Таблица 2.6
Исходная симплекс-таблица с выделенными разрешающей строкой и столбцом, а также с иллюстрацией к применению правила прямоугольника
Таким образом, при пересчете элементов разрешающей строки каждый ее элемент делится на разрешающий элемент.
Еще проще пересчитать элементы разрешающего столбца. Все они
(кроме разрешающего элемента) становятся равными нулю:
. (2.8)
Элементы, не принадлежащие разрешающим столбцу и строке, пересчи- тываются по так называемому правилу прямоугольника: мысленно выделяет- ся прямоугольник, в котором элемент, подлежащий пересчету и разрешаю- щий элемент образуют одну из диагоналей. Формулы будут иметь следую- щий вид:
. (2.9) где
– новые значения пересчитываемых элементов,
a
ij
, b
i
, c
j
, L – старые значения пересчитываемых элементов.
Применение правила прямоугольника проиллюстрируем, используя таб- лицу 2.6. Пересчитаем элемент a
11
(в исходной симплекс-табл. 2.5 его значе-
Электронный архив УГЛТУ
35 ние равно 4). В таблице 2.6 можно видеть прямоугольник (прочерчен пунк- тиром), соединяющий четыре элемента, участвующих в пересчете:
Аналогичным образом пересчитываются остальные элементы.
По окончании пересчета осуществляется возврат к шагу 4.
Полностью результат пересчета для нашего примера можно видеть в табл. 2.7.
Таблица 2.7
Симплекс-таблица для задачи о хоккейных клюшках и шахматных наборах
(второе базисное решение)
Базис
Переменные
b
i
x
1
x
2
x
3
x
4
x
5
x
3
4
0
1
0
-6
60
x
4
2
0
0
1
-6
12
x
2
0
1
0
0
1
10
c
j
2
0
0
0
-4
-40
Таким образом, в новом базисном решении базисными переменными яв- ляются: x
2
= 10, x
3
= 60, x
5
= 12 (соответствующие значения можно видеть в последнем столбце таблицы). Неосновные переменные x
1 и x
5
равны нулю.
Значение целевой функции в этом случае равно 40 (это можно видеть в пра- вой нижней ячейке таблицы).
Доведем решение нашего примера до конца.
Вернемся к шагу 4 симплекс-алгоритма. Рассмотрим последнюю строку таблицы 2.7. В ней есть положительные элементы, значит полученное реше- ние не является оптимальным.
Шаг 5. Выберем разрешающий столбец. Им окажется столбец x
1
, по- скольку здесь содержится единственный положительный элемент нижней строки. Стало быть, переменную x
1 будем переводить в основные.
Далее. Шаг 6. Проверка показывает, что в разрешающем столбце есть положительные элементы, следовательно, можно продолжать решение.
Шаг 7. Определим разрешающую строку. При этом будем рассматри- вать лишь первую и вторую строки, поскольку для третьей строки в разре- шающем столбце находится нуль. Найдем частное от деления элемента b
i на элемент, находящийся в разрешающем столбце:
Электронный архив УГЛТУ
36
Для первой строки: D
1
= 60 / 4 = 15.
Для второй строки: D
2
= 12 / 2 = 6.
Наименьший результат деления - во второй строке, значит именно эту строку выбираем в качестве разрешающей, т.е. переводить в неосновные (ис- ключать из базиса) будем переменную x
4
Ниже приведена симплекс-таблица с выделенными разрешающей стро- кой и столбцом (табл. 2.8).
Таблица 2.8
Симплекс-таблица (второе базисное решение) с выделенными разрешающей строкой и столбцом
Базис
Переменные
b
i
x
1
x
2
x
3
x
4
x
5
x
3
4
0
1
0
-6
60
x
4
2
0
0
1
-6
12
x
2
0
1
0
0
1
10
c
j
2
0
0
0
-4
-40
Далее перейдем к шагу 8 и осуществим пересчет элементов симплексной таблицы в соответствии с правилами, приводимыми выше. Результат пере- счета представлен в таблице 2.9.
Таблица 2.9
Симплекс-таблица для задачи о хоккейных клюшках и шахматных наборах (третье базисное решение)
Базис
Переменные
b
i
x
1
x
2
x
3
x
4
x
5
x
3
0
0
1
-2
6
36
x
1
1
0
0
1/2
-3
6
x
2
0
1
0
0
1
10
c
j
0
0
0
-1
2
-52
Таким образом, в очередном (третьем) базисном решении основными переменными являются: x
1
= 6, x
2
= 10, x
3
= 36. Неосновные переменные x
4
и
x
5 равны нулю. Значение целевой функции для этого решения равно 52.
Электронный архив УГЛТУ
37
Вернемся к шагу 4 симплекс-метода. Рассмотрим последнюю строку таблицы 2.9. В ней все еще есть положительные элементы, значит, получен- ное решение не является оптимальным, и необходимо продолжить выполне- ние симплекс-алгоритма.
Шаг 5. Выберем разрешающий столбец. Им окажется столбец x
5
, по- скольку здесь содержится единственный положительный элемент нижней строки. Переменную x
5 будем переводить в основные.
Шаг 6. Проверка показывает, что в разрешающем столбце есть положи- тельные элементы, следовательно, можно продолжать решение.
Шаг 7. Определим разрешающую строку. При этом будем рассматри- вать лишь первую и третью строки, поскольку для второй строки в разреша- ющем столбце находится отрицательное число. Найдем частное от деления элемента b
i на элемент, находящийся в разрешающем столбце:
Для первой строки: D
1
= 36 / 6 = 6.
Для третьей строки: D
2
= 10 / 1 = 10.
Наименьший результат деления - в первой строке, значит именно эту строку мы выбираем в качестве разрешающей, т.е. переводить в неосновные
(исключать из базиса) будем переменную x
3
Ниже приведена симплекс-таблица с выделенными разрешающей стро- кой и столбцом (табл.2.10).
Далее перейдем к шагу 8 и осуществим пересчет элементов симплексной таблицы в соответствии с правилами, приводимыми выше. Результат пере- счета представлен в табл. 2.11.
Таблица 2.10
Симплекс-таблица (третье базисное решение) с выделенными разрешающей строкой и столбцом
Базис
Переменные
b
i
x
1
x
2
x
3
x
4
x
5
x
3
0
0
1
-2
6
36
x
1
1
0
0
1/2
-3
6
x
2
0
1
0
0
1
10
c
j
0
0
0
-1
2
-52
Таким образом, в очередном (четвертом) базисном решении основными переменными являются: x
1
= 24, x
2
= 4, x
5
= 6. Неосновные переменные x
3 и x
4 равны нулю. Значение целевой функции для этого решения равно 64.
Вернемся к шагу 4. Рассмотрим последнюю строку таблицы 2.11. Поло- жительных элементов в ней не осталось, следовательно, полученное решение является оптимальным.
Электронный архив УГЛТУ
38
Решение задачи найдено. Оно, что естественно, совпадает с решением, полученным для этой же задачи при помощи графического метода:
(
)
Таблица 2.11
Симплекс-таблица для задачи о хоккейных клюшках и шахматных наборах (четвертое базисное решение)
Базис
Переменные
b
i
x
1
x
2
x
3
x
4
x
5
x
5
0
0
1/6
-1/3
1
6
x
1
1
0
1/2
-1/2
0
24
x
2
0
1
-1/6
1/3
0
4
c
j
0
0
-1/3
-1/3
0
-64
На рисунке 2.2 приведена общая схема симплексного алгоритма, наглядно показывающая порядок его реализации.
Рис. 2.2. Общая схема симплекс-метода
Электронный архив УГЛТУ
39
2.5. Двойственность
в линейном программировании
Теория математического линейного программирования позволяет не только получать оптимальные планы с помощью эффективных вычислитель- ных процедур, но и делать ряд экономически содержательных выводов, ос- нованных на свойствах задачи, которая является двойственной по отноше- нию к исходной ЗЛП.
Пусть в качестве исходной дана задача:
( ̅)= c
1
x
1
+ c
2
x
2
+ ... + c
n
x
n
= max;
{
(2.10)
̅̅̅̅̅
Задача линейного программирования, двойственная задаче (2.10), будет иметь вид:
( ̅) = b
1
y
1
+ b
2
y
2
+ ... + b
m
y
m
→ min;
{
̅̅̅̅̅̅
(2.11)
Можно сформулировать правила получения двойственной задачи ли- нейного программирования из задачи исходной.
1. Если в исходной задаче ищется максимум целевой функции, то в двойственной ей - минимум.
2. Коэффициенты при переменных в целевой функции одной задачи яв- ляются свободными членами системы ограничений другой задачи.
3. В исходной ЗЛП все функциональные ограничения - неравенства вида
«≤ », а в задаче, двойственной ей, - неравенства вида « ≥ ».
4. Коэффициенты при переменных в системах ограничений взаимно двойственных задач описываются матрицами, транспонированными относи- тельно друг друга.
5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой.
6. Условие неотрицательности переменных сохраняется в обеих задачах.
Электронный архив УГЛТУ
40
Связь между оптимальными планами взаимно двойственных задач уста- навливают теоремы двойственности.
Теорема 1. Если одна из двойственных задач имеет конечный оптимум, то другая также имеет конечный оптимум, причем экстремальные значения целевых функций совпадают:
( ̅) ( ̅
) ( ̅) ( ̅
) (2.12)
Если целевая функция одной из двойственных задач не ограничена, то условия другой задачи противоречивы.
Теорема 2 (о дополняющей нежёсткости). Для того чтобы планы
̅
(
) ̅
(
)
являлись оптимальными решениями необходимо и достаточно, чтобы вы- полнялись следующие соотношения:
(∑
) (2.13)
(∑
) (2.14)
Таким образом, если компонент оптимального плана больше нуля, то при подстановке в соответствующее ограничение двойственной задачи опти- мального плана это ограничение обращается в верное равенство, и наобо- рот.
Теорема об оценках. Значения переменных в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов bi в системе ограничений прямой задачи на величину целевой функции
( ̅
):
( ̅
)
(2.15)
Компоненты оптимального решения двойственной задачи принято называть двойственными оценками. Часто употребляется также термин «объ- ективно обусловленные оценки».
На свойствах двойственных оценок базируется экономико- математический анализ распределения ресурсов. В пределах устойчивости двойственных оценок имеют место свойства, рассмотренные ниже.
При описании свойств двойственных оценок будем пользоваться зада- чей о хоккейных клюшках и шахматных наборах для наглядной иллюстрации рассматриваемых положений.
Электронный архив УГЛТУ
41
Формулировка прямой (исходной) задачи:
( ̅)= 2x
1
+ 4x
2
→ max;
{
x
1
≥ 0, x
2
≥ 0.
Получим двойственную задачу.
( ̅)= 120y
1
+ 72y
2
+ 10y
3
→ min;
{
y
1
≥ 0, y
2
≥ 0, y
3
≥ 0.
В результате решения получим следующие оптимальные планы:
̅
= (24, 4);
̅
= (1/3, 1/3, 0).
Легко убедиться, что при подстановке оптимальных планов в целевые функции задач оба получаемых значения равны 64.
Рассмотрим свойства двойственных оценок.
Свойство 1. Оценки как мера дефицитности ресурсов. Двойственные оценки отражают сравнительную дефицитность факторов производства. Чем выше величина оценки
, тем выше дефицитность i-го ресурса. Факторы, получившие нулевые оценки, не являются дефицитными и не ограничивают производство.
В нашем примере нулевую оценку получил третий ресурс (
= 0), по- этому он не является дефицитным, т.е., с точки зрения задачи, фонд рабочего времени на участке С не ограничивает производство. Напротив, первый (уча- сток А) и второй (участок В) ресурсы являются дефицитными, причем огра- ничивают производство в одинаковой степени (
1/3).
Последнее утверждение легко подтвердить, подставив и в ограничения исходной задачи:
{
Откуда видно, что при реализации оптимального плана фонд рабочего времени участка С, действительно, расходуется не полностью.
Свойство 2. Оценки как мера влияния ограничений на значение целевой функции. Величина двойственной оценки какого-либо ресурса показывает,
Электронный архив УГЛТУ
42 насколько возросло бы максимальное значение целевой функции, если бы объем данного ресурса увеличился на единицу. В связи с этим значение объ- ективно обусловленной оценки иногда называют теневой ценой ресурса. Те- невая цена - это стоимость единицы ресурса в оптимальном решении.
Однако нужно учитывать, что двойственные оценки позволяют измерить эффективность лишь незначительного изменения объема ресурсов. При зна- чительных изменениях может быть получен новый оптимальный план и но- вые двойственные оценки.
Для нашего примера увеличение (уменьшение) фонда времени на участ- ке А или В должно приводить к увеличению (уменьшению) максимальной прибыли на 1/3 у.е. Соответственно, например, при увеличении фонда вре- мени участка А на 12 н/часов общая прибыль должна увеличиться на 4 у.е.
(1/3·12).
Свойство 3. Оценки как инструмент определения эффективности от- дельных хозяйственных решений. С помощью двойственных оценок можно определить выгодность выпуска новых изделий, эффективность новых тех- нологических способов производства. При этом эффективным может счи- таться тот вариант производства, для которого сумма прибыли, недополу- ченной из-за отвлечения дефицитных ресурсов, будет меньше прибыли полу- чаемой. Разница между этими величинами (Δ
j
) вычисляется как
∑
̅̅̅̅̅
(2.16)
В том случае, если Δ
j
≤ 0, вариант производства является выгодным, ес- ли Δ
j
> 0 – вариант невыгоден.
Вернемся к нашему примеру. Пусть предприятие планирует выпуск нового вида изделий: бейсбольные биты. Для производства одной биты необходимо затратить 3 часа работы на участке А, 4 часа работы на участке В и 1 час работы на участке С. Прибыль, получаемая от продажи одной биты, составляет
3 у.е. Выгодно ли предприятию выпускать новую продукцию?
Для ответа на вопрос рассчитаем Δ
j по формуле (2.16):
Δ
j
= 3·
+ 4·
+ 1·
– 3 = 3·1/3 + 4·1/3 + 1·0 – 3 = -2/3,
Получается, что Δ
j
< 0, значит производить бейсбольные биты выгодно.
Свойство 4. Оценки как мера относительной заменяемости ресурсов с точки зрения конечного эффекта.
Например, отношение показывает, сколько единиц k-го ресурса может быть высвобождено при увеличении объема i-го ресурса на единицу, для того чтобы максимум целевой функции остался на прежнем уровне. Или наоборот, сколько единиц k-го ресурса необходимо дополнительно ввести
Электронный архив УГЛТУ
Переменные
b
i
x
1
x
2
... x
n
x
n+1
...
x
n+m
x
n+1
a
11
a
12
... a
1n
1 0 0
b
1
x
n+2
a
21
a
22
... a
2n
0 ... 0
b
2
...
... ... ... ... ... ... ... ...
x
n+m
a
m1
a
m2
... a
mn
0 0 1
b
m
c
j
c
1
c
2
... c
n
0 0 0
L
Таблица 2.5
Исходная симплекс-таблица для задачи о хоккейных клюшках и шахматных наборах
Базис
Переменные
b
i
x
1
x
2
x
3
x
4
x
5
x
3
4
6
1
0
0
120
x
4
2
6
0
1
0
72
x
5
0
1
0
0
1
10
c
j
2
4
0
0
0
0
В нашей задаче последняя строка содержит два положительных элемен- та, следовательно, необходимо перейти к шагу 5.
Шаг 5. Выбор разрешающего столбца (переменной, вводимой в базис).
Разрешающий столбец выбирается в соответствии со следующим условием:
Электронный архив УГЛТУ
33
{
}
̅̅̅̅̅̅̅̅̅̅̅ (2.5) где r – номер разрешающего столбца.
Таким образом, при определении разрешающего столбца просматрива- ется последняя строка симплексной таблицы и в ней отыскивается наиболь- ший положительный элемент.
В нашей задаче в качестве разрешающего выберем второй столбец (со- ответствующий переменной x
2
), поскольку в последней строке для этого столбца содержится 4.
Шаг 6. Проверка условия: все a
ir
≤ 0. Если «ДА» - целевая функция не ограничена и решения нет, если «НЕТ» - переход к шагу 7.
Таким образом, необходимо проверить элементы разрешающего столб- ца. Если среди них нет положительных, то задача неразрешима.
В нашем примере все элементы разрешающего столбца положительны
(6, 6 и 1), следовательно, необходимо перейти к шагу 7.
Шаг 7. Выбор разрешающей строки (переменной, выводимой из базиса) по условию:
{
}
̅̅̅̅̅̅
(2.6) где s - номер разрешающей строки.
Таким образом, для тех строк, где элементы разрешающего столбца по- ложительны, необходимо найти частное от деления элемента b
i
(последний столбец таблицы) на элемент, находящийся в разрешающем столбце. В каче- стве разрешающей выбирается строка, для которой результат такого деления будет наименьшим.
Проиллюстрируем выполнение шага 7, обратившись к нашему примеру.
Для первой строки: D
1
= 120 / 6 = 20.
Для второй строки: D
2
= 72 / 6 = 12.
Для третьей строки: D
3
= 10 / 1 = 10.
Наименьший результат деления - в третьей строке, значит именно эту строку мы выбираем в качестве разрешающей, т.е. исключать из базисного решения будем переменную x
5
Элемент, стоящий на пересечении разрешающей строки и разрешающе- го столбца, называется разрешающим элементом. В нашем случае таковым является единица, стоящая на пересечении третьей строки и второго столбца.
Исходная симплекс-таблица нашего примера с выделенными цветом разре- шающей строкой и разрешающим столбцом представлена ниже (табл. 2.6).
Шаг 8. Пересчет элементов симплекс-таблицы (переход к новому базис- ному решению).
Порядок пересчета различных элементов таблицы несколько отличается.
Для элементов разрешающей строки используются следующие формулы:
Электронный архив УГЛТУ
34
(2.7)
где s – номер разрешающей строки,
r – номер разрешающего столбца,
– новые значения пересчитываемых элементов,
a
sj
, b
s
– старые значения пересчитываемых элементов,
a
sr
– старое значение разрешающего элемента.
Таблица 2.6
Исходная симплекс-таблица с выделенными разрешающей строкой и столбцом, а также с иллюстрацией к применению правила прямоугольника
Таким образом, при пересчете элементов разрешающей строки каждый ее элемент делится на разрешающий элемент.
Еще проще пересчитать элементы разрешающего столбца. Все они
(кроме разрешающего элемента) становятся равными нулю:
. (2.8)
Элементы, не принадлежащие разрешающим столбцу и строке, пересчи- тываются по так называемому правилу прямоугольника: мысленно выделяет- ся прямоугольник, в котором элемент, подлежащий пересчету и разрешаю- щий элемент образуют одну из диагоналей. Формулы будут иметь следую- щий вид:
. (2.9) где
– новые значения пересчитываемых элементов,
a
ij
, b
i
, c
j
, L – старые значения пересчитываемых элементов.
Применение правила прямоугольника проиллюстрируем, используя таб- лицу 2.6. Пересчитаем элемент a
11
(в исходной симплекс-табл. 2.5 его значе-
Электронный архив УГЛТУ
35 ние равно 4). В таблице 2.6 можно видеть прямоугольник (прочерчен пунк- тиром), соединяющий четыре элемента, участвующих в пересчете:
Аналогичным образом пересчитываются остальные элементы.
По окончании пересчета осуществляется возврат к шагу 4.
Полностью результат пересчета для нашего примера можно видеть в табл. 2.7.
Таблица 2.7
Симплекс-таблица для задачи о хоккейных клюшках и шахматных наборах
(второе базисное решение)
Базис
Переменные
b
i
x
1
x
2
x
3
x
4
x
5
x
3
4
0
1
0
-6
60
x
4
2
0
0
1
-6
12
x
2
0
1
0
0
1
10
c
j
2
0
0
0
-4
-40
Таким образом, в новом базисном решении базисными переменными яв- ляются: x
2
= 10, x
3
= 60, x
5
= 12 (соответствующие значения можно видеть в последнем столбце таблицы). Неосновные переменные x
1 и x
5
равны нулю.
Значение целевой функции в этом случае равно 40 (это можно видеть в пра- вой нижней ячейке таблицы).
Доведем решение нашего примера до конца.
Вернемся к шагу 4 симплекс-алгоритма. Рассмотрим последнюю строку таблицы 2.7. В ней есть положительные элементы, значит полученное реше- ние не является оптимальным.
Шаг 5. Выберем разрешающий столбец. Им окажется столбец x
1
, по- скольку здесь содержится единственный положительный элемент нижней строки. Стало быть, переменную x
1 будем переводить в основные.
Далее. Шаг 6. Проверка показывает, что в разрешающем столбце есть положительные элементы, следовательно, можно продолжать решение.
Шаг 7. Определим разрешающую строку. При этом будем рассматри- вать лишь первую и вторую строки, поскольку для третьей строки в разре- шающем столбце находится нуль. Найдем частное от деления элемента b
i на элемент, находящийся в разрешающем столбце:
Электронный архив УГЛТУ
36
Для первой строки: D
1
= 60 / 4 = 15.
Для второй строки: D
2
= 12 / 2 = 6.
Наименьший результат деления - во второй строке, значит именно эту строку выбираем в качестве разрешающей, т.е. переводить в неосновные (ис- ключать из базиса) будем переменную x
4
Ниже приведена симплекс-таблица с выделенными разрешающей стро- кой и столбцом (табл. 2.8).
Таблица 2.8
Симплекс-таблица (второе базисное решение) с выделенными разрешающей строкой и столбцом
Базис
Переменные
b
i
x
1
x
2
x
3
x
4
x
5
x
3
4
0
1
0
-6
60
x
4
2
0
0
1
-6
12
x
2
0
1
0
0
1
10
c
j
2
0
0
0
-4
-40
Далее перейдем к шагу 8 и осуществим пересчет элементов симплексной таблицы в соответствии с правилами, приводимыми выше. Результат пере- счета представлен в таблице 2.9.
Таблица 2.9
Симплекс-таблица для задачи о хоккейных клюшках и шахматных наборах (третье базисное решение)
Базис
Переменные
b
i
x
1
x
2
x
3
x
4
x
5
x
3
0
0
1
-2
6
36
x
1
1
0
0
1/2
-3
6
x
2
0
1
0
0
1
10
c
j
0
0
0
-1
2
-52
Таким образом, в очередном (третьем) базисном решении основными переменными являются: x
1
= 6, x
2
= 10, x
3
= 36. Неосновные переменные x
4
и
x
5 равны нулю. Значение целевой функции для этого решения равно 52.
Электронный архив УГЛТУ
37
Вернемся к шагу 4 симплекс-метода. Рассмотрим последнюю строку таблицы 2.9. В ней все еще есть положительные элементы, значит, получен- ное решение не является оптимальным, и необходимо продолжить выполне- ние симплекс-алгоритма.
Шаг 5. Выберем разрешающий столбец. Им окажется столбец x
5
, по- скольку здесь содержится единственный положительный элемент нижней строки. Переменную x
5 будем переводить в основные.
Шаг 6. Проверка показывает, что в разрешающем столбце есть положи- тельные элементы, следовательно, можно продолжать решение.
Шаг 7. Определим разрешающую строку. При этом будем рассматри- вать лишь первую и третью строки, поскольку для второй строки в разреша- ющем столбце находится отрицательное число. Найдем частное от деления элемента b
i на элемент, находящийся в разрешающем столбце:
Для первой строки: D
1
= 36 / 6 = 6.
Для третьей строки: D
2
= 10 / 1 = 10.
Наименьший результат деления - в первой строке, значит именно эту строку мы выбираем в качестве разрешающей, т.е. переводить в неосновные
(исключать из базиса) будем переменную x
3
Ниже приведена симплекс-таблица с выделенными разрешающей стро- кой и столбцом (табл.2.10).
Далее перейдем к шагу 8 и осуществим пересчет элементов симплексной таблицы в соответствии с правилами, приводимыми выше. Результат пере- счета представлен в табл. 2.11.
Таблица 2.10
Симплекс-таблица (третье базисное решение) с выделенными разрешающей строкой и столбцом
Базис
Переменные
b
i
x
1
x
2
x
3
x
4
x
5
x
3
0
0
1
-2
6
36
x
1
1
0
0
1/2
-3
6
x
2
0
1
0
0
1
10
c
j
0
0
0
-1
2
-52
Таким образом, в очередном (четвертом) базисном решении основными переменными являются: x
1
= 24, x
2
= 4, x
5
= 6. Неосновные переменные x
3 и x
4 равны нулю. Значение целевой функции для этого решения равно 64.
Вернемся к шагу 4. Рассмотрим последнюю строку таблицы 2.11. Поло- жительных элементов в ней не осталось, следовательно, полученное решение является оптимальным.
Электронный архив УГЛТУ
38
Решение задачи найдено. Оно, что естественно, совпадает с решением, полученным для этой же задачи при помощи графического метода:
(
)
Таблица 2.11
Симплекс-таблица для задачи о хоккейных клюшках и шахматных наборах (четвертое базисное решение)
Базис
Переменные
b
i
x
1
x
2
x
3
x
4
x
5
x
5
0
0
1/6
-1/3
1
6
x
1
1
0
1/2
-1/2
0
24
x
2
0
1
-1/6
1/3
0
4
c
j
0
0
-1/3
-1/3
0
-64
На рисунке 2.2 приведена общая схема симплексного алгоритма, наглядно показывающая порядок его реализации.
Рис. 2.2. Общая схема симплекс-метода
Электронный архив УГЛТУ
39
2.5. Двойственность
в линейном программировании
Теория математического линейного программирования позволяет не только получать оптимальные планы с помощью эффективных вычислитель- ных процедур, но и делать ряд экономически содержательных выводов, ос- нованных на свойствах задачи, которая является двойственной по отноше- нию к исходной ЗЛП.
Пусть в качестве исходной дана задача:
( ̅)= c
1
x
1
+ c
2
x
2
+ ... + c
n
x
n
= max;
{
(2.10)
̅̅̅̅̅
Задача линейного программирования, двойственная задаче (2.10), будет иметь вид:
( ̅) = b
1
y
1
+ b
2
y
2
+ ... + b
m
y
m
→ min;
{
̅̅̅̅̅̅
(2.11)
Можно сформулировать правила получения двойственной задачи ли- нейного программирования из задачи исходной.
1. Если в исходной задаче ищется максимум целевой функции, то в двойственной ей - минимум.
2. Коэффициенты при переменных в целевой функции одной задачи яв- ляются свободными членами системы ограничений другой задачи.
3. В исходной ЗЛП все функциональные ограничения - неравенства вида
«≤ », а в задаче, двойственной ей, - неравенства вида « ≥ ».
4. Коэффициенты при переменных в системах ограничений взаимно двойственных задач описываются матрицами, транспонированными относи- тельно друг друга.
5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой.
6. Условие неотрицательности переменных сохраняется в обеих задачах.
Электронный архив УГЛТУ
40
Связь между оптимальными планами взаимно двойственных задач уста- навливают теоремы двойственности.
Теорема 1. Если одна из двойственных задач имеет конечный оптимум, то другая также имеет конечный оптимум, причем экстремальные значения целевых функций совпадают:
( ̅) ( ̅
) ( ̅) ( ̅
) (2.12)
Если целевая функция одной из двойственных задач не ограничена, то условия другой задачи противоречивы.
Теорема 2 (о дополняющей нежёсткости). Для того чтобы планы
̅
(
) ̅
(
)
являлись оптимальными решениями необходимо и достаточно, чтобы вы- полнялись следующие соотношения:
(∑
) (2.13)
(∑
) (2.14)
Таким образом, если компонент оптимального плана больше нуля, то при подстановке в соответствующее ограничение двойственной задачи опти- мального плана это ограничение обращается в верное равенство, и наобо- рот.
Теорема об оценках. Значения переменных в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов bi в системе ограничений прямой задачи на величину целевой функции
( ̅
):
( ̅
)
(2.15)
Компоненты оптимального решения двойственной задачи принято называть двойственными оценками. Часто употребляется также термин «объ- ективно обусловленные оценки».
На свойствах двойственных оценок базируется экономико- математический анализ распределения ресурсов. В пределах устойчивости двойственных оценок имеют место свойства, рассмотренные ниже.
При описании свойств двойственных оценок будем пользоваться зада- чей о хоккейных клюшках и шахматных наборах для наглядной иллюстрации рассматриваемых положений.
Электронный архив УГЛТУ
41
Формулировка прямой (исходной) задачи:
( ̅)= 2x
1
+ 4x
2
→ max;
{
x
1
≥ 0, x
2
≥ 0.
Получим двойственную задачу.
( ̅)= 120y
1
+ 72y
2
+ 10y
3
→ min;
{
y
1
≥ 0, y
2
≥ 0, y
3
≥ 0.
В результате решения получим следующие оптимальные планы:
̅
= (24, 4);
̅
= (1/3, 1/3, 0).
Легко убедиться, что при подстановке оптимальных планов в целевые функции задач оба получаемых значения равны 64.
Рассмотрим свойства двойственных оценок.
Свойство 1. Оценки как мера дефицитности ресурсов. Двойственные оценки отражают сравнительную дефицитность факторов производства. Чем выше величина оценки
, тем выше дефицитность i-го ресурса. Факторы, получившие нулевые оценки, не являются дефицитными и не ограничивают производство.
В нашем примере нулевую оценку получил третий ресурс (
= 0), по- этому он не является дефицитным, т.е., с точки зрения задачи, фонд рабочего времени на участке С не ограничивает производство. Напротив, первый (уча- сток А) и второй (участок В) ресурсы являются дефицитными, причем огра- ничивают производство в одинаковой степени (
1/3).
Последнее утверждение легко подтвердить, подставив и в ограничения исходной задачи:
{
Откуда видно, что при реализации оптимального плана фонд рабочего времени участка С, действительно, расходуется не полностью.
Свойство 2. Оценки как мера влияния ограничений на значение целевой функции. Величина двойственной оценки какого-либо ресурса показывает,
Электронный архив УГЛТУ
42 насколько возросло бы максимальное значение целевой функции, если бы объем данного ресурса увеличился на единицу. В связи с этим значение объ- ективно обусловленной оценки иногда называют теневой ценой ресурса. Те- невая цена - это стоимость единицы ресурса в оптимальном решении.
Однако нужно учитывать, что двойственные оценки позволяют измерить эффективность лишь незначительного изменения объема ресурсов. При зна- чительных изменениях может быть получен новый оптимальный план и но- вые двойственные оценки.
Для нашего примера увеличение (уменьшение) фонда времени на участ- ке А или В должно приводить к увеличению (уменьшению) максимальной прибыли на 1/3 у.е. Соответственно, например, при увеличении фонда вре- мени участка А на 12 н/часов общая прибыль должна увеличиться на 4 у.е.
(1/3·12).
Свойство 3. Оценки как инструмент определения эффективности от- дельных хозяйственных решений. С помощью двойственных оценок можно определить выгодность выпуска новых изделий, эффективность новых тех- нологических способов производства. При этом эффективным может счи- таться тот вариант производства, для которого сумма прибыли, недополу- ченной из-за отвлечения дефицитных ресурсов, будет меньше прибыли полу- чаемой. Разница между этими величинами (Δ
j
) вычисляется как
∑
̅̅̅̅̅
(2.16)
В том случае, если Δ
j
≤ 0, вариант производства является выгодным, ес- ли Δ
j
> 0 – вариант невыгоден.
Вернемся к нашему примеру. Пусть предприятие планирует выпуск нового вида изделий: бейсбольные биты. Для производства одной биты необходимо затратить 3 часа работы на участке А, 4 часа работы на участке В и 1 час работы на участке С. Прибыль, получаемая от продажи одной биты, составляет
3 у.е. Выгодно ли предприятию выпускать новую продукцию?
Для ответа на вопрос рассчитаем Δ
j по формуле (2.16):
Δ
j
= 3·
+ 4·
+ 1·
– 3 = 3·1/3 + 4·1/3 + 1·0 – 3 = -2/3,
Получается, что Δ
j
< 0, значит производить бейсбольные биты выгодно.
Свойство 4. Оценки как мера относительной заменяемости ресурсов с точки зрения конечного эффекта.
Например, отношение показывает, сколько единиц k-го ресурса может быть высвобождено при увеличении объема i-го ресурса на единицу, для того чтобы максимум целевой функции остался на прежнем уровне. Или наоборот, сколько единиц k-го ресурса необходимо дополнительно ввести
Электронный архив УГЛТУ