Родоначальником ЛП считают доктора физ.-мат. наук, лау реата Государственной и Нобелевской премий акад. Л.В. Канто ровича [3, 4], который в 30-е гг. XX в. предложил метод оптими зации решения экономических задач (в частности, задачи раскроя фанеры [5]). Л.В. Канторович внес существенный вклад в развитие теории двойствешюсти линейного программирования. Согласно этой тео- 345 рии каждой задаче ЛП можно поставить в соответствие некото рую другую (так называемую двойственную) задачу ЛП, опти мальное значение которой такое же, как и в исходной задаче. Достоинство такого подхода состоит в том, что двойственная задача может оказаться проще исходной задачи в вычислитель ном отношении. Л.В. Канторович разработал метод разрешаю щих мноэ1сителей для решения задачи ЛП. Предложенный Канторовичем метод был принят не сразу. Потребовалось более 30 лет, чтобы ЛП сформировалось как са мостоятельный раздел теории оптимизации. В последующем, в 50-е гг. XX в. независимо от Канторовича метод решения задачи ЛП (так называемый симплекс-метод) был развит американским математиком Дж. Данцигом, который в 1951 г. и ввел термин «линейное программирование». Слово «программирование» объясняется тем, что неизвестные переменные, которые отыскиваются в процессе решения задачи, обычно определяют программу (план) действий некоторого объек та, например промышленного предприятия. Слово «линейное» отражает линейную зависимость между переменными. Рассмотрим простейший пример задачи Л П. Предположим, что в трех цехах (Ц1, Ц2, ЦЗ) изготавливают ся два вида изделий - И1 и И2. Известны загрузка каждого цеха а. (оцениваемая в данном случае в процентах) при изготовлении каждого из изделий и прибыль (или цена, объем реализуемой про дукции в рублях) с. от реализации изделий. Требуется определить, сколько изделий каждого вида следует производить при возмож но более полной загрузке цехов, чтобы получить за рассматрива емый плановый период максимальную прибыль или максималь ный объем реализуемой продукции. Такую ситуацию удобно отобразить в таблице, которая под сказывает характерную для задач математического программи рования форму представления задачи, т.е. целевую функцию (в данном случае определяющую максимизацию прибыли или объе ма реализуемой продукции) F{x) = X c^xi = 240xi + 320x2 -^ max (1) и ряд ограничений (в данном случае диктуемых возможностями цехов, т.е. их предельной 100%-ной загрузкой): 346 5л:, + 4х2< 100, 1,6х, +6,4^2- ^^^' 2,9л-, + 5,8^2 < 100. (2) Изделие И1 И2 Максимальная загрузка Загрузка цеха (участка), % Ц1 5 4 100 Ц2 1,6 6,4 100 цз 2,9 5,8 100 Цена изделия, руб. 240 j 320 - Графическое решение задачи приведено на рисунке. Ограничения здесь задают область допустимых решений в форме (заштрихованного) многоугольника, а семейство (пунк тирных) прямых представляет собой линии уровня целевой фун кции F. Существуют два крайних положения линии уровня, когда она «касается» допустимого множества. Этим двум положениям в данном случае соответствуют две точки «касания» - начало ко ординат (О, 0) и точка (9, 13). Первая из этих точек - точка мини- 347 мума, а вторая - максимума данной функции /'вида (1) на допус тимом множестве (2). В случае большего числа разнородных ограничений графи ческая интерпретация задачи затруднена, поэтому задачу пред ставляют в математической форме и используются специальные методы. Каноническая задача ЛП заключается в минимизации (макси мизации) линейной целевой функции F(x) = c,xi+C2X2+... + c„x,, при ограничениях (3) « 2 1 ^ 1 + ^ 2 2 ^ 2 + - + «2,;^А;=^2' Х,,л:2,...,Х^ >0, где числа с,, с^,..., с„ являются коэффициентами целевой функции; числа а.., i = l,2,...,/7t.у =1,2,..., /7 - коэффициенты системы ограничений, а ^,, ^2 ••' ^т ~ свободные члены, которые считаются неотрицательными. Математическую модель общей задачи ЛП представляют так же в следующей форме: найти такие значения вещественных переменных л,, л^ ,..., -v,^, кото рые доставляют максимальное (минимальное) значение линейной целе вой функции ^(•^) = S ^у • ^j ~^ ^^^ (min) 7=1 (4) при следующих ограничениях п 7=1 ^aij'Xj>bi, i = k + lj; 7=1 (5) ^aij'Xj =bi, i = l-^l,m; l7=l _ aj<xj<^j , j = l,n , m<n, где с, a.., b., a. (3. - заданные вещественные числа; к, I, т, п - целые числа. 348 Вектор X = (Xj, л'^,..., А'J, удовлетворяющий ограничениям задачи ЛП, называется допустимым решением или планом. До пустимый план X* =(jc*, Х2,..., х„), при котором целе вая функция задачи ЛП принимает максимальное (ми нимальное) значение, называется оптимальным планом. Иными словами, каноническая задача ЛП состоит в отыска нии среди всех решений системы (5) линейных уравнений такого ее неотрицательного решения, на котором достигает своего ми нимального (максимального) значения линейная целевая функ ция г от п переменных. В задаче ЛП общего вида вместо некоторых (всех) равенств в ограничениях записаны нестрогие неравенства в ту или другую сторону; при этом условие неотрицательности переменных мо жет отсутствовать для части или же для всех переменных. Извес тно, что решение любой задачи ЛП может быть сведено к реше нию канонической задачи, представляемой в форме (1) или (4). Линейное программирование первоначально развивалось как направление, разрабатывающее новые подходы к решению задач минимизации выпуклых функций на выпуклом мноэ/сестве (см. Выпуклое программирование). Понятие целевой функции (см.), удоб ное для приложений, сформировалось позднее. Наиболее простым и распространенным методом решения ка нонической задачи ЛП до сих пор является симплекс-метод, пред ложенный в 50-е гг. XX в. Дж. Данцигом. Геометрически идею сим плекс-метода в упрощенной форме можно выразить следующим образом. Допустимым множеством в задаче ЛП является неко торое многогранное множество ;7-мерного векторного простран ства (в частном случае п = 2 - это выпуклый и не обязательно ограниченный многоугольник). Работа симплекс-метода начина ется с некоторой начальной вершины (начального опорного пла на) многогранного множества. Специальным образом выясняет ся, нет ли среди соседних вершин такой, в которой значение целевой функции лучше? Если такая вершина выявлена, то она и принимается за следующее приближение. После этого вновь ис следуются соседние вершины для полученного приближения и т.д. до тех пор, пока не будет получена вершина, среди соседних вер шин которой не существует вершины с лучшим значением целе вой функции. Такая вершина является оптимальной. Она соответ ствует оптимальной точке (оптимальному решению) задачи ЛП. 349 Б настоящее время разработан широкий круг различных чис ленных методо]в решения задач ЯП, каждый из которых учи тывает ту или иную специфическую особенность имеющейся за дачи ЯП. Кроме симплекс-метода есть и другие методы решения спе циальных задач ЯП: метод потенциалов, венгерский метод, двои- ственный симплекс-метод, метод обратной матрицы {модифици рованный симплекс-метод) и др. Современное ЯП представляет собой область математики, по священную разработке теории и численных методов решения эк стремальных задач с линейными целевыми функциями и линей ными ограничениями в виде систем равенств и/или неравенств. С применением ЯП решается широкий круг задач экономического характера: задачи о комплексном использовании сырья, рацио нального раскроя материалов, задачи загрузки оборудования, размещения заказов по однородным предприятиям, задачи о сме сях, задачи текущего производственного планирования (стати ческая модель), задачи перспективного оптимального планиро вания, транспортная задача (см.).
Ви переглядаєте статтю (реферат): «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ (ЛП)» з дисципліни «Теорія систем і системний аналіз в управлінні організаціями»
