|
худшее решение (по значению целевой функции) определяет оценку сверху исходной задачи. Для нашего примера имеем две задачи о ранце Задача 1. шах (10х + 8 x2 + 6 x3 + 7 x4 ) 6 x1 + 3 X2 = 2 хз + 5 X4 < 1 1 Ее решение XI = х2 = х3 = 1, Х4 = 0; 9 1 = 24 Задача 2. шах (10х + 8 x2 + 6 x3 + 7 x4 ) 3 X1 + 5 X2 = 6 X3 + Х4 < 11 Ее решение XI = хг = Х4 = 1, Хз = 0; ф! = 25. Таким образом, оценка сверху оптимального решения исходной задачи в данном случае равна 24, что больше чем оценка 21, полученная методом сетевого программирования. Более того, поскольку обе рассмотренные задачи о ранце получаются в методе сетевого программирования (первая при Бп = с» $ 2 = 0 , а вторая, наоборот, при = с\, Бц = 0 ), то можно утверждать, что применение метода сетевого программирования дает лучшие (или такие же) оценки. Согласно второму способу решается задача линейного программирования без требования целочисленности. Рассмотрим простой Пример. Определить значения х» = {0; 1}, ¡= 1,2 максимизирующие функцию <р(х) = 42x1 + 14х2 при ограничениях 3 x1 + 4х2 < 6 5x1 + 2 x2 < 6 Получим оценку методом сетевого программирования. Для этого достаточно положить Бп = 42, Бг14, б1 2 = $22 =0. Решение первой оценочной задачи XI = 1, Х2 = 0, ф! = 42 является допустимым для второй задачи и, следовательно, оптимально. Получим оценку, решая нецелочисленную задачу линейного программирования. Ее решение Х= 6/7;хг = 6 /^»Фо = 48 > 42. Как видим, оценка существенно хуже. 55 |
Таким образом, оценка сверху оптимального решения исходной задачи в данном случае равна 24, что больше чем оценка 21, полученная методом сетевого программирования. Более того, поскольку обе рассмотренные задачи о ранце получаются в методе сетевого программирования (первая —при si( = q, Si2= 0, а вторая, наоборот, при Si2= с,, Sn = 0), то можно утверждать, что применение метода сетевого программирования дает лучшие (или такие же) оценки. Согласно второму способу решается задача линейного программирования без требования целочисленности. Рассмотрим простой Пример. Определить значения Xj = {0; 1}, i = 1, 2 максимизирующие функцию (p(x) = 42xj + 14x2 при ограничениях 3xi + 4х2 <6 5 x j + 2 х г —6 Получим оценку методом сетевого программирования. Для этого достаточно положить Sn = 42, S2= 14, s12= S22“ 0. Решение первой оценочной задачи Xi —1, Х2= 0, ф( = 42 является допустимым для второй задачи и, следовательно, оптимально. Получим оценку, решая нецелочисленную задачу линейного программирования. Ее решение xi=6/7;xz = 6/7;(p0= 4 8 > 4 2 . Как видим, оценка существенно хуже. ♦ 98 |