Практика. Практика ММ 1. Постановки ЗЛП (1). О. Г. Кантор Рассматриваются вопросы Примеры задач линейного программирования. Задача

• Название: О. Г. Кантор Рассматриваются вопросы Примеры задач линейного программирования. Задача
• Анкор: Практика
• Дата: 23.01.2022
• Размер: 0.61 Mb.
• Имя файла: Практика ММ 1. Постановки ЗЛП (1).pdf
• Тип: Задача; #339416

Примеры постановок задач
линейного программирования
Составлено к.ф.-м.н. доц.
О.Г. Кантор

Рассматриваются вопросы:
1. Примеры задач линейного программирования.
1.1. Задача составления рациона.
1.2. Задача использования ресурсов.
1.3. Основные этапы записи модели линейного программирования.
2. Стандартная и каноническая формы записи модели линейного программирования.
3. Основные приемы перехода от произвольной записи модели к стандартной и канонической форме записи.

1. Примеры задач линейного программирования.
1.1. Задача составления рациона.
Исходные данные задачи
Вид корма
Содержание питательных веществ кг/кг корма
Стоимость руб./кг кальций белок клетчатка
Известняк
0.380
---
---
4
Зерно
0.001 0.09 0.02 15
Соевые бобы
0.002 0.50 0.08 40
Поголовье 20000 цыплят
Средний расход корма на единицу на период планирования – 0,5 кг
Таблица1. Требования по питательности

1. Примеры задач линейного программирования.
1.1. Задача составления рациона.
Цель
Птицеводческой ферме необходимо составить рацион минимальной стоимости при соблюдении требований по питательности.
Требования к кормовой смеси по питательности - смесь должна содержать:
1) не менее 0.8%, но не более 1.2% кальция;
2) не менее 22% белка;
3) не более 5% клетчатки.

1. Примеры задач линейного программирования.
1.1. Задача составления рациона.
Процесс построения математической модели можно
представить как ответы на следующие три вопроса:
1.
Для определения каких величин должна быть построена модель?
2. В чем состоит цель, для достижения которой из всех допустимых значений переменных нужно выбрать те, которые будут соответствовать оптимальному (наилучшему) решению задачи?
3. Какие ограничения должны быть наложены на переменные, чтобы выполнить условия, отраженные в содержательной постановке задачи?

1. Примеры задач линейного программирования.
1.1. Задача составления рациона.
1.
Неизвестными являются содержание в смеси кормов.
Отсюда переменные задачи :
- содержание известняка в смеси;
- содержание зерна в смеси;
- содержание соевых бобов в смеси.
1
x
2
x
3
x
2. Критерием эффективности при сравнении различных вариантов
рациона служит стоимость смеси. Следовательно, целевая функция
задачи будет иметь вид:
min
40 15 4
3 2
1




x
x
x
L

1. Примеры задач линейного программирования.
1.1. Задача составления рациона.
3. Содержательный смысл ограничений.
1). Ограничение на минимальный недельный рацион для всего поголовья
2). Смесь должна содержать не менее 0.8% кальция
3).Смесь должна содержать не более 1.2% кальция
4). Смесь должна содержать не менее 22% белка
5). Смесь должна содержать не более 5% клетчатки кг
000 10 3
2 1



x
x
x
)
(
008 0
002 0
001 0
38 0
3 2
1 3
2 1
x
x
x
x
x
x





)
(
012 0
002 0
001 0
38 0
3 2
1 3
2 1
x
x
x
x
x
x





)
(
22 0
5 0
09 0
3 2
1 3
2
x
x
x
x
x




)
(
05 0
08 0
02 0
3 2
1 3
2
x
x
x
x
x





1. Примеры задач линейного программирования.
1.1. Задача составления рациона.
После преобразования модель задачи будет иметь вид:



























,...
3
,
2
,
1
,
0 0
030 0
030 0
050 0
0 280 0
130 0
220 0
0 010 0
011 0
368 0
0 006 0
007 0
372 0
000 10 3
2 1
3 2
1 3
2 1
3 2
1 3
2 1
j
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
j
min
x
x
x
L




3 2
1 40 15 4

1. Примеры задач линейного программирования.
1.2. Задача использования ресурсов.
Для отделочных работ поступает мраморная крошка 3-х видов и цветной цемент в количестве 50 т., 30 т., 40 т., 30 т.. Эти материалы используются для приготовления 2-х видов облицовочных растворов. Растворы получают при смешивании компонентов в пропорциях 2:3:2:1:2 и 2:1:2:1:4. Последний член пропорции приходится на прочие материалы, которые поступают без ограничения.
Определить оптимальный план приготовления облицовочных растворов, при котором достигается минимум стоимости неиспользованных материалов, если стоимость 1т материалов соответственно равна 500, 800,
300, 100 рублям.
Содержательная постановка задачи

1. Примеры задач линейного программирования.
1.2. Задача использования ресурсов.
Предварительный расчет параметров
:
000 64 100 30 300 40 800 30 500 50
,
250 100 10 1
300 10 2
800 10 1
500 10 2
,
410 100 10 1
300 10 2
800 10 3
500 10 2
0 2
1



















c
c
c
2 1
,c
c
0
c
- стоимость материалов, идущих на приготовление 1т растворов
Где,
- общая стоимость материалов

1. Примеры задач линейного программирования.
1.2. Задача использования ресурсов.
1
x
2
x
min
250 410 000 64 2
1 2
2 1
1 0







x
x
x
c
x
c
c
L
Целевая функция задачи
План приготовления растворов включает две переменные:
- количество раствора первого вида
- количество раствора второго вида.

1. Примеры задач линейного программирования.
1.2. Задача использования ресурсов.















30 1
0 1
0 40 2
0 2
0 30 1
0 3
0 50 2
0 2
0 2
1 2
1 2
1 2
1
x
x
x
x
x
x
x
x
Система ограничений включает один тип ограничений - ограничения по ресурсам, то есть расход всех имеющихся ресурсов не должен превышать их количество

1. Примеры задач линейного программирования.
1.2. Задача использования ресурсов.
min
250 410 000 64 2
1 2
2 1
1 0







x
x
x
c
x
c
c
L















30 1
0 1
0 40 2
0 2
0 30 1
0 3
0 50 2
0 2
0 2
1 2
1 2
1 2
1
x
.
x
.
x
.
x
.
x
.
x
.
x
.
x
.
0 2
1

x
,
x
Модель:

2. Эквивалентные формы записи модели линейного
программирования.
Стандартной задачей называется следующая форма записи задачи
ЛП.
Среди всех неотрицательных решений, удовлетворяющих системе линейных неравенств, выбрать такое, при котором линейная форма принимает минимальное значение
F




























m
n
mn
m
m
m
n
n
n
n
n
n
b
x
a
x
a
x
a
x
a
b
x
a
x
a
x
a
x
a
b
x
a
x
a
x
a
x
a
x
c
x
c
x
c
c
F




3 3
2 2
1 1
2 2
3 23 2
22 1
21 1
1 3
13 2
12 1
11 2
2 1
1 0
min

2. Эквивалентные формы записи модели линейного
программирования
Канонической задачей называется следующая форма записи задачи ЛП.
Среди всех неотрицательных решений системы уравнений выбрать такое, при котором линейная форма принимает минимальное значение
P




























s
t
st
s
s
s
t
t
t
t
t
t
d
x
x
x
x
d
x
x
x
a
x
d
x
x
x
x
x
p
x
p
x
p
p
P















3 3
2 2
1 1
2 2
3 23 2
22 1
21 1
1 3
13 2
12 1
11 2
2 1
1 0
min

3. Основные приемы перехода от произвольной записи
модели к стандартной и канонической форме записи.


1. Переход от неравенства типа к неравенству осуществляется умножением неравенства на -1. Например, неравенства
2 3
2 2
3 2
2 1
2 1






x
x
x
x
эквивалентны.
2. Переход от задачи на отыскание максимума к задаче на отыскание минимума осуществляется умножением целевой функции на -1.
Например, функция max
3 4
3 2
3 2
1 1





x
x
x
L
достигает максимального значения при тех же значениях неизвестных, что и функция min
3 4
3 2
3 2
1 2






x
x
x
L
достигает минимального значения.

3. Основные приемы перехода от произвольной записи
модели к стандартной и канонической форме записи.
3. Переход от неравенства к равенству. Этот переход основан на том, что в задаче ЛП принято, что все переменные .
0

j
x
Рассмотрим общий вид неравенства
i
n
in
i
i
b
x
a
x
a
x
a




2 2
1 1
Перенесем свободный член в левую часть неравенства
i
b
0 2
2 1
1





i
n
in
i
i
b
x
a
x
a
x
a

Обозначим левую часть через
x
n

1
i
n
in
i
i
n
b
x
a
x
a
x
a
x







2 2
1 1
1
Последнее уравнение совместно c требованием не отрицательности переменной будет эквивалентно исходному неравенству.
Переход от равенств к неравенствам осуществляется в обратном порядке.
0 1


n
x