Аналогично
*2 + z2x3 + 22Х4 = 3 2 (пРоизв°Дя1Чая *УстРока) записывается в виде
v(0+i)v(0+Ata=(3+2-)-
Следовательно, в данном случае отсечение имеет вид
--х --х + - <0 22*3 22 4 + 2
Любое из трех отсечений может быть использовано на первой итерации метода отсекающих плоскостей. Поэтому нет необходимости строить все три отсечения перед выбором одного из них.
Выбирая (произвольно) отсечение, порожденное х2-строкой, записываем его следующим образом.
~г\ХЪ~22ХА + $\=~2 51 ~° (отсечение
Это ограничение добавляется в качестве дополнительного в оптимальную симплекс-таблицу задачи.
Базис | | | | | | Решение |
| | | 63/22 | 31/22 | | 66,5 |
| | | 7/22 | 1/22 | | |
| | | -1/22 | 3/22 | | |
«1 | | | -7/22 | -1/22 | | -0,5 |
Таблица представляет оптимальное, но недопустимое решение. Для восстановления допустимости решения применим двойственный симплекс-метод (см. раздел 4.4), что приведет к следующей симплекс-таблице.
Из-за дробных значений переменных х, и х3 последнее решение все еще нецелочисленное. Выберем хустроку в качестве производящей, т.е.
vKh+(-+fh=K)-
Соответствующее отсечение имеет вид
~4xa~7s,+s2=~i s2~° (отсечение2).
Присоединяя отсечение 2 к последней симплекс-таблице, получаем следующее.
базис | | | | | | | Решение |
| | | | | | | |
| | | | | | | |
| | | | | -1,7 | | |
| | | | | -22/7 | | |
| | | | -1/7 | -6/7 | | -4/7 |
Применение двойственного таблице. | симплекс-метода | приводит к | следующей | симплекс- |
Базис | | | | | | | Решение |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
Оптимальное решение (jc, = 4, хг = 3, г - 58), определяемое последней симплекс-таблицей, является целочисленным. То, что все элементы данной симплекс-таблицы являются целочисленными, не случайность. Это типичное явление при использовании дробных отсечений.
Важно подчеркнуть, что применение дробного отсечения предполагает целочис-ленность всех переменных, включая дополнительные. Это значит, что данный метод применим только к решению полностью целочисленных задач.
Важность этого продемонстрируем на следующем примере. Рассмотрим ограничение
1 13
х. +-х2 <-,
1 3 2 2
jc,, хг> О и целые.
С точки зрения решения соответствующей задачи ЦЛП это ограничение преобразуется в уравнение путем введения неотрицательной дополнительной переменной s,, т.е.
1 13
1 3 - 1 2
Применение дробного отсечения предполагает, что ограничение имеет допустимое целочисленное решение по всем переменным, т.е. xv хг и s,. Рассмотрев это уравнение, можем сказать, что оно может иметь допустимое целочисленное решение переменных хх и х2 лишь в том случае, если переменная s, принимает нецелочисленные значения. Следовательно, применение дробного отсечения приведет к недопустимому целочисленному решению, так как все переменные xlt х2 и s, не могут одновременно быть целочисленными. Тем не менее ограничение имеет допустимые целочисленные решения для рассматриваемых переменных лг, и х2.
Есть две возможности исправить эту ситуацию.
1. Можно умножить все ограничения на соответствующую константу для устранения дробей. Например, приведенное выше ограничение умножается на 6, что приводит к неравенству 6л:1 + 2х2 < 39. Любое целочисленное решение переменных х, и х2 автоматически дает целочисленное значение дополнительной переменной. Однако этот тип преобразования применим лишь для простых ограничений, так как значения необходимых целочисленных коэффициентов в некоторых случаях могут быть чрезвычайно большими.
2. Можно использовать специальные отсечения, именуемые частично-целочисленными. Они ориентированы на решение задач, в которых лишь часть переменных должна принимать целочисленные значения, а остальные (включая дополнительные) остаются непрерывными. Детальное изложение таких отсечений в этой главе не рассматривается (см. [3]).
УПРАЖНЕНИЯ 9.2.3
1. В примере 9.2.2 покажите графически, может ли каждое из следующих ограничений служить в качестве правильного отсечения.
a) xt + 2х2 < 10.
b) 2х, + х2<10.
c) Зх2<10.
d) Зх1+х2<15.
2. В примере 9.2.2 покажите графически, как следующие два правильных отсечения могут привести к оптимальному целочисленному решению.
Отсечение I. х, + 2х2 < 10.
Отсечение II. Зхх + х2 < 15.
3. Запишите отсечения I и II в примере 9.2.2 через уравнения для переменных х, и х2 и покажите, что они совпадают с отсечениями, которые графически показаны на рис. 9.12.
4. Покажите, что дробное отсечение не приводит к допустимому решению в приведенной ниже задаче, если не устранены все дроби в ограничении.
Максимизировать z = хх + 2х2
при ограничениях
1 13
X. + -Х, <-,
1 2 - 4 х,, х2 > 0 и целые.
5. Решите следующие задачи методом отсекающих плоскостей и сравните оптимальное целочисленное решение с решением, полученным путем округления соответствующего оптимального непрерывного решения.
а) Максимизировать г = 4х, + 6х2 + 2хъ
при ограничениях
4х, - 4х2 < 5,
-х, + 6х2< 5,
-х, + х2 + х3< 5,
х,, х2, х3> 0 и целые.