Постановка задач линейного программирования и исследование их структуры. Тема 4

1.

Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Ижевский государственный технический университет
имени М. Т. Калашникова»
Кафедра «АСОИУ»
Курс «Модели и методы анализа проектных решений»
Тема «Постановка задач линейного программирования и
исследование их структуры»
Автор Исенбаева Е.Н., старший преподаватель
Ижевск
2014

2. ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Задача решаемая методами исследования операций:
максимизировать
при ограничениях
f(x1,..,xn)
где f(x1,..,xn) - целевая функция или эффективность системы (например,
доход от производства каких-то изделий, стоимость перевозок и пр.);
x={x1,..xn} - варьируемые параметры;
g1(x), …, gm(x) - функции, которые задают ограничения на имеющиеся
ресурсы
Курс «Модели и методы анализа проектных решений»
Тема «Постановка задач линейного программирования и исследование их структуры»
2

3. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Среди известных разделов
математического
программирования наиболее
развитым и законченным
является линейное
программирование (ЛП).
Курс «Модели и методы анализа проектных решений»
Тема «Постановка задач линейного программирования и исследование их структуры»
3

4. ПРИМЕРЫ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

• Определение оптимального ассортимента.
Имеются р видов ресурсов в количествах а1, а2, …, аi, …, ap
и q видов изделий. Задана матрица А=||аik|| , где aik характеризует нормы расхода i-го ресурса на единицу k-го
изделия (k = 1, 2, …, q).
Эффективность
выпуска
единицы
k-го
изделия
характеризуется показателем ck, удовлетворяющим условию
линейности. Количество единиц k-го изделия, выпускаемых
предприятием, обозначим xk.
Определить план выпуска изделий (оптимальный
ассортимент), при котором суммарный показатель
эффективности принимает наибольшее значение.
Курс «Модели и методы анализа проектных решений»
Тема «Постановка задач линейного программирования и исследование их структуры»
4

5. ПРИМЕРЫ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Математическая модель задачи определения
оптимального ассортимента:
максимизировать
при ограничении
(1)
, i=1, 2, …, p.
Курс «Модели и методы анализа проектных решений»
Тема «Постановка задач линейного программирования и исследование их структуры»
(2)
5

6. ПРИМЕРЫ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

• Оптимальное распределение взаимозаменяемых ресурсов.
Имеются m видов взаимозаменяемых ресурсов а1, а2, …, аi, …,
am, используемых при выполнении n различных работ в объеме
b1, b2, …, bn.
Заданы числа , указывающие, сколько единиц j-й работы можно
получить из единицы i-го ресурса, а также cij – затраты при
изготовлении единицы j-го продукта из i-го ресурса.
Требуется распределить ресурсы по работам таким образом,
чтобы суммарная эффективность была наибольшей (или
суммарные затраты - наименьшими).
Курс «Модели и методы анализа проектных решений»
Тема «Постановка задач линейного программирования и исследование их структуры»
6

7. ПРИМЕРЫ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Данная задача называется общей распределительной задачей.
Количество единиц i-го ресурса, которое выделено для
выполнения работ j-го вида, обозначим xij.
Математическая модель задачи оптимального распределения
взаимозаменяемых ресурсов :
минимизировать
при ограничениях
(3)
, j=1, 2, …, n;
, i=1, 2, …, m.
(4)
(5)
Курс «Модели и методы анализа проектных решений»
Тема «Постановка задач линейного программирования и исследование их структуры»
7

8. ПРИМЕРЫ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

• Задача о смесях
Имеется р компонентов i=1, 2, …, p, при сочетании
которых в разных пропорциях получают различные
смеси.
В каждый компонент, а следовательно, и в смесь входит
q веществ. Количество k-го вещества k=1, 2, …, q,
входящее в состав единицы i-го компонента и в
состав единицы смеси, обозначим соответственно aik
и ak.
Курс «Модели и методы анализа проектных решений»
Тема «Постановка задач линейного программирования и исследование их структуры»
8

9. ПРИМЕРЫ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Полагают, что ak зависит от aik линейно, т. е. если смесь
состоит из x1 единиц первого компонента и x2 – единиц
второго компонента и т. д., то
Необходимо определить состав смеси, при котором
суммарная характеристика (цена, масса или
калорийность) окажется наилучшей.
Курс «Модели и методы анализа проектных решений»
Тема «Постановка задач линейного программирования и исследование их структуры»
9

10. ПРИМЕРЫ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Математическая модель задачи о смесях:
минимизировать
при условии
(6)
, k=1, 2, …,q.
Курс «Модели и методы анализа проектных решений»
Тема «Постановка задач линейного программирования и исследование их структуры»
(7)
10

11. ПРИМЕРЫ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

• Задача о раскрое материалов.
На раскрой поступает m различных материалов. Требуется
изготовить из них k разных комплектующих изделий в количествах,
пропорциональных b1, b2, …, bk (условие комплектности).
Пусть каждая единица j-го материала, j=1, 2, …, m, может быть
раскроена n различными способами, так что при использовании i-го
способа раскроя, i=1, 2, …, n, получится akij единиц k-го изделия.
Определить план раскроя, обеспечивающий максимальное
количество комплектов, если известно, что объем запаса j-го
материала равен aj единиц.
Курс «Модели и методы анализа проектных решений»
Тема «Постановка задач линейного программирования и исследование их структуры»
11

12. ПРИМЕРЫ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Количество единиц j-го материала, раскраиваемых i-м способом,
обозначим xij, а количество изготавливаемых комплектов изделий – х.
Математическая модель задачи о раскрое материала:
максимизировать х
при условиях
,
(8)
(9)
Курс «Модели и методы анализа проектных решений»
Тема «Постановка задач линейного программирования и исследование их структуры»
12

13. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

максимизировать
(10)
при условиях
(11)
и
(12)
Ограничения (12) - условия неотрицательности.
В данном случае все условия имеют вид неравенств.
Курс «Модели и методы анализа проектных решений»
Тема «Постановка задач линейного программирования и исследование их структуры»
13

14. ФОРМЫ ЗАДАНИЯ УСЛОВИЙ

• Смешанная форма - неравенства и равенства:
(13)
• Каноническая форма– строгие неравенства
(14)
Курс «Модели и методы анализа проектных решений»
Тема «Постановка задач линейного программирования и исследование их структуры»
14

15.

Курс «Модели и методы анализа проектных решений»
Тема «Постановка задач линейного программирования и исследование их структуры»
15

16. ДОПУСТИМОЕ МНОЖЕСТВО РЕШЕНИЯ ЗАДАЧИ

Курс «Модели и методы анализа проектных решений»
Тема «Постановка задач линейного программирования и исследование их структуры»
16

17.

СПАСИБО ЗА ВНИМАНИЕ
© ФГБОУ ВПО ИжГТУ имени М.Т. Калашникова, 2014
© Исенбаева Елена Насимьяновна, 2014