Тема: Прикладные модели, относящиеся к задачам линейного програм­мирования. Задача нахождения оптимального плана. Транспортная задача. Задача о назначениях.

Задача нахождения оптимального производственного плана. Для изготовления различных видов изделий используются разные ресурсы. Общие запасы каждого ресурса, количество ресурсов каждого вида, прибыль, получаемая от реализации одного изделия определённого вида заданы. Нужно составить план производства изделий, обеспечивающий максимальную суммарную прибыль от их реализации.

Этапы построения экономико - математической модели:

1. целью является максимизация прибыли;

2. для формулировки задачи вводим следующие условные обозначения:

n – число различных видов изделий; m – число различных типов ресурсов;

b_i - запас ресурса i – го типа, ; a_ij – количество ресурсов i-го типа, необходимых для изготовления одного изделия j-го вида, , ; p_j – прибыль от реализации одного изделия j-го вида;

3. управляющие переменные x_j, - число изделий j-го вида;

4. о граничения задачи – ограничения по ресурсам и условия неотрицатель­ности управляющих переменных.

Постановка транспортной задачи: задано m поставщиков продукции одного вида и n потребителей, предложение каждого i-го поставщика составляет a_i – единиц, ; спрос каждого j-го потребителя - b_j единиц, ; тарифы перевозок равны с_ij, , . Найти объёмы перево­зок для каждой пары «Поставщик - потребитель» так, чтобы 1) мощности всех поставщиков были реализованы, 2) спросы всех потребителей были удовлетворены, 3) суммарные затраты на перевозку были бы минимальными. В качестве переменных в данной задаче выступают x_ij – количество продукции, перевозимой от i-го поставщика j-му потребителю , . Формальная запись транспортной задачи:

Методы нахождения начального решения транспортной задачи: метод «северо-западного угла», метод минимального элемента, метод Фогеля. Нахождение оптимального плана транспортной задачи. Метод потенциалов.

Общая формулировка задачи о назначениях: имеется n работ и n кандидатов для их выполнения. Затраты i-го кандидата на выполнение j-й работы равны с_ij (i, ). Каждый кандидат может быть назначен только на одну работу, а каждая работа может быть выполнена только одним кандидатом. Требуется найти назначение кандидатов на работы, при котором суммарные затраты на выпол­нение работ минимальны. Пусть x_ij – переменная, значение которой равно 1, если i-й кандидат выполняет j-ю работу и 0 – в противном случае. Тогда условие, что кандидат выполняет только одну работу имеет вид: . Условие о том, что каждая работа может выполняться только одним кандидатом можно представить в виде: .

Математическая модель данной задачи

выглядит следующим образом:

Методы решения задачи о назначениях: симплекс – метод, метод потенциалов, венгерский метод, пакет MS Excel «Поиск решения». Алгоритм венгерского метода решения задачи о назначениях. Применение рассмотренного алгоритма для решения задач о назначениях произвольной размерности.

---

---

Смотрите также файлы

• 5.3. Симплекс-метод.docx

• 5.2. Сведения о теоремах линейного программирования.docx

• 5.1. Математическая постановка и методы решения задач линейного программирования.docx

• 4.2. Принципы и подходы к построению математических моделей. Этапы построения математических моделей.docx

• 4.1. Классификация математических моделей.docx