назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [ 25 ] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]


25

Учитывая свойство оптимального решения, которое заключается в том, что оно может быть представлено как выпуклая комбинация базисных решений, получим, принимая за базисные решения:

X, =(3;5;0;0;9), Хс =(6;2;0;9;0)

Х=аХ, +(1-а)Х2 ;0<а< 1.

3.7. Неограниченность целевой функции

Если система ограничений в задаче линейного программирования непротиворечива, то применение конечного числа итераций симплекс-метода приводит либо к получению решения задачи (может быть неединственного) либо к установлению факта неограниченно-целевой функции.

Рассмотрим следующую задачу линейного программирования. Решить задачу минимизации линейной целевой функции:

F = 2Xj-3x2+l-при ограничениях:

2х-х>\ х,>0

Рассмотрим геометрическое решение этой задачи.

,F=-6

(3.33)

(3.34) (3.35) (3.36) (3.37)

12 3 4 5 6

Рис. 3.4

Из рис. 3.4 видно, что если перемещать линию уровня в направлении, противоположном вектору q (в направлении убывания), то она всегда

будет пересекать множество допустимых решений и, следовательно, це-



левая функция не ограниченна на множестве заданном ограничениями (З.ЗЗН3.37).

Если эту задачу решать симплексным методом, то на очередном шаге решения задачи получаем: основные переменные х, х, х. неосновные

переменные х, дс.

5 1 1

X, = - + -х, -\--Хл 1 3 3 3 3 4

7 2 1

2 = 3 + 33-34 Х5 =4 + Хз -Х4;

F= ~--~Хз +-Х4С, минимум не достигнут: переменная х имеет от-

X = (5/3; 7/3; 0; 0; 4) - базисное решение;

1 2 4

----Хо + -.

3 3 5

рицательный коэффициент в выражении для F, Определяем х3 = min( 00,00,00) = 00, следовательно, уравнения не ограничивают рост

хз и, следовательно, оптимальное значение функции F не ограниченно и

отрицательно, т.е. Fmm = -qo . Из рассмотренного примера видно, что если на каком либо шаге получаем во всех уравнениях системы бесконечные оценочные отношения переменной, которая переводится в основные, то задача не имеет конечного оптимума (Fmax= , если задача на максимум и Fmin = -00, если задача на минимум).

Можно сделать следующий вывод. Если система ограничений непротиворечива, то выполнение конечного плана шагов симплексного метода либо приводит к нахождению оптимального решения задачи (возможно неединственного), либо к установлению того факта, что целевая функция не имеет конечного оптимума.



Глава 4

ДВОЙСТВЕННЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Каждой задаче линейного программирования можно поставить в соответствие так называемую двойственную или сопряженную задачу по отношению к исходной. Аппарат теории двойственности может быть эффективно использован для проведения качественных исследований свойств задачи линейного программирования.

4.1. Двойственная задача для стандартной и канонической задачи линейного программирования

Каждой задаче линейного программирования на максимум может бьпъ поставлена в соответствие задача линейного программирования на минимум, получаемая из исходной путем определенных преобразований. Эти задачи называются симметричными или взаимно-двойственными.

Рассмотрим частный вид задачи выбора оптимально производственной программы, представленной в гл. 1.

Пусть предприятие № 1 имеет запасы материально-сырьевых ресурсов в объемах bf (/ = 1,...,т), где

т - число видов ресурсов. Как и раньше будем считать, что aj - это

объем материально-сырьевых ресурсов вида /, необходимых для выпуска одной единицы продукции вида j, Cj - прибыль от выпуска и реализации единицы продукции вида j {j =!,.;.,«).

Далее будем считать, что предприятие № 2 решило купить все материально-сырьевые ресурсы у предприятия № 1 по некоторым оптимальным ценам на эти ресурсы, которые обозначим как у\,..,Ут • Естественно, что предприятие №2 заинтересовано в том, чтобы затраты на приобретение материально-сырьевых ресурсов были минимальными, т.е.

Z = Ь,у, + Z)2>2 + + КУш ™п.

С другой стороны, предприятие № 1, которое продает материально-сырьевые ресурсы (далее их будем называть ресурсы), заинтересовано в

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [ 25 ] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]