Прикладные линейные модели

Рассмотрим основные приемы построения математических моделей для некоторых типовых задач линейного программирования.

1. Задача определения производственного плана.

Для изготовления n видов продукции A₁,…,A_n необходимы ресурсы S₁,…,S_m (сырье, рабочая сила, оборудование и т.д.). Заданы значения a_ij, которые характеризуют количество ресурса S_i, необходимого для выпуска единицы продукции A_j. Запас каждого ресурса S_i ограничен и равен b_i. От реализации единицы продукции A_j может быть получена прибыль c_j. Необходимо так составить производственный план (т.е. определить, сколько продукции каждого вида необходимо выпустить), чтобы общая прибыль от производства всей продукции была максимальной.

Исходные данные задачи можно удобно представить в виде табл.1:

Таблица 1

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

c₁x₁+ c₂x₂+...+ c_nx_n ®max;

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

Пример. Требуется определить, в каком количестве необходимо выпускать продукцию четырех типов Прод1, Прод2, Прод3, Прод4 для изготовления которой требуются ресурсы трех видов: трудовые ресурсы, сырье, финансы. Нормы расхода ресурсов каждого вида для выпуска единицы продукции, а также прибыль, получаемая от реализации единицы каждого типа продукции, приведены в табл. 2. Количество расходуемых ресурсов не должно превышать имеющихся запасов.

Таблица 2

Математическая модель для решения данной задачи будет иметь следующий вид:

F=7x₁+3x₂+6x₃+12x₄®max;

3x₁+x₂+2x₃+4x₄ £440;

x₁+8x₂+6x₃+2x₄ £200;

x₁+4x₂+7x₃+2x₄ £320;

x_j ³0, j= .

2. Задача о смесях.

Имеется набор компонентов A₁,…,A_n, при сочетании которых в разных пропорциях образуются различные смеси. В состав каждого компонента входят вещества P₁,…,P_m. Через a_ij обозначим количество вещества P_i в единице компонента A_j. В смеси необходимо обеспечить содержание вещества P_i (обозначим его через b_i). Цена единицы компонента A_j равна c_j. Необходимо определить состав смеси (т.е., количество компонентов каждого вида), цена которой окажется минимальной. Исходные данные задачи представлены в табл.3:

Таблица 3

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

c₁x₁+ c₂x₂+...+ c_nx_n ®min;

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

Пример Фирма занимается составлением диеты, состоящей из трех продуктов (мясо, крупы, молоко) и содержащей не более 26 единиц углеводов, не менее 16 единиц витаминов и не более 60 единиц белков. Как дешевле всего достичь этого при указанных в табл. 4 количествах углеводов, витаминов и белков в единице каждого продукта?

Таблица 4

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

F=6x₁+x₂+x₃®min;

2x₁+4x₂+5x₃ £26;

4x₁+2x₂³16;

12x₁+3x₂+x₃ £60;

x_j ³0, j= .

3. Задача о комплектах.

Пусть планируется производство комплектных изделий. Каждое изделие содержит m видов деталей, причем деталей первого вида - k₁ единиц, деталей второго вида k₂ единиц, деталей j-го вида k_j единиц. Изделия могут изготавливаться n различными исполнителями. Пусть в единицу времени i-й исполнитель может изготовить a_ij элементов j-го вида. Сдаче подлежат только комплектные изделия. Каждый i-й исполнитель работает не более b_i часов. Определить такой план загрузки исполнителей, чтобы общее число выпускаемых комплектных изделий было максимальным.

Обозначим через - время изготовления деталей j-го вида i-м исполнителем. Тогда общее число деталей j-го вида, изготавливаемых всеми исполнителями, определится в виде

, .

Общее количество изделий, для выпуска которых хватит деталей j-го типа при условии, что k_j единиц расходуется на одно изделие равно

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

В результате математическую модель задачи можно сформулировать в виде:

=

, ;

.

Для формализации данной постановки в виде задачи линейного программирования введем новую переменную:

,

что равносильно записи

.

Тогда окончательный вид математической модели задачи:

Не нашли, что искали? Воспользуйтесь поиском: