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

Содержание

Слайд 2

Для изготовления двух видов продукции Р1 и Р2 используют четыре вида ресурсов:

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

Задача об использовании ресурсов

Прибыль от реализации единицы продукции Р1 и Р2 соответственно 2 и 3 ден. ед.

Слайд 3

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

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

Задача об использовании ресурсов

Слайд 4

Решение
Введем переменные

Задача об использовании ресурсов

Х1 – число единиц продукции Р1, запланированных к

Решение Введем переменные Задача об использовании ресурсов Х1 – число единиц продукции
производству

Х2 – число единиц продукции Р2, запланированных к производству

Прибыль:

F = 2*X1+3*X2

Цель:

F → max

Слайд 5

Решение
Ограничения

Задача об использовании ресурсов

1) Условие неотрицательности: Х1≥0, Х2 ≥0

2) На запас сырья S1:

1*X1+3*X2

Решение Ограничения Задача об использовании ресурсов 1) Условие неотрицательности: Х1≥0, Х2 ≥0
≤ 18

3) На запас сырья S2:

4) На запас сырья S3:

5) На запас сырья S4:

2*X1+1*X2 ≤ 16

0*X1+1*X2 ≤ 5

3*X1+0*X2 ≤ 21

Слайд 6

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

Задача об использовании ресурсов

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

Слайд 7

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

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

Слайд 8

В дневной рацион питания цыплят включают два продукта П1 и П2. Причем

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

Задача составления рациона

Определить оптимальный рацион питания, стоимость которого будет наименьшей

Слайд 9

Решение
Введем переменные

Задача составления рациона

Х1 – число единиц продукта П1, входящего в дневной

Решение Введем переменные Задача составления рациона Х1 – число единиц продукта П1,
рацион

Х2 – число единиц продукта П2, входящего в дневной рацион

Стоимость дневного рациона :

F = 2*X1+4*X2

Цель:

F → min

Слайд 10

Решение
Ограничения

Задача составления рациона

1) Условие неотрицательности: Х1≥0, Х2 ≥0

2) Ограничение на максимальное содержание продукта

Решение Ограничения Задача составления рациона 1) Условие неотрицательности: Х1≥0, Х2 ≥0 2)
П1: X1 ≤ 200

0,2*X1+0,2*X2 ≥ 120
0,4*X1+0,2*X2 ≥ 160

3) Ограничения на минимальное содержание питательных веществ:

Слайд 11

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

Задача составления рациона

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

Слайд 12

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

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

Слайд 13

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

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

Слайд 14

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

В канонической задаче:
1) Целевая функция → max
2) Все ограничения

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

Слайд 15

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

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

Для выполнения этих условий может понадобиться выполнить следующие преобразования:

Пусть F → min
Переходим к (-F) → max (переходим к противоположной функции)

Слайд 16

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

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

Для выполнения этих условий может понадобиться выполнить следующие преобразования:

2. Пусть дано ограничение неравенство
a1x1+a2x2≥b
Вводим новую переменную х3≥0:
a1x1+a2x2-х3 = b

Слайд 17

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

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

Для выполнения этих условий может понадобиться выполнить следующие преобразования:

3. Пусть xi ≤ 0
Вводим новые переменные хj≥0, хk≥0 :
xi=xj-хk

Таким образом, задача линейного программирования (ЗЛП) в любом виде может быть преобразована к канонической форме

Имя файла: Примеры-задач-линейного-программирования.pptx
Количество просмотров: 142
Количество скачиваний: 1