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

Содержание слайда: Формула, описывающая статистическую модель: Формула, описывающая статистическую модель: У=f(x1, X2, …, xn) Формула, описывающая межотраслевой баланс: Ах + у = Х

Содержание слайда: ПРЕДМЕТ, МЕТОД И ТЕОРЕТИЧЕСКИЕ ОСНОВЫ МЕТОДОВ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Вопросы: 1.1. Понятие и теоретические основы методов линейного программирования 1.2. Основные понятия и обозначения 1.3. Общая задача линейного программирования 1.4. Геометрическая интерпретация и графический способ решения простейших задач линейного программирования.

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

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

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

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

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

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

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

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

Содержание слайда: Поскольку на производство какого-либо продукта всегда затрачиваются некоторые ресурсы, то необходимо ввести общее обозначение для нормативов затрат ресурсов. Поскольку на производство какого-либо продукта всегда затрачиваются некоторые ресурсы, то необходимо ввести общее обозначение для нормативов затрат ресурсов. Обозначим норму затрат первого ресурса на единицу первого продукта через а11 , норму затрат первого ресурса на единицу второго продукта через a12, норму затрат второго ресурса на единицу первого продукта через a21 и т. п. В общем случае норма затрат i-го ресурса на единицу j-го продукта обозначим aij.

Содержание слайда:

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

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

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

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

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

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

Содержание слайда: Общая задача линейного программирования Заданы: линейная функция Z = C1X1 + C2X2 + . . . + CnXn min(max) и система линейных ограничений

Содержание слайда:

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

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

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

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

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

Содержание слайда: Нормативы затрат ресурсов, прибыльность проса и гречихи (в расчете на 1 ц) установлены

Содержание слайда: Обозначим через X1 – объем производства проса (ц), через Х2 объем производства гречихи (ц), запишем условия задачи в математическом виде:

Содержание слайда:

Содержание слайда: Рассмотрим первое неравенство: 0,07X1+0,05X2<=200. Рассмотрим первое неравенство: 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.

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

Содержание слайда: Прямая k, соответствующую второму неравенству: Прямая 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).

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

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

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

Содержание слайда: При необходимости координаты точки G можно определить точно. Для этого надо решить систему двух уравнений, каждое из которых соответствует тем линиям, на пересечении которых эта точка находится,— линиям k и l. При необходимости координаты точки 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.

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

Содержание слайда: Таким образом, при Х1 = 1740 и Х2=1565 второй ресурс используется также полностью. Таким образом, при Х1 = 1740 и Х2=1565 второй ресурс используется также полностью. А раз оба (первый и второй ресурсы) используются полностью и нормы замены одного вида производства на другой с точки зрения экономии в расходовании ресурсов противоположны, то улучшить программу производства и достичь еще большей прибыли не представляется возможным. Найденный вариант сочетания выращивания проса и гречихи является оптимальным и приводит к достижению максимальной величины прибыли, равной 12870 руб.