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

Для изготовления двух видов продукции Р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: X ,2*X1+0,2*X ,4*X1+0,2*X ) Ограничения на минимальное содержание питательных веществ:

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

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

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

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

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

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

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

Литература 1. Шикин Е.В., Шикина Г.Е. Исследование операций. - М.: ТК Велби, с. 2. Кремер Н.Ш., Путко Б.А. Исследование операций в экономике. - М.: ЮНИТИ, с. 3. Красс М.С., Чупрынов Б.П. Математика для экономистов. - СПб.: Питер, с.