XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 20
Текст из файла (страница 20)
3.1. Докажите, что любая точка ограниченного выпуклого замкнутого множества может быть представлена в виде выпуклой комбинации его крайних точек. 3.2. Пусть в (3.20) для всех г = 1, Ь имеет место иеравенство (А ~а,); < О. Докажите, что в этом случае оптимальное решение 1'* задачи линейного программирования (2.11) ие ограничено. 3.3. Может ли количество положительных базисных переменных превышать Ь на итерации симплекс-метода, если решается задача линейного программирования (2.11)? Ответ аргументируйте. 3.4.
Возможны ли ситуации, при которых ведущий элемент симплекс-таблицы равен нулю илн является отрицательным? 3.5, Можно ли утверждать, что если текущей итерации симплекс-метода соответствует вырожденное допустимое базисное решение, то и на следующей итерации будет получено вырожденное допустимое базисное решение? 3 6 Пусть значение целевои функции р < 0 соответству ет оптимальному решению вспомогательной задачи линейного программирования (3.25). Что означает этот результат для исходной задачи линейного программирования (3.24)? 3.7.
Докажите, что ограничениям типа равенства в исходной задаче линейного программирования соответствуют переменные двойственной задачи, которые не ограничены в знаке. 3.8. Докажите, что если в исходной задаче линейного про. граммирования есть переменные, которые не ограничены в знаке, то в двойственной задаче им соответствуют ограничения типа равенства. 3. СИМПЛЕКС-МЕТОД 144 Вопросы и задачи 145 хг >9, хг >О; У(хм хг) = 11Х1+ 44хг -+ шах Ответ: Таблица З.Ц 3.9. Может ли двойственная задача линейного программирования иметь допустимое решение, если оптимальное решение соответствующей ей прямой задачи не ограничено? 3.10. Воспользовавшись симплекс-методом, найдите решения следующих задач линейного программирования: /(хг,хг,хз) = Зхг+бхг+2хз-+ шах; а) Зх, — 4хг+хз < 2, х1+ Зхг+2хз < 1, хь>0, я=1,3; /(х„хг,хз) = 2х, — 2хг+4хз — + ппп; б) — хг+ 4хз > 1> — хг+ 2хг+ Зхз ( 9, — х1+ 5хз < 1, хь > О, Й = 1, 3.
Ответ: а) Х'=(2/5 1/5 0); б) Х = (О 1/5 3/10) . 3.11. Из фиксированного набора продуктов необходимо составить пищевой рацион, обладающий минимальной ценой и содержащий по крайней мере 20 единиц белков, 30 единиц углеводов, 10 единиц жиров и 40 единиц витаминов. Количество единиц белков, жиров, углеводов и витаминов в 1 кг (в 1 л) каждого вида продукта и его цена указаны в табл.
3.14. Проведите анализ задачи на чувствительность. О т вет: цена — 150 (денежных единиц), состав — 5/6 кг рыбы, 5 кг фруктов, 4/3 л молока. 3.12. Найдите решения следующих задач линейного программирования: У(хы хг, хз) = — ЗХ1 — 4хг — 5хз -+ т!п; а) х~+хг+хз>4, 2х,+Зх +4х <О, хь >О, й=1,3; /(хм хг) = х ~ + хг + ш1п. б) 7хг + 8хг > 56, хг -1- 2хг < 6, /(хг хг хз) = 8х1+ 19хг+ 7хз — + шах. в) хг+Зхг+Зхз (50, Зх1+4хг+хз < 25 хь>0, 3=1,3.
О т в е т: а) С = Я; б) С = Я; в) Х* = (О 25/9 125/9) . 3.13. Запишите двойственную задачу линейного программирования для следующей задачи: Зхг+5хг ~(18, хг+9хг < 30, 2х +7Х (27, х1 > О, хг > О. а(Х1 гг1хз) = 18Х1+ЗОгг+27хз — ~ пйп; Зх1 + хг+ 2хз ~ )11, 5гг + Огг + 7гз > 44, гь > О, й = 1, 3, 3. 14 Фабрика производит три вида продукции для п изводства единицы продукции типа А требуются три единицы сырья о и единица сырья 17 Для производства единицы прод к у ции типа В требуются четыре единицы сырья о н три единицы з. СИМПЛЕКС-МЕТОД сырья д,' а для производства единицы продукции типа С— одна единица сырья о и две единицы сырья,З. Производство единицы продукции типа А приносит прибыль в 3 денежные единицы, типа  — в 6 денежных единиц и типа С вЂ” в 2 денежные единицы.
Определите: а) оптимальный план производства продукции, максимизируюший суммарную прибыль, если в наличии имеются 20 единиц сырья о и 10 единиц сырья д; б) обоснованную цену за возможную поставку еше одной единицы сырья о (или ф). Ответ: а) произвести 4 единицы продукции типа А и 2 единицы продукции типа В, а продукцию типа С не производить; б) за поставку единицы сырья о платить 0,6 денежных единиц (для,3 — 1,2 денежных единиц).
3.15. С помощью симплекс-метода найдите решение следующей задачи линейного программирования: — х1+ 4хз — бхз+ 18х4 -+ ппп; — х1+1,5хз+х4 д 1, хз — 5хз+4х4 > 3, хь >О, й=1,4. С помощью симплекс-метода найдите решение двойственной задачи и сопоставьте полученные результаты. От нет: Х* = (О 0 1~11 19~22), Я" = (6 3) . 3.16. Задачу линейного программирования х, + 2хг+ хз+ 8х4 -+ п1ах; х1+ 4хя — Зхз — 4х4 ( — 1, 2х1+ Зхз+ хз — 2хл > 3, хя >О, 1=1,4, решите симплекс-методом, а двойственную ей задачу решите геометрическим методом. Сопоставьте полученные результаты. Ответ: Х'= (2 0 1 0), х* = (3~5 4/5) . 4. ЦБЛО'4ИСЛБННОБ ПРОГРАММИРОВАНИБ Обшал постановка задачи целочислеккого проераммировакил отличается от общей постановки задачи линейного программирования лишь наличием дополнительного ограничения.
Этим ограничением является пяребовакке келочислеккос|пи, в соответствии с которым значения всех или части переменных модели в оптимальном решекки являются целыми неотрицательными числами, т.е. принадлежат множеству 1ч О (О). При этом если требование целочисленности распространяется на все переменные, то задачу целочисленного программирования называют полкоспзью целочислеккоб эодачеб.
Если же требование целочисленности относится лишь к части переменных, то задачу называют чоспзичко целочислеккой. Задачу линейного программирования, отличающуюся от рассматриваемой задачи целочисленного программирования лишь отсутствием требования целочисленности, называют эодочеб с ослоблеккыми оеракичеки,ямк, соответствующей задаче целочисленного программирования. Материал зтой главы посвящен анализу различных задач целочисленного программирования и изучению методов их решения. Чтобы понять, насколько важны с практической точки зрения задачи целочисленного программирования, достаточно обратиться к задаче распределения ограниченных ресурсов. В такой задаче некоторые ресурсы могут использоваться лишь в количествах, кратных соответствующей единице измерения.
Эти ресурсы будут характеризоваться переменными модели, УДовлетворяющими требованию целочисленности. Примерами подобных ресурсов являются штучные изделия: станки, грузовики, партии товаров, самолеты, компьютеры и т.д. 148 4, ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ 4.1. Методы решения задач целочисленного программирования На первый взгляд наиболее естественным методом решения задач целочисленного програланированил является метпод оююругленил, реализация которого состоит из двух этапов.
На первом этапе находят оптилюальное реиюение задачи линейного программирования с ослабленными ограничениями, соответствующей рассматриваемой задаче целочисленного программирования. На втором этапе значения переменных в оптимальном решении Х', не являющиеся целыми, округляют так, чтобы получить допустилюое решение Х- с целочисленными значениями. Соблазнительность использования метода округления понятна, особенно если погрешность округления невелика по сравнению со значениями округляемых переменных. Однако практическая реализация метода округления может привести к допустимому решению, значимо отличающемуся от оптимального решения исходной задачи целочисленного программирования. Пример 4.1.
Рассмотрим пвлностпью целочисленную задачу х1+1,5хг -+ тах; 2х1+ 4хз ( 17, 10х1+ 4хз ( 45, хыхт) О, хмхз Е Я0(0). Соответствующая задача линейного программирования с ослабленными ограничениями получается снятием ограничений т х„хз Е 1ч'010). Ее оптимальное решение Х' = 17/2 572) может быть получено геолюетричеснилю методом 1рис. 4.1). Этому решению соответствуют крайняя точка А множества С допустимых решений и значение целевой 97уньции 7" = 7,25.
В соответствии с методом округления получаем допустимое т решение Х** = 13 2), значение целевой функции на котором 4.1. Методы решению эадач целочисленного программированию 149 равно 7" = 6. Однако на самом деле оптимальным решением т целочисленной задачи 14.1) является Хв = 12 3), при этом значение целевой функции равно 7'= 6,5. 7Р 1 2х1ж4хт -— 17 а1+ 4хю — -4ь Рис. 4.1 Несостоятельность метода округления как общего метода решения задач целочисленного программирования обусловлена не только возможностью получения неоптимального решения.
Дело заключается в том, что многие задачи люатематичесного програльмированил, не имеющие на первый взгляд никакого отношения к полностью или частично целочисленным задачам, могут быть сформулированы как задачи целочисленного программирования, в которых переменные модели принимают значения из множества 10, 1). В этой ситуации процедура округления является логически неприемлемой. Для иллюстрации основной идеи методов решения задач целочисленного программирования, известных как метподью отпсечений, рассмотрим полностью целочисленную задачу, множество допустимых решений которой изображено на рис. 4.2.
Допустимым решениям этой задачи соответствуют не все точки множества С допустимых решений, а лишь те, координаты которых удовлетворяют требованию целочисленности. Теоретически из множества С всегда можно выделить такое под- 130 4. ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ Рис. 4.я множество С*, что 1см. рис, 4.2): а) оно содержит все точки множества С, координаты которых удовлетворяют требованию целочисленности; б) оно является выпуклым множеством; в) координаты всех его крайних точек удовлетворяют требованию целочисленности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
