Методы решения задач линейного программирования
Линейное программирование — область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между переменными.
Программирование в управлении можно представить как процесс распределения ресурсов. Существует ряд различных методов, основанных на идеях математического программирования, однако, наиболее широкое применение нашел метод линейного программирования.
Применение методов линейного программирования актуально в сегодняшнее время, так как использование математических моделей является важным направлением совершенствования планирования и анализа деятельности компании. Представление данных в виде математической модели позволяет конкретизировать информацию, создавать и моделировать варианты, выбирать оптимальные решения.
Постановка практической задачи ЛП включает следующие основные этапы:
· определение показателя эффективности, переменных задачи,
· задание линейной целевой функции S(x), подлежащей минимизации или максимизации,
Приведем сейчас общую математическую формулировку основной задачи линейного программирования.
Дана система линейных уравнений с n неизвестными:
a11 x1 + a11 x2 + …… + a11 xn 
= 
b1,
a21 x1 + a22 x2 + …… + a2n xn = b2,
am1 x1 + am2 x2 + …… + amn xn = bm,
Требуется найти такое неотрицательное решение системы
при котором функция 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 |
Верхняя строка симплекс-таблицы представляет целевую функцию задачи. Каждая строка симплекс-таблицы, кроме первой, соответствует определенному ограничению-равенству задачи. Свободные члены ограничений составляют крайний левый столбец таблицы. Слева от таблицы записаны текущие базисные переменные (X1. Xm). Сверху от таблицы приведен набор всех переменных задачи, где Xm+1. Xn — свободные переменные задачи.
Преобразования таблицы надо производить до тех пор, пока не будет получена симплекс-таблица, которая одновременно является прямо и двойственно допустимой.
Данный метод получил широкое распространение и большую популярность по сравнению с другими подходами, так как крайне редко на практике встречаются задачи трудные для симплекс-метода.
6.2.2. Геометрический метод
Применяется для задач с двумя переменными. Метод решения состоит в следующем:
На плоскости Ох1х2 строятся прямые, которые задают соответствующие ограничения:
a11 x1 + a11 x2 + …… + a11 xn = b1,
Находим множество всех точек х1,х2, удовлетворяющим всем неравенствам. Такое множество называется областью допустимых решений. Строим вектор 
и перемещаем линию уровня, который задается уравнением: с1х1+с2х2 = const в направлении вектора 
до последней точки пересечения с ОДР. Эта точка и дает решение задачи Lmax = значению L в этой точки
Транспортная задача.
Одна из наиболее распространенных задач математического программирования — транспортная задача. В общем виде ее можно представить так: требуется найти такой план доставки грузов от поставщиков к потребителям, чтобы стоимость перевозки (или суммарная дальность, или объем транспортной работы в тонно-километрах) была наименьшей. Следовательно, дело сводится к наиболее рациональному прикреплению производителей к потребителям продукции (и наоборот). В простейшем виде, когда распределяется один вид продукта и потребителям безразлично, от кого из поставщиков его получать, задача формулируется следующим образом.
Имеется ряд пунктов производства 
с объемами производства в единицу времени (месяц, квартал), равными соответственно 
и пункты потребления 
потребляющие за тот же промежуток времени соответственно 
продукции. В случае, если решается закрытая (сбалансированная) задача, сумма объемов производства на всех пунктах-поставщиках равна сумме объемов потребления на всех пунктах-получателях:
Кроме того, известны затраты по перевозке единицы продукта от каждого поставщика к каждому получателю — эти величины обозначаются 
В качестве неизвестных величин выступают объемы продукта, перевозимого из каждого пункта производства в каждый пункт потребления, соответственно обозначаемые 
.
Тогда наиболее рациональным прикреплением поставщиков к потребителям будет такое, при котором суммарные затраты на транспортировку будут наименьшими:
При этом каждый потребитель получает нужное количество продукта:
и каждый поставщик отгружает весь произведенный им продукт:
Как и во всех подобных случаях, здесь также оговаривается неотрицательность переменных: поставка от какого-то пункта производства тому или иному пункту потребления может быть равна нулю, но отрицательной, т. е. следовать в обратном направлении, быть не может.
Строки транспортной таблицы соответствуют пунктам производства (в последней клетке каждой строки указан объем запаса продукта ai), а столбцы — пунктам потребления (последняя клетка каждого столбца содержит значение потребности bj). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о перевозке из i-го пункта в j-й: в левом верхнем углу находится цена перевозки единицы продукта, а в правом нижнем — значение объема перевозимого груза для данных пунктов. Клетки, которые содержат нулевые перевозки (xi,j=0), называют свободными, а ненулевые — занятыми (xi,j>0).
Несбалансированную (открытую) транспортную задачу приводят к виду, показанному выше, искусственно: в модель вводятся так называемые фиктивный поставщик или фиктивный потребитель, которые балансируют спрос и потребление.
В настоящее время разработано множество различных алгоритмов решения транспортной задачи: распределительный метод, метод потенциалов, дельта-метод, венгерский метод, метод дифференциальных рент, различные сетевые методы и т. д.
Производственно-транспортная задача
Это оптимизационная задача, при которой одновременно с установлением объема производства на отдельных предприятиях определяется и оптимальная схема размещения заказов (т. е. прикрепления поставщиков к потребителям). Она имеет особое значение для так называемых многотоннажных производств, где важен транспортный фактор (например, черные металлы, минеральные удобрения, нефтепереработка).
Такие задачи математически могут быть представлены в двух видах: в сетевой и в матричной постановке. Будучи основанными на принципах транспортной задачи линейного программирования, они очень сложны и решаются специальными, обычно многостадийными приемами с использованием эвристических элементов.
Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:
Это важно знать:
Этапы проектирования баз данных Этапы проектирования баз данных. Темы: этапы проектирования баз данных.
Классификация чрезвычайных ситуаций Чрезвычайная ситуация — обстановка, сложившаяся на определенной территории в результате промышленной аварии, иной опасной ситуации.
Управленческий цикл, основные функции управления Управленческий цикл — это завершенная последовательность повторяющихся действий, направленных на достижение поставленных целей.
С какими неисправностями запрещается выпускать локомотивы в эксплуатацию? Не допускается выпускать локомотивы, мотор-вагонный железнодорожный подвижной состав и специальный самоходный подвижной состав, если.
V. Общие требования к оформлению письменных работ по математике 5.1. Обучающие упражнения или другие письменные задания по математике ученикам выполняются в тетрадях в клеточку. 5.2. В 1 классе.