Некоторые приложения линейного программирования

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

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

Задача о составе шихты. С такой задачей мы сталкиваемся на чугуноли­тейных предприятиях при составлении оптимального состава шихты. Шихта представляет собой смесь, в состав которой входят в определенной весовой пропорции различные исходные материалы (чугун, лом и т.д.). Сырьевые мате­риалы шихты содержат различные количества примесей углерода, кремния, марганца, серы и т.д. Составляющие шихту материалы в количественном отно­шении выбираются так, чтобы жидкий металл имел определенное содержание необходимых примесей. От этого зависит химический состав и механические характеристики конечного продукта.

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

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

Пусть — содержание -го химического элемента в единице -го сырьевого материала . Чтобы металл обладал необходимыми свойствами, величина содержания в нем каждого элемента должна находиться между заданными нижним , и верхним пределами. Обозначим через доли каждого сырьевого материала в единице шихты. Пусть — стоимость единицы -го сырьевого материала. Тогда математическая модель задачи примет вид:

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

1) содержание -го химического элемента в шихте должно находиться между нижним и верхним пределами:

;

;

2) условие, выражающее долевой состав сырьевых материалов в единице искомой шихты:

;

3) условие неотрицательности:

.

Задача сводится, таким образом, к вычислению , обращающих в минимум линейную форму при заданных условиях.

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

Пусть при -м способе раскроя одной единицы -й партии полуфабрикатов получается деталей -го типа.

Обозначим через количество единиц -й партии материалов, которые следует раскроить по -му способу. Количество деталей -го типа, которое будет при этом получено, равно . Количество деталей -го типа, которое можно получить из -й партии полуфабрикатов, используя все способы раскроя, равно . Общее число деталей -го типа, очевидно, можно получить, если сложить количества деталей этого вида, выкраиваемых из каждой партии материалов:

.

Каждый комплект содержит деталей -го типа. Поэтому количество комплектов, обеспеченных деталями -го типа, равно:

.

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

.

Кроме того, должны быть учтены условия

― целые.

Данные показывают, что -я партия содержит единиц материала. Также выполнены естественные условия неотрицательности переменных и их целочисленности.

Задача о назначениях (задача выбора). Прежде всего отметим, что си­туация, на основе которой обычно ставится задача о назначениях, выглядит достаточно искусственной. И в этом плане целесообразность ее рассмотрения объясняется в первую очередь обилием приложений, т.е. можно привести мно­жество примеров из различных областей, где возникают задачи, подобные рассматриваемой.

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

Для составления математической модели обозначим через назначение -го кандидата на -ю работу. Тогда, так как количество кандидатов равно количеству работ и каждый из них может быть назначен только на одну работу, принимает только два значения: единица, если -й кандидат назначается для выполнения -й работы; нуль, если -й кандидат не назначается для выполнения -й работы. Поэтому и . При назначении -го лица на -ю работу производительность равна . Суммарную производительность можно выразить функцией .

Таким образом, приходим к следующей задаче линейного программирования:

найти максимальное значение функции

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

.

Умножая линейную функцию на –1, приводим задачу к транспортной, в которой объем запасов каждого поставщика и объем потребностей каждого потребителя равны единице. Рассмотренную задачу можно обобщить, если име­ются идентичные работы и кандидаты, которые могут их выполнять. Тогда работы можно объединить в категории, а кандидатов — в группы.

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

Обозначим через количество лиц -й группы, назначенных для выполнения работ -й категории. Тогда математическая модель задачи примет следующий вид:

найти максимальное значение линейной функции

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

.

Замечание. В задаче общее число работ равно общему числу кандидатов. Если , то вводят фиктивную группу кандидатов, содержащую . Если , то используют фиктивную категорию работ, состоящую из единиц.

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

Рассмотрим так называемую однопродуктовую модель задачи, т.е. рассмот­рим задачу, по условию которой отрасль производит один вид продукции. Введем обозначения: — спрос на данный продукт в -м пункте потребления; — мощности действующих предприятий или проекты реконструкции и ново­го строительства; — функция затрат на производство продукции в пункте -его производства в объеме единиц; — транспортные издержки на доставку единицы продукта из -го пункта его производства в -й пункт потребления; ― объем поставок -го поставщика -му потребителю; — мощность нового, реконструируемого или действующего предприятия в -м пункте.

Математическая модель задачи такова:

найти минимум функции

,

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

Данная задача будет нелинейной, если функции являются нелинейными; если же линейно зависят от объемов производства, то задача будет линейной.

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

Вопросы для самостоятельного изучения и подготовки рефератов

1. Двойственность в линейном программировании.

2. Экономическая интерпретация теорем двойственности (оптимальные значения двойственных переменных как оптимальные оценки ресурсов в задачах оптимизации плана производства).

3. Целочисленное программирование. Кадровая задача, задачи об инвестициях, распределение оборудования.