XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 9
Текст из файла (страница 9)
Заметим, 'что анализ влияния процесса сокрашения запасов дефицитного йесурса на оптимальное решение часто проводится на прак:тике, если возможна недопоставка дефицитного ресурса. Но сокращение запаса дефицитного ресурса не может улучшить (в пмысле значения целевой функции) оптимальное решение. По!лепим сказанное примером. Пример 2.3.
Вернемся к задаче линейного программиро1вания, рассмотренной в примерах 2.1 и 2.2. В изначальной остановке, отраженной в математической модели (2.2), объпотребления первого дефицитного ресурса (исходный про~к1укт А) ограничен величиной 6! —— 6. На рис. 2.2 видно, что ч!ри увеличении запа~а 6, этого дефицитного ресурса прямая, О1х1+гхз=я О» Рис. г.з Рис. г.г 13-— 38 3 7 — б 3' 38 18 — — 4 3 12 — 8 3 68 г. основы ливвйного врогрлммировлния определяемая уравнением х1+2хз — — 6м начинает перемещаться параллельна самой себе.
До момента ее прохождения через точку Г при 61 — — 7 этому процессу соответствуют перемещение оптимальной вершины С вдоль прямой, заданной уравнением 2х1+ хз = 8, в направлении точки Е и увеличение прибыли 1значения целевой функции) при оптимальном решении. При 61 > 7 анализируемый ресурс уже не является дефицитным и дальнейшее увеличение его запаса теряет смысл. Заметим, что т при 61 = 7 оптимальное решение Х' = (3 2) соответствует значению целевой функции 7" = 13 и наряду с уже имеющимся активным ограничением 2х1+ хэ < 8 появляется еще одно активное ограничение: хз < 2.
Аналогичный анализ может быть проведен и по отношению ко второму дефицитному ресурсу 1исходный продукт В), объем потребления которого ограничен величиной 6з = 8. На рис. 2.3 видно, что увеличение запаса 6з исходного продукта В имеет смысл до величины 6з = 12, при котором оптимальное решение Х* = (б О) соответствует значению целевой функции 7'" = 18. При наличии ограничений на затраты, связанные с созданием дополнительных запасов исходных продуктов А и В, „лицу, принимающему решения", важно знать, какому ресур- су следует отдать предпочтение. Для этих целей используют дополнительную характеристику 1-го дефицитного ресурса— ценностпь дополнитпельноб единицы 1-го ресурса, которая определяется как отношение максимального приращения целевой функции к максимально допустимому приращению объема 1-го ресурса.
В рассматриваемом случае ценность дополнительной единицы первого ресурса (продукта А) а второго ресурса 1продукта В) Полученные результаты свидетельствуют о том, что при нали- чии средств дополнительные вложения в первую очередь следу- -ет направить на увеличение объема продукта В, а лишь затем на увеличение объема продукта А. (2.7) а;ях1 < 61, (2.5) пряха > 6; 1=1 1Ч Е асЯУл — 1л! асяХ1 — у = 6Ь 1=1 1=1,Ь, (2.6) 60 2. ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Завершая решение задачи об определении оптимальных объемов производства различных видов лака, рассмотрим вопрос о влиянии на оптимальное решение правой части неактивного ограничения хз < 2.
Это ограничение отражает предельный уровень спроса на лак для наружных работ. Проанализировав рис. 2.1, можно утверждать, что при неизменности остальных ограничений, входящих в математическую модель (2.2), уменьшение спроса на лак для наружных работ до величины 4/3 не т может влиягь на оптимальное решение Х* = (10/3 4/3) (см. пример 2.2).
2.2. Формы записи задач линейного программирования В дальнейших рассуждениях будем говорить, что эадана линейного программирования представлена в стпандартпной форме, если она имеет следующий вид: 1и 7яуе -+ шах; Е=! л! Е агяуя=А, 1=1,~; Ям1 у, >0, 6=1,А', где система линейных алгебраических уравнений определяющая множество Я допустпимых ре1иеинй, является баэисной, т.е. число уравнений этой системы равно рангу ее матрицы.
Таким образом, в (2.5) имеем Ь < А'. А так как при Ь = Х система (2.6) имеет единственное решение и множество 2.2. Формы записи задач линейного программирование 61 Я не может содержать больше одного элемента, то в общем случае можно считать, что Сравнивая задачи (2.1) и (2.5), видим, что любая задача линейного программирования может быть представлена в стандартной форме, если все ограничения типа неравенства, за исключением ограничений на знаки переменных модели, записать в виде равенств.
Ограничение типа неравенства можно записать как ограничение типа равенства путем введения нового неотрицательного переменного. Если ограничение типа неравенства имеет вид то с помощью дополнительного переменного у > 0 его можно записать в виде ад,х1+ у = 66 Е 1=1 Аналогично ограничение вида можно записать следующим образом: Для обоснования высказанного утверждения обратимся к математической модели (2.1) и проведем ее анализ, начав с системы ограничений, определяющих множество допустимых решений С. у„+; —— 6; — ~1 аслуь > О.
Ьм» уг + ул = 2, (2.8) Если же»' Е 1з, то у„+, — ~~» а»луь — 6, > О. и = 1,а; к=в+»; /с>в, Йфв+»; асяс есса— О, если»61г тоД=6;и если»61з, то Д= — 6; и Й=1,в; и= и+»; Й >»», й ~ »»+». 1с О, » = 1, 1,. х» 11» 13= хсъ Ръ х„+» Л» ' с 'сг= сю Й=1,и; О, и= в+1, Х. 62 2. ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Пусть для определенности в (2.1) 1» = »1, 2, -, п»г) 1з = (»в +1 +2,, и» ), 1 =(и» «-1, га «-2, ..., »»»).
Полагаем ую =хм к = 1, и. Если» 6 1», то вводим новое у»сравдлез»ое ' »»еред»екиое: ь=» Таким образом, г1= в+п»г в (2.5). Если» 6 1», то Д = 6; и Если среди ограничений в (2.1) нет линейно зависимых, то 1 = »а. Если в (2.1) целевая функцию минимизируется, то если в (2.1) целевая функция максимизируется, то 2.2. Формы записи задач аииейиого программироааииа 63 Пример 2.4.
Чтобы задачу линейного программирования (2.2), рассмотренную в примерах 2.1 — 2.3, представить в стандартной форме, полагаем у» — — х», уг = хг, уз — — 6 — х» ~хг, уд — — 8 — 2х» — хг, ул = 2 — хг. В этом случае получаем Зу»+2уг -+ шах; у»+2уг+уз — — 6, 2у»+уз+у»=8, ую>О, Й=1,5. Таким образом, »ч' = 5 и Ь = 3, в чем нетрудно убедиться.
Заметим, что исходная задача (2,2) может быть решена гео- метрическим методом, а для ее записи в стандартной форме верно равенство Х вЂ” Ь = 2. Понятно, что задача (2.5) — это частный случай задачи линейного программирования вида (2.1), в котором нет ограничений типа неравенства. Но иногда удобно сделать наоборот: ограничения типа равенства преобразовать в неравенства. Рассмотрим приемы такого преобразования на примере задачи (2.5) линейного программирования в стандартной форме. В задаче (2.5) система линейных алгебраических уравнений („. 2.6) является базисной, в этой системе Х вЂ” 1, неизвестных являются свободными, а Ь вЂ” бззисными [ПЦ.
Обозначим свободные неизвестные (свободные переменные) через х», ..., х„, где»» = Ж вЂ” 1,, а базисные — через ха+„..., хи. Запишем систему (2.6) в следующем виде: ока+»ха+с+... +»»;мхк = /у; — ес;»х, ... а»„х„ Вводя матричные обозначения бг В,Х, =,В - В2Х2. Х1 = В1 В2Х2+ В1 Д, У1 = 2 — уз+ 2ув, У2 = 2 — ув, У4 = 2+ 2уз — Зув.
х„ч., — — ~~ д1ьхь+д;, 1= 1, Ь, в=1 (2.9) 2 — уз+ 2ув > О, 2 — ув > О, 2+2уз — Зув > О. ~~) драХЬ+д, > О, 1= 1, Ь, в=1 64 2. ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ приходим к следующему представлению системы линейных ал- гебраических уравнений: Так как матрица В, является квадратной порядка Ь и невырождена (она соответствует базисному минору матрицы системы), то имеет обратную матрицу В 1.
Поэтому что можно записать следующим образом: где ды — элементы матрицы — В В2, а д; — элементы матрицы-столбца В, ~~3. Возвращаясь к задаче (2.5), заметим, что ограничения типа равенства в системе (2.6) можно заменить эквивалентными ограничениями типа неравенства. Так как х„+, > О, 1= 1, Ь, то из (2,9) следует, что Итак, для перехода от задачи (2.5) к задаче (2.1) нужно разделить переменные на базисные и свободные, выразить базисные переменные через свободные, а затем исключить базисные переменные как из целевой д1уикции, так и из ограничений, заменив последние неравенствами, означающими, что исключаемые переменные неотрицательны. В целевой функции прн этом может появиться постоянное слагаемое, которое можно отбросить как не оказывающее влияния на положение точки экстремума.
2.2. Формы записи задач лииейиого программирования Напомним, что выбор базисных и свободных переменных в общем случае не является однозначным 1П1). Поэтому не является однозначным и переход от (2.5) к (2.1). Пример 2.5. Три уравнения в системе ограничений задачи (2.8) являются базисными, так как ранг матрицы, составленной из коэффициентов при неизвестных, равен трем. В качестве базисных переменных можно выбрать У1, У2 и У4 (этим переменным соответствует базисный минор матрицы). Разрешая исходную систему относительно базисных переменных, полу- чаем Учитывал неотрицательность переменных У1, У2 и у4, запишем ограничения в виде неравенств: Из целевой функции ЗУ1 + 2У2 исключим базисные переменные: ЗУ1+2У2 = З(2 — уз+ 2ув) + 2(2 — ув) = 6 — Зуз+4ув.
Целевую функцию 6 — Зуз+ 4ув можно заменить целевой функцией — Зуз+ 4ув, так как максимум первой функции достигается при тех же значениях переменных, что и максимум второй. В результате приходим к следующей задаче линейного программирован ня: Зуз+4ув -+ 1пах; Уз — 2ув < 2, ув < 2, — 2уз+Зуь < 2, Уз > О, ув > О. ул = ЗУ1 — 2уг + 1, (2.10) Уз = — У1 + Уг + 4 1У вЂ” Ь= 2, 1=1,Ь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
