Задачей линейного программирования (ЗЛП) называется задача отыскания экстремума (максимума или минимума) линейной функции от нескольких переменных при линейных ограничениях на эти переменные.
Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах. -мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах. -мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.
Линейное
программирование
Задачей линейного программирования (ЗЛП) называется
задача отыскания экстремума (максимума или минимума)
линейной функции от нескольких переменных при линейных
ограничениях на эти переменные.
)
2
x
,
xxf
(
1
1
127
x
x
1
7
83
x
1
,0
0
x
1
2
x
x
2
2
2
5
x
2
max
целевая функция
система
ограничений
Транспортная задача
380т
220т
320т
200т
280т
Транспортная задача
Стоимости перевозок
С пл.
Завод
№1
№2
№1
№2
№3
2
4
4
5
6
3
Транспортная задача
Завод №1
x
y
320т
320xy
Стройплощадки
№1
№2
№3
220т
200т
280т
Завод №2
280y
200x
x+y100
380т
План перевозок
С.пл.
зав.
№1
№2
№1
x
№2
y
200x
280y
№3
320xy
x+y100
Завод №1Завод №2№1№2№3
Математическая модель
Стоимость перевозок
С.пл.
зав.
№1
№2
№1
№2
№3
2
4
4
5
6
3
С.пл.
зав.
№1
№2
План перевозок
№3
№2
№1
x
y
200x
280y
320xy
x+y100
Стоимость запланированных перевозок
f(x,y)= 2x + 4y + 6(320xy) + 4(200x) + 5(280y) + 3(x+y100) =
= 3820 – 5x – 4y
Математическая модель
f(x,y) = 3820 – 5x – 4y
min→
Целевая функция
x
320
200
yx
0
x
0
y
0
280
x
y
0
100
y
,0
0
Система ограничений
Ограничения
неотрицательности
Планирование
производства
Запас
ресурса
24
12
8
4
3
1
4
6
2
1
5
x – число выпускаемых
табуреток
y – число выпускаемых
стульев
Ресурс1
Ресурс2
Ресурс3
Прибыл
ь
Суммарная прибыль от реализации всей продукции
f(x,y) = 4x + 5x
→ max
Цель задачи – максимизация прибыли
Планирование
производства
Расход ресурса ≤ Запас ресурса
Запас
ресурса
24
12
8
4x
+
+3x
+x
6y ≤
2y ≤
y ≤
24
12
8
Ресурс1
Ресурс2
Ресурс3
Прибыл
ь
4
3
1
4
6
2
1
5
Расход ресурсаЗапас ресурса
Математическая модель
f(x,y) = 4x + 5y
→
max
Целевая функция
24
12
6
y
x
4
x
y
2
y
8
3
x
Система ограничений
x
y
,0
0
Ограничения
неотрицательности
Составление оптимального
рациона
Предположим, что в дневной рацион животных должны входить
питательные вещества двух видов в количестве, заданном в
таблице. Имеется возможность составлять рацион из кормов двух
видов, для которых задано содержание питательных веществ в
единице корма и цена одной единицы каждого из видов кормов.
При удовлетворении условий по необходимому содержанию
питательных веществ в данном рационе требуется достичь его
минимальной стоимости.
Корм1 Корм2
Пит. вво1
Пит. вво2
Цена корма
2
6
5
1
4
2
Пит. вещ
в в
рац.
12
30
Математическая модель
min
2
y
,(
yxf
2
x
x
6
x
5
x
12
30
y
,0
0
)
y
4
y
Составить
математическую модель
На фабрике для производства двух видов продукции
используются три вида сырья. Оно имеется на фабрике в
следующих количествах: 13 единиц вида А, 9 единиц вида
В и 8 единиц вида С. На производство первого вида
продукции надо израсходовать (2; 0; 2) единиц указанных
видов сырья, а для второго вида продукции эти показатели
равны
(2; 3; 0). Прибыль, получаемая фабрикой от
реализации первого вида продукции, равна 3 условным
единицам, а от реализации единицы продукции второго
вида
единицам. Составить
математическую модель работы фабрики, чтобы обеспечить
наибольшую прибыль.
таким же
равна
4
Математическая модель
max
y
4
y
yxf
,(
2
x
y
3
x
2
x
)
3
x
13
2
9
8
y
,0
0
Составьте
математическую модель
На животноводческой ферме производится откорм скота.
Пусть известно, что каждому животному надо ежедневно
выдать не менее 6 единиц вещества А, 8 единиц вещества В
и 12 единиц вещества С (этими веществами могут быть,
например, белки, жиры и углеводы). Для откорма животных
можно закупить два вида кормов
(например, жмых и
комбикорм). Единица веса первого корма содержит 21
единицу вещества А, 2 единицы вещества В и 4 единицы
вещества С, а стоимость ее равна 3рублям. Для второго вида
кормов соответствующие цифры равны 3; 2; 2 и 2рублям.
Составьте математическую модель процесса, при котором
была бы обеспечена суточная потребность в веществах А, В
С, причем стоимость его была бы наименьшей.
Математическая модель
min
y
2
)
3
yxf
,(
x
21
3
6
y
x
y
2
8
2
x
x
y
2
12
4
,0
y
0
x
Графический метод
y
8
6
4
0
f(x,y) = 4x + 5y
→
max
x ≥0 y ≥0
4x+6y ≤ 24
4x+6y = 24
3x+2y ≤ 12
3x+2y = 12
x + y ≤ 8
4
6
8
x
x= 12
5 y= 12
5
f= 108
5
Вывод: наиболее выгодно выпускать табуретки и стулья в
одинаковом количестве.
ЗЛП неразрешима
Система не имеет
ни одного
решения
y
0
x
ЗЛП неразрешима
Целевая функция
не ограничена на
множестве
решений
y
0
N
x
ЗЛП разрешима
Множество
решений состоит
из одной точки
y
0
x
ЗЛП разрешима
Единственное
оптимальное
решение ЗЛП
N
y
0
x
Решить ЗЛП графически
min
f
x
x
y
2
1
x
y
y
2
x
4
y
2
x
y
,0
0
max
f
x
2
y
x
1
y
x
1
x
y
,0
1
y
max
f
x
x
2
y
y
1
x
x
2
y
1
,0
y
0
max
y
x
f
x
y
1
,0
x
y
0
Решить ЗЛП графически
f(x,y) = 3820 – 5x – 4y
min→
x
320
200
yx
0
x
0
y
0
280
x
y
0
100
y
,0
0
Решить ЗЛП графически
№1
№2
120 тыс.т
80 тыс.т
А
Б
В
100 тыс.т
60 тыс.т
40 тыс.т
Стоимость перевозок
№1 №2
24
15
12
18
27
9
А
Б
В
Математическая модель
5
y
1380
min
x
120
80
)
,(
yxf
y
x
x
100
y
60
x
y
0
x
0
y
Графическое решение
3x
120
80
)
,(
yxf
x
y
x
100
y
60
x
y
0
0
x
y
15
y
4140
min
y
120
80
60
10
0 10
80
100
120
x
x=60, y=60, f =3420
Линейное программирований.ppt
