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


[Старт] [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] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]


27

3.1. Стандартная форма задачи ЛП

5. Покажите, как следующую целевую функцию можно записать в стандартной форме задачи ЛП.

Минимизировать z = maxflx, - х2 + Зх3\, \-хх + Зх2 - х3\},

хх, х2, х3>0.

6. Покажите, что т равенств вида

Y,a„x,=b,- = 1.2,...,ш,

7 = 1

эквивалентны следующим т + 1 неравенствам.

ai]Xj<b„ / = 1,2,...,т,

7 = 1

II f III \ III

3.1.2. Свободная переменная

Во всех примерах задач ЛП главы 2 условие неотрицательности переменных является естественным. Но, конечно, возможны ситуации, когда переменные могут принимать любые действительные значения. Такая ситуация показана в следующем примере.

Пример 3.1.1

Ресторан быстрого обслуживания McBurger торгует порционными мясными пирогами и чизбургерами. На порцию мясного пирога идет четверть фунта мяса, а на чизбургер - только 0,2 фунта. В начале рабочего дня в ресторане имеется 200 фунтов мяса, можно еще прикупить мясо в течение дня, но уже с наценкой в 25 центов. Мясо, оставшееся в конце рабочего дня, жертвуется благотворительной организации. Ресторан получает доход 20 центов от одной порции мясного пирога и 15 центов - от одного чизбургера. Как и многие другие, этот ресторан не может продать в день более 900 бутербродов. Какова должна быть доля каждого блюда (т.е. сколько порций мясного пирога и сколько чизбургеров) в ежедневном производстве ресторана, чтобы максимизировать его доход?

Сначала рассмотрим ограничения. Обозначим через х, и х2 соответственно количество порций мясного пирога и чизбургеров, производимых рестораном. Для их производства ресторан может либо ограничиться 200 фунтами мяса, либо прикупить еще. В первом случае получаем ограничение в виде неравенства 0,25х, + 0,2х, < 200, а во втором- 0,25д, + 0,2д:2 > 200. Естественно, выбор одного из этих неравенств будет существенно влиять на возможное оптимальное решение. Так как мы не знаем, какое из них необходимо, логично заменить их одним равенством 0,25 + 0,2х2 + х3 = 200, гдех3 - свободная переменная. Фактически свободная переменная х3 в данной ситуации одновременно играет роли как остаточной, так и избыточной переменной.

Далее построим целевую функцию. Ресторан хочет максимизировать свой доход. Очевидно, что для максимизации дохода желательно как можно больше продавать своей продукции, но для этого необходимы дополнительные закупки мяса. В этом случае переменная х3 должна быть отрицательной, т.е. должна играть роль избыточной переменной.



Для того чтобы раскрыть "двойственную" природу переменной х3, используем стандартный математический прием, т.е. представим ее в следующем виде.

х3 = х*3 - х3 , где .г, , л-, > 0.

Если л* > 0 и л3 = 0, то переменная .v3 играет роль остаточной. Если, напротив, х} > О и xl = 0, то переменная х3 выступает в роли избыточной. (Теория задач ЛП гласит, что переменные х*3 и .v3~ не могут одновременно принимать положительные значения.) Итак, теперь ограничение можно записать в виде равенства

0,25л-, +0,2х2 + х; - х~ = 200. Целевая функция получает следующее выражение.

Максимизировать z = 0,20 + 0, [5х2 - 0,25 х}

УПРАЖНЕНИЯ 3.1.2

1. В некотором машинном центре производятся два изделия, причем на производство одной единицы первого изделия затрачивается 10 минут рабочего времени, а на единицу второго изделия - 12 минут. Рабочее время машинного центра ограничено 2500 минут в день (некоторые операции центр может выполнять параллельно); возможно превышение этой величины, но каждая дополнительная минута работы машинного центра стоит 50 центов. В рабочий день допустимо производить от 150 до 200 единиц первого изделия, но не более 45 единиц второго.

a) Предполагая, что доход от единицы первого изделия составляет 6,00 долл., а второго - 7,50 долл., постройте модель и найдите оптимальное соотношение между объемами производства изделий, максимизирующее общий доход, а также дополнительное время работы машинного центра.

b) Если стоимость дополнительного времени работы машинного центра увеличится до 1,50 долл., будет ли компания использовать это время?

2. Фирма производит три вида изделий, прибыль от которых составляет соответственно 2, 5 и 3 долл. на единицу изделия. Для производства этих изделий фирма располагает 80 рабочими часами ручного труда и 65 часами машинного времени. Для производства одной единицы изделия каждого из трех видов требуется 2, 1 и 2 часа ручного труда и 1, 1 и 2 часов машинного времени соответственно. При необходимости фирма может увеличить количество рабочих часов ручного труда и количество часов машинного времени, но каждый дополнительный час ручного труда будет стоить 15, а машинного - 10 долл.

Сформулируйте задачу линейного программирования и найдите ее оптимальное решение с помощью программы TORA.

3. В задачах ЛП, где есть несколько свободных переменных, преобразование типа *;=.v*-.v~, х*, Xj>0, удваивает соответствующее число неотрицательных переменных. Но при использовании подстановок х =xj-w, xj,w>0

можно к свободных переменных заменить на ft + 1 неотрицательных. Используя программу TORA, покажите, что эти два метода приводят к одному и тому же решению следующей задачи ЛП.

Максимизировать z = -2х, + Зх2 - 2х3



при ограничениях

4х, - х2 - 5х3 = 10,

2х, + Зл:2 + 2л:з= 12,

л:, > 0, х2, хъ - свободные переменные.

3.2. ПЕРЕХОД ОТ ГРАФИЧЕСКОГО РЕШЕНИЯ К АЛГЕБРАИЧЕСКОМУ

Идеи, лежащие в основе графического метода решения задач линейного программирования, также являются основой и алгебраического симплекс-метода. На рис. 3.1 показаны параллели между этими двумя методами. В графическом методе пространство решений определяется как пересечение полупространств, порождаемых ограничениями. В симплекс-методе пространство решений задают система из т линейных уравнений и п неотрицательных переменных. Вы должны понимать различие между этими методами, как показано на рис. 3.1 и как будет пояснено на материале этого раздела.

Графический метод

Алгебраический метод

Графическое представление всех ограничений, включая условие неотрицательности

Пространство решений состоит из бесконечного количества допустимых точек

Определяются допустимые угловые точки пространства решений

Кандидатами на оптимальное решение будут конечное число угловых точек

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

Задание пространства решений посредством системы из т линейных уравнений с п неотрицательными переменными, т<п

Задача имеет бесконечное количество допустимых решений

Находятся допустимые базисные решения системы уравнений

Кандидатами на оптимальное решение будут конечное число базисных допустимых решений

Целевая функция используется для определения оптимального базисного допустимого решения среди всех кандидатов

Рис. 3.1. Переход от графического решения к алгебраическому

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

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

[Старт] [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] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]