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

Методы решения задач линейного программирования

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

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

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

Постановка практической задачи ЛП включает следующие основные этапы:

· определение показателя эффективности, переменных задачи,

· задание линейной целевой функции S(x), подлежащей минимизации или максимизации,

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

Дана система линейных уравнений с n неизвестными:

a₁₁ x₁ + a₁₁ x₂ + …… + a₁₁ x_n = b₁,

a₂₁ x₁ + a₂₂ x₂ + …… + a_2n x_n = b₂,

a_m1 x₁ + a_m2 x₂ + …… + a_mn x_n = b_m,

Требуется найти такое неотрицательное решение системы

при котором функция f принимает наименьшее значение.

Уравнения (1.1) называют системой ограничений данной задачи; функцию f — целевой функцией (или линейной формой).

Методы решения задач линейного программирования

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

Применение симплекс-метода для задачи линейного программирования предполагает предварительное приведение ее формальной постановки к канонической форме с n неотрицательными переменными: (X1. Xn), где требуется минимизация линейной целевой функции при m линейных ограничениях типа равенств. Среди переменных задачи выбирается начальный базис из m переменных, для определенности (X1. Xm), которые должны иметь неотрицательные значения, когда остальные (n-m) свободные переменные равны 0. Целевая функция и ограничения равенства преобразуются к диагональной форме относительно базисных переменных, переменных, где каждая базисная переменная входит только в одно уравнение с коэффициентом 1:

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

Симплекс-таблица

1	X1	X2	.	Xm	Xm+1	.	Xn
X0	A0,0	0	0	.	0	A0,m+1	.	A0,n
X1	A1,0	1	0	.	0	A1,m+1	.	A1,n
X2	A2,0	0	1	.	0	A2,m+1	.	A2,n
.	.	.	.	.	.	.	.	.
Xm	Am,0	0	0	.	1	Am,m+1	.	Am,n

Верхняя строка симплекс-таблицы представляет целевую функцию задачи. Каждая строка симплекс-таблицы, кроме первой, соответствует определенному ограничению-равенству задачи. Свободные члены ограничений составляют крайний левый столбец таблицы. Слева от таблицы записаны текущие базисные переменные (X₁. X_m). Сверху от таблицы приведен набор всех переменных задачи, где X_m+1. X_n — свободные переменные задачи.

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

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

6.2.2. Геометрический метод

Применяется для задач с двумя переменными. Метод решения состоит в следующем:

На плоскости Ох₁х₂ строятся прямые, которые задают соответствующие ограничения:

a₁₁ x₁ + a₁₁ x₂ + …… + a₁₁ x_n = b₁,

Находим множество всех точек х₁,х₂, удовлетворяющим всем неравенствам. Такое множество называется областью допустимых решений. Строим вектор и перемещаем линию уровня, который задается уравнением: с₁х₁+с₂х₂ = const в направлении вектора до последней точки пересечения с ОДР. Эта точка и дает решение задачи L_max = значению L в этой точки

Транспортная задача.

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

Имеется ряд пунктов производства с объемами производства в единицу времени (месяц, квартал), равными соответственно и пункты потребления потребляющие за тот же промежуток времени соответственно продукции. В случае, если решается закрытая (сбалансированная) задача, сумма объемов производства на всех пунктах-поставщиках равна сумме объемов потребления на всех пунктах-получателях:

Кроме того, известны затраты по перевозке единицы продукта от каждого поставщика к каждому получателю — эти величины обозначаются В качестве неизвестных величин выступают объемы продукта, перевозимого из каждого пункта производства в каждый пункт потребления, соответственно обозначаемые .

Тогда наиболее рациональным прикреплением поставщиков к потребителям будет такое, при котором суммарные затраты на транспортировку будут наименьшими:

При этом каждый потребитель получает нужное количество продукта:

и каждый поставщик отгружает весь произведенный им продукт:

Как и во всех подобных случаях, здесь также оговаривается неотрицательность переменных: поставка от какого-то пункта производства тому или иному пункту потребления может быть равна нулю, но отрицательной, т. е. следовать в обратном направлении, быть не может.

Строки транспортной таблицы соответствуют пунктам производства (в последней клетке каждой строки указан объем запаса продукта ai), а столбцы — пунктам потребления (последняя клетка каждого столбца содержит значение потребности bj). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о перевозке из i-го пункта в j-й: в левом верхнем углу находится цена перевозки единицы продукта, а в правом нижнем — значение объема перевозимого груза для данных пунктов. Клетки, которые содержат нулевые перевозки (x_i,j=0), называют свободными, а ненулевые — занятыми (x_i,j>0).

Несбалансированную (открытую) транспортную задачу приводят к виду, показанному выше, искусственно: в модель вводятся так называемые фиктивный поставщик или фиктивный потребитель, которые балансируют спрос и потребление.

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

Производственно-транспортная задача

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

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

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:

Самое популярное на сайте:

Международные организации и союзы Международные организации — одна из важнейших форм многостороннего сотрудничества между государствами.
Задача № 3 В терапевтическом отделении пациент, страдающий гипертонической болезнью, пожаловался медсестре на то, что у него появилась одышка.
Воздействие негативных факторов на человека и среду обитания Человек живет, непрерывно обмениваясь энергией с окружающей средой, участвуя в круговороте веществ в биосфере.
Классификация питательных сред При приготовлении питательных сред необходимо учитывать потребность культивируемых микроорганизмов в различных элементах питания.
Мифологическое мировоззрение Мифологическое мировоззрение было древнейшей формой познания мира, космоса, общества и человека.

Источник

Н.А. Курганова

Н.А. Курганова. Основные методы решения задач линейного программирования: Учебное пособие. – Омск, 2011. – , с.

Учебное пособие составлено с учетом современных требований к подготовке студентов, обучающихся по специальностям «Информатика», «Математика», «Математические методы в экономике». Материалы, представленные в пособии, являются базовыми для изучения учебных курсов «Исследование операций и методы оптимизации», «Математические методы в экономике» и др.

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

Тема 1. Постановка задачи линейного программирования. Геометрический метод решения задач линейного программирования. Основные понятия, теоремы, следствия. 6

1.1. Постановка задачи линейного программирования 6

1.2. Геометрический метод решения задач ЛП 9

Лабораторная работа №1. Геометрическое решение задачи ЛП при помощи математического пакета MathCad 11

Лабораторная работа №2. Геометрическое решение задачи ЛП при помощи математического пакета Maple 17

Задания для самостоятельной работы 26

Лабораторная работа №3. Решение оптимизационных задач в системах MathCad, Maple, Excel, в специализированном пакете SimplexWin. 29

Задания для самостоятельной работы 43

Тема 2. Симплекс-метод. 45

2.1. Табличный симплекс-метод (в чистом виде) 46

2.2. Табличный симплекс метод. Метод искусственного базиса (М-метод) 50

Лабораторная работа №4. Реализация пошагового алгоритма решения задачи линейного программирования табличным симплекс-методом средствами Excel при выполнении всех условий 53

Лабораторная работа №5. Реализация пошагового алгоритма решения задачи линейного программирование методом искусственного базиса (М-методом) средствами Excel 62

Задания для самостоятельной работы 68

Библиографический список 73

Введение

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

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

Приведенные в пособии темы охватывают такие методы решения задач линейного программирования, как геометрический метод и симплекс-метод. Эти методы могут рассматриваться при изучении таких дисциплин, как «Исследование операций и методы оптимизации», «Методы оптимизации», «Экономико-математические методы и модели».

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

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

Источник