- Если операционная математическая модель состоит из линейной целевой функции, и входящие в систему ограничений равенства и неравенства также линейны, то такая модель относится к классу оптимизационных задач линейного программирования
- Если наряду с указанными выше ограничениями потребовать, чтобы все переменные
xj(j = 1,n) были целыми, то задача становится задачей целочисленного линейного программирования.
- Ограничения задачи определяют в n-мерном пространстве выпуклую область OABCD. Эта область изображена на рисунке в плоскости двух координат
Хк и Хi. Узлы целочисленной решётки показаны точками. Такие точки, расположенные внутри области OABCD, являются допустимыми решениями задачи целочисленного программирования.
Рассмотрим в качестве примера следующую задачу
- Для приобретения оборудования фирма может выделить
36 тыс. руб. Оборудование должно быть размещено на производственных площадях не превышающих
60 кв. м. Фирма может заказать оборудование двух видов: менее мощные машины типа А стоимостью 3
тыс. руб.,
каждая из которых требует для размещения производственную площадь 3
кв. м., и обеспечивает производительность за смену 2 т, и более мощные машины
В стоимостью 4 тыс. руб., каждая из которых занимает площадь 5 кв. м. И обеспечивает производительность 2,7 т.
- В качестве управляющих переменных выбираем х1 – количество приобретаемых машин типа А и х2 – количество приобретаемых машин типа В.
Тогда определив целевую функцию Z,
выражающую суммарную производительность, которую требуется максимизировать, получим математическую модель задачи в виде
- Z
=2x1 + 2,7x2
max При ограничениях
- 3x1
+ 5x2 < 60
- 3x1
+ 4x2 < 36
- x2
< 8
- x1
>0, x2 >0
- x1,
x2 –
целые числа
Фирма занимается составлением диеты, содержащей по крайней мере
20 единиц белков,
30 единиц углеводов,
10 единиц жиров и 40 единиц витаминов. Составить диету из 5 продуктов, имеющую минимальную стоимость, в которой содержание каждого вида ингредиентов были бы не менее установленного предела. Цена за 1 кг. пяти имеющихся продуктов и содержание ингредиентов в 1 кг. продукта указаны в таблице.
10
18
32
36
12
Цена
2
6
4
2
2
Витамины
4
0
3
8
1
Жиры
3
4
0
0
12
Углеводы
2
1
10
12
2
Белки
Молоко
Фрукты
Рыба
Соя
Хлеб
Ингредиенты