Примеры задач линейного программирования

Для изготовления двух видов продукции
Р1 и Р2 используют четыре вида ресурсов: S1, S2, S3 и S4.
Задача об использовании ресурсов
Прибыль от реализации единицы продукции Р1 и Р2 соответственно 2 и 3 ден. ед.

Необходимо составить такой план производства продукции, при котором прибыль от ее реализации будет максимальной
Задача об использовании ресурсов

Решение
Введем переменные
Задача об использовании ресурсов
Х1 – число единиц продукции Р1, запланированных к производству
Х2 – число единиц продукции Р2, запланированных к производству
Прибыль:
F = 2*X1+3*X2
Цель:
F → max

Решение
Ограничения
Задача об использовании ресурсов
1) Условие неотрицательности:
Х1≥0, Х2 ≥0
2) На запас сырья S1:
1*X1+3*X2 ≤ 18
3) На запас сырья S2:
4) На запас сырья S3:
5) На запас сырья S4:
2*X1+1*X2 ≤ 16
0*X1+1*X2 ≤ 5
3*X1+0*X2 ≤ 21

Экономико-математическая модель
(задача линейного программирования)
Задача об использовании ресурсов

Экономико-математическая модель (коротко)

В дневной рацион питания цыплят включают два продукта П1 и П2. Причем продукта П1 должно войти в дневной рацион не более 200 ед.
Стоимость 1 ед. продукта П1 составляет 2 ден. ед., а продукта П2 – 4 ден. ед.
Задача составления рациона
Определить оптимальный рацион питания, стоимость которого будет наименьшей

Решение
Введем переменные
Задача составления рациона
Х1 – число единиц продукта П1, входящего в дневной рацион
Х2 – число единиц продукта П2, входящего в дневной рацион
Стоимость дневного рациона :
F = 2*X1+4*X2
Цель:
F → min

Решение
Ограничения
Задача составления рациона
1) Условие неотрицательности:
Х1≥0, Х2 ≥0
2) Ограничение на максимальное содержание продукта П1: X1 ≤ 200
0,2*X1+0,2*X2 ≥ 120
0,4*X1+0,2*X2 ≥ 160
3) Ограничения на минимальное содержание питательных веществ:

Экономико-математическая модель
(задача линейного программирования)
Задача составления рациона

Поясним термин линейное программирование
линейное означает: ищется экстремальное значение (min или max) линейной целевой функции при линейных ограничениях (линейных уравнениях или неравенствах)
программирование в данном словосочетании имеет смысл планирования

Каноническая задача линейного программирования

Каноническая задача линейного программирования
В канонической задаче:
1) Целевая функция → max
2) Все ограничения имеют вид уравнений
3) Все переменные неотрицательны

В канонической задаче:
1) Целевая функция → max
2) Все ограничения имеют вид уравнений
3) Все переменные неотрицательны
Для выполнения этих условий может понадобиться выполнить следующие преобразования:
Пусть F → min
Переходим к (-F) → max (переходим к противоположной функции)

В канонической задаче:
1) Целевая функция → max
2) Все ограничения имеют вид уравнений
3) Все переменные неотрицательны
Для выполнения этих условий может понадобиться выполнить следующие преобразования:
2. Пусть дано ограничение неравенство
a1x1+a2x2≥b
Вводим новую переменную х3≥0:
a1x1+a2x2-х3 = b

В канонической задаче:
1) Целевая функция → max
2) Все ограничения имеют вид уравнений
3) Все переменные неотрицательны
Для выполнения этих условий может понадобиться выполнить следующие преобразования:
3. Пусть xi ≤ 0
Вводим новые переменные хj≥0, хk≥0 :
xi=xj-хk
Таким образом, задача линейного программирования (ЗЛП) в любом виде может быть преобразована к канонической форме