Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МОДЕЛИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

No description
by

Helen Ya

on 18 December 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МОДЕЛИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

- это набор математических методов и приемов решения задачи оптимального распределения имеющихся ограниченных ресурсов (денег, материалов, времени и т.п.) для достижения определенной цели (максимума прибыли или минимума издержек).
Формулировка задачи
Глава 1.
Математическое программирование
Линейное программирование
Подготовила студентка 4 курса Ячнева Е.
Минск, 2014
Глава 2. Способы решения задачи линейного программирования
Глава 1. Решение экономико-математических задач методами линейного программирования (ЛП)
1.1 Линейное программирование
1.2 Формулировка задачи
1.3. Методы линейного программирования
1.3.1. Задача о составлении смеси
1.3.2. Задача планирования производства
Глава 2. Способы решения задачи линейного программирования
2.1. Экономико-математическая модель задачи производственного планирования
2.1.1 Пример построения экономико-математической модели
задачи производственного планирования
2.2. Графический способ решения ЗЛП
2.3. Решение ЗЛП симплекс-методом

В данной главе на примере решения простой задачи производственного
планирования рассмотрены следующие два способа решения ЗЛП: графический и симплекс-метод.

ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МОДЕЛИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Содержание
Математическое программирование [mathematical prog­ramming] — (см. также Оптимальное программирование) — раздел математики, который «… изучает методы решения задач на нахождение экстремума функций (показателя качества решения) при ограничениях в форме уравнений и неравенств».

Оно объединяет различные математические методы и дисциплины исследования операций:

линейное программирование
,
нелинейное программирование,
динамическое программирование,
выпуклое программирование,
геометрическое программирование,
целочисленное программирование и др.
Джордж Данциг

Леонид Витальевич
Канторович
Методы линейного программирования
Наиболее распространенным методом решения задач линейного программирования является так называемый
симплекс-метод
, разработанный Дж. Данцигом, а наиболее эффективным из известных - метод
эллипсоидов
. В простейшем случае, когда число переменных равно двум, удобен простой и наглядный
графический способ
.
Другой важный класс линейных задач образуют задачи, сводимые к
системам линейных уравнений
, - это линейные задачи, ограничения в которых имеют характер равенств.
Эффективное применение линейного программирования достигается при
решении следующих общих классов задач

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

2)
задачи планирования производства
, цель которых подбор наиболее
выгодной производственной программы выпуска одного или нескольких видов продукции при использовании некоторого числа ограниченных источников сырья;

3)
задачи распределения товаров
, цель которых состоит в том, чтобы
организовать доставку товаров от некоторого числа поставщиков к некоторому числу потребителей так, чтобы оказались минимальными либо расходы по этой доставке, либо время, либо некоторая комбинация того и другого. В простейшем случае это задача о перевозках (транспортная задача).
Рассматриваются и комбинированные задачи (например, в случае, когда
какой-то товар производится в разных местах, задачи производства и распределения объединяют в единую модель).

Задача о составлении смеси
Задача № 1. Металлургическому комбинату требуется уголь с содержанием фосфора не более 0,03 % и с долей зольных примесей не более 3,25 %. Комбинат закупает три сорта угля, условно обозначенных A, B и С, с известным содержанием примесей. В какой пропорции нужно смешивать сорта угля A, B и C, чтобы полученная смесь удовлетворяла ограничениям на содержание примесей и имела минимальную цену?
Экономико-математическая модель задачи производственного планирования
при которых целевая функция задачи (прибыль от реализации произведенной продукции) принимает максимальное значение
Предыдущие выражения можно записать в краткой форме:

Другим кратким способом записи выражений является следующая матричная форма:

вектор ресурсных ограничений
технологическая матрица;

вектор-план

Разновидностью матричной формы записи математической модели задачи является
векторная
форма
где CX - скалярное произведение векторов

векторы
состоят соответственно из коэффициентов при переменных и свободных членов.

Задача
при ограничениях

где x1 и x2 - количество единиц продукции P1 и P2.

Так как в математической модели задачи использованы только две переменные x1 и x2 , ее можно решить графически.
Графический способ решения ЗЛП
Запись математических выражений, представляющих целевую функцию и ограничения, в виде равенств (уравнений).
Построение на графике прямых для уравнений, соответствующих ограничениям.
Определение области допустимых решений (ОДР) для задачи.
Построение на графике прямой, соответствующей целевой функции.
Параллельный перенос (перемещение) прямой, построенной для целевой функции, в одну из крайних точек ОДР для получения оптимального решения.

Представим каждое из ограничений (3.13)-(3.17) в виде равенства (уравнения) и получим для них по паре точек, через которые проведем на графике отрезки прямых.

ОДР задачи представляет собой выпуклый пятиугольник ABCDE
Уравнение для целевой функции -
Оптимальный план для данной задачи составит 3 единицы продукции P1 и 2 единицы продукции P2 , от реализации которых предприятие получит максимум прибыли, равный 17 денежным единицам
Оптимальное решение задачи производственного планирования найдено
1. На сколько можно увеличить запас некоторого вида сырья для улучшения полученного оптимального плана?
2. На сколько можно снизить запас некоторого вида сырья при сохранении полученного оптимального плана?
3. Увеличение запасов какого вида сырья наиболее выгодно?
4. Каков диапазон изменения того или иного коэффициента целевой
функции, при котором не происходит изменение оптимального решения?


Анализ его чувствительности к изменениям исходных данных модели.
Для ответа на поставленные вопросы, анализируем рисунок
Решение задачи линейного программирования симплекс-методом
1) способ определения какого-либо первоначального допустимого базисного решения задачи;
Симплекс-метод
- универсальный метод решения ЗЛП, разработанный в 1949 г. американским математиком Дж. Данцигом. В его основе лежит идея последовательного улучшения полученного решения, для реализации которого необходимы:

2) правило перехода к лучшему (по крайней мере, не худшему) решению;
3) критерий проверки оптимальности найденного решения.
Пример решения задачи производственного планирования симплекс-методом
Преобразуем с помощью дополнительных переменных неравенства в уравнения
Получим систему ограничений в виде:
Для нахождения первоначального базисного решения разобьем переменные на две группы - основные и не основные (вспомогательные).
ШАГ
В системе уравнений (3.18) выразим основные переменные через вспомогательные, т.е. получим следующую систему уравнений:

ШАГ
Выразим новые основные переменные через новые вспомогательные переменные, начиная с разрешающего уравнения:

ШАГ
В результате преобразований (3.26) - (3.28) получаем следующую систему уравнений:
Full transcript