XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 8
Текст из файла (страница 8)
Задача линейного программирования имеет следующий вид: сьхь -о шах; Е Я=1 Яазьхь < 6;, 1 Е 11,' Ьк1 ~асяхь = 6,, 1б 1з, 1=1 ~1 асяхь > 6;, 1 б 1з', 1=1 хь > О, й=1,п, (2.1) Пример 2.1. Небольшая фабрика производит два вида лака для покрытия деревянных поверхностей при внутренних и наружных работах. Для производства лаков используются два исходных продукта — А и В. Максимально возможные суточные запасы этих продуктов определяются емкостями, где а;ь, сь, 6; — известные числовые параметры, а множества 11, 11, 1з попаРно не пеРесекаютсЯ и 11 0 1з 0 1з —— (1, ..., т).
Неизвестные хь, й = 1, и, в задаче (2.1), представляющие собой т координаты вектора Х = (х1 хз ... х„), называют управляемыми переменными, или переменными модели. Рассмотрим пример задачи исследования операций, приводящей к задаче линейного программирования. имеющимися на фабрике, и составляют 6 и 8 т соответственно. При производстве 1 т лака для внутренних работ расходуется 1т продукта А и 2т продукта В, а при производстве 1т лака для внешних работ расходуется 2т продукта А и 1т продукта В.
Изучение рынка сбыта показало, что суточный спрос на лак для наружных работ не превышает 2 т. Доход от реализации (в условных денежных единицах) 1т лака для внутренних работ равен 3, а доход от реализации 1 т лака для внешних работ — 2. Необходимо выяснить, какое количество лака каждого вида должна производить фабрика, чтобы доход от реализации продукции был максимальным. Суть рассматриваемой задачи исследования операций можно сформулировать следующим образом. Для фабрики требуется определить объемы производства каждого из лаков, максимизирующие доход от реализации продукции, с учетом ограничений на спрос и расход исходных продуктов А и В.
Так как нужно определить объемы производства каждого вида лака, то управляемыми переменными являются: х1— суточный объем производства лака для внутренних работ (в тоннах); хз — суточный объем производства лака для внешних работ (в тоннах). Таким образом, и = 2 в (2.1). Суточный расход каждого из исходных продуктов А и В дяя производства лаков не может превосходить максимально яюэможного суточного запаса этого продукта, т.е.
х1+ 2хз < 6 (дяя продукта А) и 2х1+ хз < 8 (для продукта В), Ограничение на величину суточного спроса на лак для на®жных работ имеет вид хз < 2. А так как объемы производяФва продукции не могут быть отрицательными, то необходимо 11(нести ограничения на знак управляемых переменных: х1 > О, 4~ > О. Таким образом, в задаче (2.1) т = 3, 11 — — (1,2,3), Ь= 1з= О. В предположении, что объемы сбыта каждого вида лака Й зависят друг от друга, общий доход у равен сумме дохода продажи лака для внутренних работ и дохода от продажи ЗЛ.
Постановка общей задачи и ее анализ 53 52 2. ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ лака для наружных работ. Таким образом, 1" (хм хз) = Зя1+ 2хз (в условных денежных единицах) н математическая модель рассматриваемой задачи исследования операций может быть представлена в следующем виде: Зх1+2хз -~ шах; х1+2хз < 6, 2х1+хз < 8, хз < 2, ~1 (2,2) я1>0, хз>0.
сьяь — ~ гпах; Е ь=1 Е аъхь < 5;, я=1 (2.3) г=1,т, й = 1,и. хь >О, Чтобы задача исследования операций могла быть представлена как задача линейного программирования, необходимо Задачи линейного программирования во многих случаях оказываются задачамм расвределмзтзельмоео зтамзза, суть которых заключается в следующем. Пусть рассматриваемая система характеризуется наличием и видов производственной деятельности, для осуществления которых имеются различные ресурсы с номерами 1 = 1,т.
Возможный объем потребления г-го ресурса ограничен неотрицательной величиной 5,, а его расход для производства единицы продукта Ь-го вида производственной деятельности равен апо где й = 1, о. В свою очередь, единица продукта и-го вида производственной деятельности характеризуется величиной сы называемой удельной прибылью. Необходимо определить объемы хы й = 1, о, производственной деятельности каждого вида, обеспечивающие максимальный суммарный доход от производственной деятельности системы в целом без нарушения ограничений, накладываемых на использование ресурсов.
В общем случае задача распределительного типа имеет вид выполнение трех условий: 1) пропорциональности; 2) аддитивности; 3) неотрицательности. Заметим, что зти условия имели место при построении задач (2.2), (2.3). В терминах задач распределительного типа пропорциональность означает, что затраты ресурсов на любой вид производственной деятельности, а также вклад зтого вида производственной деятельности в суммарный доход прямо пропорциональны его уровню (объему) производства. Аддитивность указывает на то, что общий объем ресурсов, потребляемый всеми видами производственной деятельности, равен сумме затрат 'ресурсов на отдельные виды производственной деятельности, а общий доход от производственной деятельности равен сумме доходов от каждого вида производственной деятельности. Неотрицательность означает, что ни одному из видов производственной деятельности не может быть приписан отрицательный объем производства.
Для большинства систем, встречающихся на практике, зто допущение является следствием реальных условий их функционирования. Возможны ситуэ; ции, когда некоторое управляемое переменное хь может при'нимать и отрицательные значения. В зтом случае говорят о !~иеоероммчеммом е эмоме тьеремеммом модели, и испольвуют представление зтого переменного в виде разности двух неотрицательных управляемых переменных: яь=хл-хь, хь>0, хь>0. На практике допущения о пропорциональности и аддитивности при построении математических моделей задач исследования операций не так часто соответствуют объективной реальности, а их принятие фактически означает аппроксимацию нелинейной модели линейной.
Продолжим рассмотрение частной задачи исследования опе,,1Фций, начатое в примере 2.1, и воспользуемся ееомезтьричефзяим мезтзодом ее решения. Основой зтого метода является геометрическое (графическое) представление множества допу- 57 э.!. Постановка общей эадачн н ее аналнэ 56 2. ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ т Х' = (10/3 4/3) .
Во всех остальных случаях оптимальное решение будет отличаться от найденного. В частности, если т ! (х2,хз) = Зх! + хз, то оптимальным является решение (4 О) При — ' = 0,5 и '— ' = 2 любая точка соответствующей стороны С2 С2 многоугольника ГО, отличная от точки С, определяет оптимальное решение, отличное от найденного оптимального решения Х*. 46 аслхь К 6;, !' Е (1, 2, ..., т), л=! (гА) в задаче (2.3) называют а2222222вэеым, если аслхь — — 6„ Е ь=! и 22оссэавэеым в противном случае.
Если некоторое ограничение является активным, то соответствующий ресурс называют „Лицу, принимающему решения", полезно знать и о том, как повлияют на оптимальное решение изменение спроса на выпускаемую продукцию и увеличение или уменьшение запасов исходных продуктов. Исследования, позволяющие получить эту информацию в совокупности с изучением зависимости оптимального решения от параметров целевой функции, представляют злобой анализ на чувствительность математической модели (2.2) рассматриваемой задачи исследования операций. Для удобства дальнейших рассуждений обратимся к задаче линейного программирования (2.3) распределительного типа, предполагая, что непустое множество С допустимых решений ограничено.
т Пусть Х' = (Х* ... Х„') — оптимальное решение рассматриваемой задачи линейного программирования распределительного типа. Ограничение деф22ци222ным ресурсом, так как при реализации оптимального решения он используется полностью. ресурс, соответствующий неактивному ограничению, следует отнести к 22едефтзцтаээамым ресурсам (недефицитные ресурсы имеются в некотором избытке). Графическое решение задачи линейного программирования, рассмотренной в примере 2.2, показывает, что оптимальному решению всегда можно поставить в соответствие хотя бы одну вершину многоугольника, изображающего множество С допустимых решений.
Такую вершину будем называть о2222222мольной вершимой. Через оптимальную вершину С (см. рис. 2.1) проходят две прямые х! + 2хз = 6 и 2х! +хз — — 8. Поэтому активными являются ограничения на суточные запасы исходных продуктов А и В. При анализе модели на чувствительность по правым частям ограничений (2.4) определяются: а) предельно допустимое увеличение запаса дефицитного ресурса, позволяющее получить 'Зовов оптимальное решение, которое в смысле значения целевой :функции является более предпочтительным, чем старое; б) предельно допустимое снижение запаса недефицитного ресурса, не 'агзменяюшее найденного ранее оптимального решения. Ясно, э!то анализ влияния на оптимальное решение процесса увеличе:ния запаса недефицитного ресурса не имеет смысла.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
