ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
ПРИМЕРЫ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
ПРИМЕРЫ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
ПРИМЕРЫ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
ПРИМЕРЫ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
ПРИМЕРЫ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
ПРИМЕРЫ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
ПРИМЕРЫ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
ПРИМЕРЫ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
ПРИМЕРЫ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
ФОРМЫ ЗАДАНИЯ УСЛОВИЙ
ДОПУСТИМОЕ МНОЖЕСТВО РЕШЕНИЯ ЗАДАЧИ
2.20M
Category: programmingprogramming

Постановка задач линейного программирования и исследование их структуры. Тема 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
English     Русский Rules