Тема 6. ТЕОРЕТИЧЕСКИЕ ОСНОВЫРЕШЕНИЯ ЗАДАЧ НА ПЭВМ.
Задачи линейного программирования.
Линейное программирование — область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между переменными.
Программирование в управлении можно представить как процесс распределения ресурсов. Существует ряд различных методов, основанных на идеях математического программирования, однако, наиболее широкое применение нашел метод линейного программирования.
Применение методов линейного программирования актуально в сегодняшнее время, так как использование математических моделей является важным направлением совершенствования планирования и анализа деятельности компании. Представление данных в виде математической модели позволяет конкретизировать информацию, создавать и моделировать варианты, выбирать оптимальные решения.
Постановка задачи
Постановка практической задачи ЛП включает следующие основные этапы:
· определение показателя эффективности, переменных задачи,
· задание линейной целевой функции 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 = c1 x1 + c2 x2 +………+ cn xn (1.2)
Требуется найти такое неотрицательное решение системы
x1 ≥0, x2 ≥0, … …, xn ≥0 (1.3)
при котором функция f принимает наименьшее значение.
Уравнения (1.1) называют системой ограничений данной задачи; функцию f — целевой функцией (или линейной формой).
Методы решения задач линейного программирования
6.2.1. Симплекс – метод
Симплекс метод - метод линейного программирования, который реализует рациональный перебор базисных допустимых решений, в виде конечного итеративного процесса, необходимо улучшающего значение целевой функции на каждом шаге.
Применение симплекс-метода для задачи линейного программирования предполагает предварительное приведение ее формальной постановки к канонической форме с n неотрицательными переменными: (X1,..., Xn), где требуется минимизация линейной целевой функции при m линейных ограничениях типа равенств. Среди переменных задачи выбирается начальный базис из m переменных, для определенности (X1,..., Xm), которые должны иметь неотрицательные значения, когда остальные (n-m) свободные переменные равны 0. Целевая функция и ограничения равенства преобразуются к диагональной форме относительно базисных переменных, переменных, где каждая базисная переменная входит только в одно уравнение с коэффициентом 1:
X0 + A0,m+1*Xm+1 +... + A0,n*Xn = A0,0 X1 + A1,m+1*Xm+1 +... + A1,n*Xn = A1,0 .................. Xi + Ai,m+1*Xm+1 +... + Ai,n*Xn = Ai,0 .................. Xm + Am,m+1*Xm+1 +... + Am,n*Xn = Am,0Данная формальная модель задачи линейного программирования обычно задается в форме так называемой симплекс-таблицы, удобной для выполнения операций симплекс-метода:
Симплекс-таблица
X1 | X2 | ... | Xm | Xm+1 | ... | Xn | ||
X0 | A0,0 | ... | A0,m+1 | ... | A0,n | |||
X1 | A1,0 | ... | A1,m+1 | ... | A1,n | |||
X2 | A2,0 | ... | A2,m+1 | ... | A2,n | |||
... | ... | ... | ... | ... | ... | ... | ... | ... |
Xm | Am,0 | ... | Am,m+1 | ... | Am,n |
Верхняя строка симплекс-таблицы представляет целевую функцию задачи. Каждая строка симплекс-таблицы, кроме первой, соответствует определенному ограничению-равенству задачи. Свободные члены ограничений составляют крайний левый столбец таблицы. Слева от таблицы записаны текущие базисные переменные (X1,..., Xm). Сверху от таблицы приведен набор всех переменных задачи, где Xm+1,..., Xn - свободные переменные задачи.
Преобразования таблицы надо производить до тех пор, пока не будет получена симплекс-таблица, которая одновременно является прямо и двойственно допустимой.
Данный метод получил широкое распространение и большую популярность по сравнению с другими подходами, так как крайне редко на практике встречаются задачи трудные для симплекс-метода.
6.2.2. Геометрический метод
Применяется для задач с двумя переменными. Метод решения состоит в следующем:
На плоскости Ох1х2 строятся прямые, которые задают соответствующие ограничения:
a11 x1 + a11 x2 + …… + a11 xn = b1,
a21 x1 + a22 x2 + …… + a2n xn = b2,
…………………………………………
am1 x1 + am2 x2 + …… + amn xn = bm.
Находим множество всех точек х1,х2, удовлетворяющим всем неравенствам. Такое множество называется областью допустимых решений. Строим вектор и перемещаем линию уровня, который задается уравнением: с1х1+с2х2 = const в направлении вектора
до последней точки пересечения с ОДР. Эта точка и дает решение задачи Lmax = значению L в этой точки
Транспортная задача.
Одна из наиболее распространенных задач математического программирования — транспортная задача. В общем виде ее можно представить так: требуется найти такой план доставки грузов от поставщиков к потребителям, чтобы стоимость перевозки (или суммарная дальность, или объем транспортной работы в тонно-километрах) была наименьшей. Следовательно, дело сводится к наиболее рациональному прикреплению производителей к потребителям продукции (и наоборот). В простейшем виде, когда распределяется один вид продукта и потребителям безразлично, от кого из поставщиков его получать, задача формулируется следующим образом.
Имеется ряд пунктов производства с объемами производства в единицу времени (месяц, квартал), равными соответственно
и пункты потребления
потребляющие за тот же промежуток времени соответственно
продукции. В случае, если решается закрытая (сбалансированная) задача, сумма объемов производства на всех пунктах-поставщиках равна сумме объемов потребления на всех пунктах-получателях:
Кроме того, известны затраты по перевозке единицы продукта от каждого поставщика к каждому получателю — эти величины обозначаются В качестве неизвестных величин выступают объемы продукта, перевозимого из каждого пункта производства в каждый пункт потребления, соответственно обозначаемые
.
Тогда наиболее рациональным прикреплением поставщиков к потребителям будет такое, при котором суммарные затраты на транспортировку будут наименьшими:
При этом каждый потребитель получает нужное количество продукта:
и каждый поставщик отгружает весь произведенный им продукт:
Как и во всех подобных случаях, здесь также оговаривается неотрицательность переменных: поставка от какого-то пункта производства тому или иному пункту потребления может быть равна нулю, но отрицательной, т. е. следовать в обратном направлении, быть не может.
Рассмотрим таблицу.
Строки транспортной таблицы соответствуют пунктам производства (в последней клетке каждой строки указан объем запаса продукта ai), а столбцы — пунктам потребления (последняя клетка каждого столбца содержит значение потребности bj). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о перевозке из i-го пункта в j-й: в левом верхнем углу находится цена перевозки единицы продукта, а в правом нижнем — значение объема перевозимого груза для данных пунктов. Клетки, которые содержат нулевые перевозки (xi,j=0), называют свободными, а ненулевые — занятыми (xi,j>0).
В1 | В2 | …… | Вn | Всего | |
C1,1 | C1,2 | …… | C1,n | а1 | |
A1 | C2,1 | C2,2 | …… | C2,n | а2 |
A2 | …. | …. | …. | …. | |
…. | … | … | … | …. | …. |
Am | Cm,1 | Cm,2 | …… | Cm,n | аm |
b1 | b2 | bn |
Несбалансированную (открытую) транспортную задачу приводят к виду, показанному выше, искусственно: в модель вводятся так называемые фиктивный поставщик или фиктивный потребитель, которые балансируют спрос и потребление.
В настоящее время разработано множество различных алгоритмов решения транспортной задачи: распределительный метод, метод потенциалов, дельта-метод, венгерский метод, метод дифференциальных рент, различные сетевые методы и т. д.
Производственно-транспортная задача
Это оптимизационная задача, при которой одновременно с установлением объема производства на отдельных предприятиях определяется и оптимальная схема размещения заказов (т. е. прикрепления поставщиков к потребителям). Она имеет особое значение для так называемых многотоннажных производств, где важен транспортный фактор (например, черные металлы, минеральные удобрения, нефтепереработка).
Такие задачи математически могут быть представлены в двух видах: в сетевой и в матричной постановке. Будучи основанными на принципах транспортной задачи линейного программирования, они очень сложны и решаются специальными, обычно многостадийными приемами с использованием эвристических элементов.