Предмет, метод и теоретические основы методов линейного программирования

Июль 31, 2022

Главная
Информатика
Предмет, метод и теоретические основы методов линейного программирования

Содержание

2. ПРЕДМЕТ, МЕТОД И ТЕОРЕТИЧЕСКИЕ ОСНОВЫ МЕТОДОВ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Вопросы: 1.1. Понятие и теоретические основы методов линейного
3. Интерес к фактическому применению МП возрос с 1947 г., когда крупный американский математик Дж. Данциг разработал
4. В сельскохозяйственном производстве круг задач очень широк. Многие известные отечественные и зарубежные математики и экономисты, специализирующиеся
5. Например, любой бухгалтерский или плановый баланс, состоящий, как известно, из двух частей: источников поступления средств и
6. Если мы разложим итоговую приходную и расходную части на их составляющие, то соотношения, естественно, не изменяются.
7. Пусть X1 обозначает запасы на начало года; Х2 – производство; Х3 – приобретение со стороны; Y1
8. Аналогичным образом можно составить и записать соотношения по всем остальным производственно-финансовым балансам. Если обозначить все позиции
9. Допустим, нам необходимо составить производственно-финансовый план хозяйства, причем такой, чтобы в результате его практической реализации хозяйство
10. Обозначим через Х1, Х2, ..., Хn множество неизвестных величин производственно-финансового плана, подлежащих определению, а через m
11. Поскольку на производство какого-либо продукта всегда затрачиваются некоторые ресурсы, то необходимо ввести общее обозначение для нормативов
13. Экономически условия, записанные в виде системы, интерпретируются так: затраты любого из m видов ресурса на производство
14. Целевая установка данной задачи – достижение максимальной прибыли. Если допустить, что единица первого продукта приносит некоторую
15. Условия задачи, объединенные вместе, характеризуют поставленную задачу в ее математической форме. В задачах линейного программирования все
16. Например, неравенство вида 0,07X1+0,05X2 в задаче характеризует тот факт, что площадь под просо и гречиху не
17. Поскольку в задачах линейного программирования отыскивается оптимальное решение, то в них необходимо кроме условий (ограничений) задачи
18. Технико-экономические коэффициенты – это есть соответствующие нормативы, т. е. те числовые коэффициенты, которые вводятся в левые
19. Общая задача линейного программирования Заданы: линейная функция Z = C1X1 + C2X2 + . . .
21. Определение 1. Задача, в которой требуется найти такие неотрицательные значения Х1, Х2, ..., Хn, которые удовлетворяют
22. Определение 3. Задача с условиями вида: Z =СХ max, AX =0 называется симметричной задачей линейного программирования.
23. Определение 5. Набор чисел X=(X1, Х2, …, Хn), удовлетворяющих ограничениям задачи линейного программирования, называется ее планом.
24. Геометрическая интерпретация и графический способ решения простейших задач линейного программирования. Применяется в основном при решении задач
25. Задача. При анализе перспективного плана развития хозяйства обнаружилось, что в нем недоиспользуется 200 га пашни. Наиболее
26. Нормативы затрат ресурсов, прибыльность проса и гречихи (в расчете на 1 ц) установлены
27. Обозначим через X1 – объем производства проса (ц), через Х2 объем производства гречихи (ц), запишем условия
29. Рассмотрим первое неравенство: 0,07X1+0,05X2 Разрешим его относительно Х2 (можно и относительно X1); знак Итак, если X1=1000,
30. Если свободный член 200 этого уравнения сокращать в соответствии с условием задачи, то линии, параллельные 1,
31. Прямая k, соответствующую второму неравенству: 0,1Х1+0,4Х2 = 800; X1 + 4X2 =8000; X1 = 8000 –
32. Поскольку третье неравенство отражает ограниченность объема производства гречихи (Х2>=1000) снизу (не менее 1000 ц), то строим
33. Построив линии, соответствующие уравнениям задачи, и определив направление движения семейства параллельных прямых в соответствии с изменением
34. Рассматривая график, видим, что точке G соответствуют значения X1 1700, Х2 1600. Итак, максимальная величина прибыли
35. При необходимости координаты точки G можно определить точно. Для этого надо решить систему двух уравнений, каждое
36. Легко убедиться, что именно в этом случае, то есть при X1=1740 и Х2=1565, прибыль будет максимальной.
38. Скачать презентацию

Слайд 2

ПРЕДМЕТ, МЕТОД И ТЕОРЕТИЧЕСКИЕ ОСНОВЫ МЕТОДОВ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Вопросы:
1.1. Понятие и теоретические

основы методов линейного программирования
1.2. Основные понятия и обозначения
1.3. Общая задача линейного программирования
1.4. Геометрическая интерпретация и графический способ решения простейших задач линейного программирования.

Слайд 3

Интерес к фактическому применению МП возрос с 1947 г., когда крупный

американский математик Дж. Данциг разработал симплексный (симплекс) – метод для решения общей задачи линейного программирования, хотя первая работа в этой области принадлежит Л. В. Канторовичу.
Линейное программирование находит широкое применение в экспериментальных и практических расчетах, в анализе и планировании сельскохозяйственного производства.

Слайд 4

В сельскохозяйственном производстве круг задач очень широк. Многие известные отечественные и

зарубежные математики и экономисты, специализирующиеся на применении экономико-математических методов в сельскохозяйственном производстве, даже считают, что сельское хозяйство является наиболее перспективной отраслью применения линейного программирования. Множество экономических задач оптимального использования (распределения) ресурсов в сельском хозяйстве вписывается в рамки моделей линейного программирования.
Специфические особенности сельскохозяйственного производства, такие, как его сезонность, строгая последовательность технологических процессов и т. п., можно учесть при разработке соответствующих линейных моделей.
Первое и основное условие задач, сводящихся к задачам линейного программирования – это допущение линейности соотношений – условий задачи.

Слайд 5

Например, любой бухгалтерский или плановый баланс, состоящий, как известно, из

двух частей: источников поступления средств и путей их расходования.
В так называемой приходной части показываются все источники поступления: запасы на начало года, производство, приобретение со стороны и т. п.,
а в расходной – пути распределения: израсходовано в процессе производства, продано на сторону, сдано государству, заложено в страховой фонд и т. п.
Если обозначить приходную часть через X,
а расходную через Y,
то в общем случае соотношение расходной и приходной частей баланса можно выразить посредством равенства или неравенства:
X=Y, или X>Y, или X В первом случае приходная и расходная части полностью сбалансированы, то есть баланс сходится (закрыт).
Во втором и третьем случаях баланс не сходится. Причем во втором случае приходная часть больше расходной (сальдо положительное), а в третьем случае – наоборот.

Слайд 6

Если мы разложим итоговую приходную и расходную части на их составляющие,

то соотношения, естественно, не изменяются. В этом случае как левая, так и правая части будут обозначать некоторый набор, некоторую сумму величин.

Слайд 7

Пусть X1 обозначает запасы на начало года; Х2 – производство; Х3

– приобретение со стороны; Y1 – то, что израсходовано в процессе производства; Y2 — то, что продано; Y3 – то, что сдано государству; Y4 — то, что заложено в страховой фонд. Теперь можно записать, что Х1 + Х2 + Х3 = (или >, или <) Y1+Y2+Y3+Y4.
В данном случае мы получили уже более развернутое линейное уравнение или неравенство (в зависимости от знака между его частями).

Слайд 8

Аналогичным образом можно составить и записать соотношения по всем остальным производственно-финансовым

балансам. Если обозначить все позиции любого баланса, как расходной, так и приходной частей, через n, то при условии, что таких балансов m, у нас получится своеобразная система линейных соотношений размерностью (m*n).

Слайд 9

Допустим, нам необходимо составить производственно-финансовый план хозяйства, причем такой, чтобы в

результате его практической реализации хозяйство смогло бы иметь наивысшую массу прибыли.
Т.е., необходимо определить, что и в каком количестве хозяйству следует производить, как и каким образом распределить ресурсы (то есть оптимизировать все балансовые соотношения), чтобы достичь наивысшего эффекта.
Такая постановка задачи, имеющая непосредственное практическое значение, может быть формализована в виде системы линейных соотношений, сведена к задаче линейного программирования и решена с помощью одного из методов линейного программирования.
Сведем данную экономическую задачу к математической и запишем все ее условия с помощью линейных уравнений и неравенств.

Слайд 10

Обозначим через Х1, Х2, ..., Хn множество неизвестных величин производственно-финансового плана,

подлежащих определению,
а через m – количество всевозможных балансовых соотношений (ограничений на использование земельных угодий, трудовых ресурсов, техники, кормов, удобрений и т. п.).
Наличные ресурсы, то есть все те ресурсы, которые к плановому периоду будут находиться в распоряжении хозяйства, обозначим соответственно через В1, В2, ..., Вn.
Иными словами, мы итоговую приходную часть каждого баланса обозначили через некоторую величину, которую закодировали как
В1, В2 и т. д.

Слайд 11

Поскольку на производство какого-либо продукта всегда затрачиваются некоторые ресурсы, то необходимо

ввести общее обозначение для нормативов затрат ресурсов.
Обозначим норму затрат первого ресурса на единицу первого продукта через а11 , норму затрат первого ресурса на единицу второго продукта через a12,
норму затрат второго ресурса на единицу первого продукта через a21 и т. п.
В общем случае норма затрат i-го ресурса на единицу j-го продукта обозначим aij.

Слайд 12

Слайд 13

Экономически условия, записанные в виде системы, интерпретируются так:
затраты любого

из m видов ресурса
на производство всех n видов продуктов не должны превышать объема этого ресурса, имеющегося в хозяйстве на начало планового периода.
При этом естественно допустить, что производство любого продукта не может быть величиной отрицательной, то есть:
(X1, Х2, ..., Хn) >= 0

Слайд 14

Целевая установка данной задачи – достижение максимальной прибыли.
Если допустить, что

единица первого продукта приносит некоторую величину прибыли, равную C1
второго продукта – C2 и т.д., то условие достижения максимальной прибыли ( Z ) можно записать так:
Z=(C1X1 + C2X2 + … + CjXj + .. . + CnXn) –>max

Слайд 15

Условия задачи, объединенные вместе, характеризуют поставленную задачу в ее математической форме.

В задачах линейного программирования все коэффициенты при неизвестных считаются постоянными величинами.
Все ограничения (условия) должны быть представлены только в виде линейных уравнений и неравенств.

Слайд 16

Например, неравенство вида
0,07X1+0,05X2<=200
в задаче характеризует тот факт, что площадь

под просо и гречиху не должна превышать 200 га.
Возможно и наоборот, т. е.
0,07X1 + 0,05X2>=200,
т. е. площадь под этими культурами должна быть не менее 200 га.
Разумеется, в одной и той же задаче возможно лишь одно из таких ограничений.
Можно ввести условие Х2>1000, т. е. производство гречихи должно быть не менее 1000 ц.

Слайд 17

Поскольку в задачах линейного программирования отыскивается оптимальное решение, то в них

необходимо кроме условий (ограничений) задачи вводить и так называемый показатель качества этого решения — целевую функцию (целевую установку или целевой функционал).
Неизвестными в задачах линейного программирования, как правило, являются объемы производимых продуктов, наличие конкретных видов кормов в рационе, приобретаемая техника, удобрения и т. п.
Они должны быть положительными числами, т. е. Xj>=0.

Слайд 18

Технико-экономические коэффициенты – это есть соответствующие нормативы, т. е. те числовые

коэффициенты, которые вводятся в левые части ограничений задачи при неизвестных.
Объемы (размеры) ограничений могут характеризовать объемы конкретных ресурсов (Bi) и т. п. Причем объемы (размеры) ограничений должны быть неотрицательными, т. е. (Aj, Bi>0).
Коэффициенты целевой функции могут иметь различное содержание. В основном они являются стоимостными оценками (прибыль, цена реализации и себестоимость в расчете на единицу продукции). Они также могут характеризовать урожайность, продуктивность, трудоемкость продукции, тонно-километры, машино-смены и т. п.
Оценки целевых функций могут иметь как положительные, так и отрицательные и нулевые значения.
Например, если задача линейного программирования решается на максимум прибыли, то оценки рентабельных продуктов в целевую функцию вводятся с положительными значениями (прибыль), оценки нерентабельных продуктов – с отрицательными значениями (убыток), а те продукты, рентабельность которых равна нулю – естественно с нулевыми коэффициентами.

Слайд 19

Общая задача линейного программирования Заданы: линейная функция Z = C1X1 + C2X2 + .

. . + CnXn min(max) и система линейных ограничений

Слайд 20

Слайд 21

Определение 1. Задача, в которой требуется найти такие неотрицательные значения Х1,

Х2, ..., Хn, которые удовлетворяют системе ограничений и обращают в минимум (максимум) линейную форму, называется общей задачей линейного программирования. Задача может быть записана и в других формах (векторной, матричной, табличной).
Определение 2. Задача с условиями вида Z = CX min, АХ>=В, Х>=0 называется стандартной задачей линейного программирования.

Слайд 22

Определение 3. Задача с условиями вида: Z =СХ max, AX<=B, Х>=0

называется симметричной задачей линейного программирования.
Определение 4. Задача с условиями вида Z = CX min (max), AX=B, X>=0 называется канонической задачей линейного программирования.

Слайд 23

Определение 5. Набор чисел X=(X1, Х2, …, Хn), удовлетворяющих ограничениям задачи

линейного программирования, называется ее планом.
Определение 6. План Х=(Х1, Х2, …, Хn), обращающий в максимум (минимум) линейную форму (1.2.1), называется оптимальным планом или решением задачи линейного программирования.
Определение 7. Задача линейного программирования называется допустимой, если множество М планов задачи не пусто (есть хотя бы один допустимый план), и разрешимой, если не пусто множество М оптимальных планов этой задачи (есть хотя бы один оптимальный план).

Слайд 24

Геометрическая интерпретация и графический способ решения простейших задач линейного программирования.
Применяется в

основном при решении задач двумерного пространства и только некоторых задач трехмерного пространства, поскольку задачу размерности больше трех графически изобразить невозможно.
Таким образом, графический метод решения применяется для решения таких задач линейного программирования, которые содержат, как правило, две переменные.
Достоинство метода - наглядность

Слайд 25

Задача. При анализе перспективного плана развития хозяйства обнаружилось, что в нем

недоиспользуется 200 га пашни. Наиболее эффективными в хозяйстве являются две культуры – просо и гречиха, рентабельность их одинаковая. Хозяйство имеет возможность приобрести сверх плана 800 ц минеральных удобрений (в пересчете на действующее вещество) при условии, что сдаст дополнительно к ранее планируемому объему 1000 ц гречихи.
Требуется так распределить имеющиеся ресурсы между этими культурами, чтобы хозяйство имело от их производства наивысшую прибыль.

Слайд 26

Нормативы затрат ресурсов, прибыльность проса и гречихи (в расчете на 1

ц) установлены

Слайд 27

Обозначим через X1 – объем производства проса (ц), через Х2 объем производства

гречихи (ц), запишем условия задачи в математическом виде:

Слайд 28

Слайд 29

Рассмотрим первое неравенство: 0,07X1+0,05X2<=200.
Разрешим его относительно Х2 (можно и относительно

X1);
знак <= мы можем заменить на =, поскольку это допускается по условию задачи. Получим Х2=4000–1,4Х1. Придавая X1 произвольное значение (в рамках допустимости), получим некоторые значения Х2.
Итак, если X1=1000, то Х2=2600, а если X1=2000, то Х2=1200. мы получили две точки А и В с координатами А(1000, 2600), В(2000, 1200). Известно, что через точки в пространстве можно провести прямую и притом только одну. Нанесем эти точки на трафик и проведем через них прямую 1, соответствующую уравнению 0,07X1+0,05X2=200.

Слайд 30

Если свободный член 200 этого уравнения сокращать в соответствии с условием

задачи, то линии, параллельные 1, будут находиться левее ее и в этом отношении проведенная нами линия является предельной, как предельна (максимально допустима) и сама величина (200) площади пашни.
На графике направление движения семейства линий при уменьшении площади пашни показано стрелочкой

Слайд 31

Прямая k, соответствующую второму неравенству:
0,1Х1+0,4Х2 = 800;
X1 + 4X2 =8000;
X1 =

8000 – 4X2
При Х2=1500; X1=2000, С(2000; 1500);
При Х2 = 2000; X1=0, D(0; 2000).

Слайд 32

Поскольку третье неравенство отражает ограниченность объема производства гречихи (Х2>=1000) снизу (не

менее 1000 ц), то строим линию, отвечающую нижнему пределу этого ограничения, то есть соответствующую уравнению Х2=1000. Эта прямая проходит параллельно оси OX1 через точку Е (0, 1000).
Данная линия (обозначим ее m) лимитирует сочетание гречихи и проса, то есть ограничивает область допустимых решений так же, как и линия ОХ2.
Итак, возможное сочетание производства проса и гречихи будет находиться в секторе, ограниченном линиями ЕХ2 и EF, причем (искомый оптимум может находиться на этих линиях или правее линии ОХ2 и выше линии EF.

Слайд 33

Построив линии, соответствующие уравнениям задачи, и определив направление движения семейства параллельных

прямых в соответствии с изменением свободных членов неравенств, найдем область допустимых значений, в которой возможен искомый оптимум. Эта область ограничена линиями: 1, k, m, OX2 и на графике представляет собой четырехугольник с вершинами EFGD.
Определив область существования возможных сочетаний производства проса и гречихи, перейдем к графическому изображению целевой функции — линии, соответствующей критерию оптимальности:

Слайд 34

Рассматривая график, видим, что точке G соответствуют значения X1 1700, Х2

1600. Итак, максимальная величина прибыли достигается в том случае, если хозяйство будет производить 1700 ц проса и 1600 ц гречихи. Прибыль в этом случае составит порядка 13 тыс. руб.
(2*1700)+ (6*1600)=13000.

Слайд 35

При необходимости координаты точки G можно определить точно. Для этого надо

решить систему двух уравнений, каждое из которых соответствует тем линиям, на пересечении которых эта точка находится,— линиям k и l.
0,1Х1 + 0,4Х2=800;
0,07Х1 + 0,05X2=200.
Решив эту систему любым из известных методов, определим точное значение координат точки G. Они будут соответственно равны: X1=1740, Х2=1565.
Прибыль в этом случае составит 12870 руб.:
(2*1740+6*1565)=12870.

Слайд 36

Легко убедиться, что именно в этом случае, то есть при X1=1740

и Х2=1565, прибыль будет максимальной. Попробуем доказать это экономически. Рассмотрим, все ли ресурсы и в каком объеме будут использованы при таком сочетании посевов.
200–(0,07*1740+0,05*1565)=0
(0,1*1740)+(0,4*1565)=800.