Материал: Основы математического моделирования. курс лекций. Перова А.В

2.Все переменные должны быть неотрицательны.

3.Правые части ограничений должны быть неотрица-

тельны.

4.Все ограничения записываются в виде равенств. Указанные выше три формы ЗЛП можно привести друг

кдругу с помощью эквивалентных преобразований.

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

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

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

Для изготовления n видов продукции A1,…,An необходимы ресурсы S1,…,Sm (сырье, рабочая сила, оборудование и т.д.). Заданы значения aij, которые характеризуют количество ресурса Si , необходимого для выпуска единицы продукции Aj. Запас каждого ресурса Si ограничен и равен bi . От реализации единицы продукции Aj может быть получена прибыль cj. Необходимо так составить производственный план (т.е. определить, сколько продукции каждого вида необходимо выпустить), чтобы общая прибыль от производства всей продукции была максимальной. Исходные данные задачи можно удобно представить в виде табл. 1:

60

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

c1x1+ c2x2+...+ cnxn max;

n

aij xj bi,i 1,m;

j 1

xj 0, j 1,n.

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

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

61

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

F=7x1+3x2+6x3+12x4 max;

3x1+x2+2x3+4x4 440;

x1+8x2+6x3+2x4 200;

x1+4x2+7x3+2x4 320;

xj 0, j=1,4.

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

Имеется набор компонентов A1,…,An, при сочетании которых в разных пропорциях образуются различные смеси. В состав каждого компонента входят вещества P1,…,Pm. Через aij обозначим количество вещества Pi в единице компонента Aj. В смеси необходимо обеспечить содержание вещества Pi (обозначим его через bi). Цена единицы компонента Aj равна cj. Необходимо определить состав смеси (т.е., количество компонентов каждого вида), цена, которой окажется минимальной. Исходные данные задачи представлены в табл.3:

62

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

c1x1+ c2x2+...+ cnxn min;

n

aijx j bi ,i 1,m;

j 1

x j 0, j 1,n.

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

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

63

Математическая модель данной задачи имеет вид: F=6x1+x2+x3 min; 2x1+4x2+5x3 26; 4x1+2x2 16;

12x1+3x2+x3 60;

xj 0, j=1,3.

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

Пусть планируется производство комплектных изделий. Каждое изделие содержит m видов деталей, причем деталей первого вида - k1 единиц, деталей второго вида k2 единиц, деталей j-го вида kj единиц. Изделия могут изготавливаться n различными исполнителями. Пусть в единицу времени i-й исполнитель может изготовить aij элементов j-го вида. Сдаче подлежат только комплектные изделия. Каждый i-й исполнитель работает не более bi часов. Определить такой план загрузки исполнителей, чтобы общее число выпускаемых комплектных изделий было максимальным.

Обозначим через xij- время изготовления деталей j-го

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

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

min I j

j 1,m

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

64