Курс лекци Русакова по методам оптимизации (1083216), страница 3
Текст из файла (страница 3)
В единице массы j-гопродукта содержится a2j жиров, a3j белков и a4j углеводов. Обозначимчерез b1, b2, b3, b4углеводахпотребление организма в энергии, жирах, белках исоответственно.Тогдаприправильномпитаниидолжнывыполняться следующие соотношения:a11 x1 + a12 x2 + ... + a1n xn ≥ b1 ;a21 x1 + a22 x2 + ... + a2 n xn ≤ b2 ;a31 x1 + a32 x2 + ... + a3n xn ≤ b3 ;,(1.11)a41 x1 + a42 x2 + ... + a4 n xn ≤ b4 ;где xj ≥ 0 – количество потребления j-го продукта.Если ввести требование экономного расходования средств, то этоэквивалентно критерию18nL = ∑ c j x j = min .(1.12)j =1{}Если поменять знаки у b1 , a1 j j = 1, n , то первое уравнение запишетсяв виде:a'11 x1 + a'12 x2 + ...
+ a'1n xn ≤ b'1 .(1.13)После этого задача о рациональном питании приобретает стандартныйвид задачи линейного программирования.Задача об использовании ресурсов.Предприятие имеет определенное количество ресурсов, рабочую силу,сырьё, оборудование и т.д. Для простоты будем считать, что число ресурсовравно трем, и каждого ресурса имеется b1, b2, b3 условных единиц.Пусть предприятие выпускает два вида товаров. Для производства{}единицы каждого товара затрачивается aij ресурсов i = 1,3; j = 1,2 .Известна стоимость cj единицы каждого товара.
Требуется при данныхресурсах выпустить такую комбинацию товаров x1 и x2, чтобы доходпредприятия был максимален. При линейной зависимости стоимостипродукцииотколичествапродукциизадачазаписываетсяввиде:L = c1 x1 + c2 x2 = maxпри{}{}ai1 x1 + ai 2 x 2 ≤ bi , i = 1,3 ; x j ≥ 0; j = 1,2 ,(1.14)и относится к классу задач линейного программирования. Еслистоимость товаров не зависит линейно от их количества, то имеет местозадача нелинейного программирования.Задача о загрузке транспорта.19Пусть имеется транспортная единица грузоподъемностью b, которуюнеобходимо загрузить различными предметами xj в разных количествах,причем cj -стоимость, wj -вес отдельного предмета j-го типа.
Например,загружаются автомобили, тракторы, самолеты. Требуется определитьоптимальную загрузку так, чтобы стоимость перевозимого груза быламаксимальной. Очевидно, что стоимость всего перевозимого груза задаетсяформулой:nL = ∑c j x j .(1.15)j =1Необходимо найти такие целые числа x j ,{j = 1,4}, при которых эталинейная форма приняла бы максимальное значение при условияхn∑ x j w j ≤ b,x j = 1,2,..., n .(1.16)j =1В отличие от предыдущих в этой задаче число ограничений i = 1. Этазадача существенно отличается от ранее рассмотренных тем, что в нейискомые значения величины xj — целочисленные.
Поэтому она относиться кзадачам целочисленного линейного программирования.1.06 Геометрический подход к решению задач линейного программированияВ решении задач линейного программирования часто пользуютсягеометрическими интерпретациями в разных вариантах.Система неравенств (2.1.2) определяет в пространстве x1, x2, …, xnвыпуклую область – выпуклый многогранник или многоугольник U. Дляслучая n = 2 имеем систему неравенств:20a11 x1 + a12 x2 + b1 ≤ 0;a x + a x + b ≤ 0; 21 122 22.............................am1 x1 + am 2 x2 + bm ≤ 0.(1.17)Каждое из этих соотношений определяет область, лежащую по однусторону от прямой:ai1 x1 + ai 2 x 2 + bi = 0 .(1.18)Теорема.Экстремальное значение целевой функции в задачах линейногопрограммирования:всегда является абсолютным;достигается в крайней точке определения задачи.Доказательство:Допустим, что в многограннике U или на его границе есть точка x0такая что ƒ(x0)≥ƒ(x) в некоторой окрестности N(x0).
Предположим также, чтов этом же многограннике есть точка типа x0, то есть точка x , в которойцелевая функция принимает лучшее значение, чем в точке x0. Если это нетак, то x*=x0, то есть точка относительного экстремума является и точкойабсолютногоэкстремума.Итак,предположимпротивное,тоестьсуществование некоторой точки x .Соединим точки x0 и x отрезком ирассмотрим значение целевой функции внутри отрезка в точке x (рис. ниже).21xnxUxx0x10Рис.
1.8. Отрезок, соединяющий точки х0 иx , принадлежащие многограннику U.Так как x j = λ x j + (1 − λ ) x 0 , 0 < λ < 1, тоnn[]f ( x ) = ∑ c j x j = ∑ c j λ x j + (1 − λ ) x 0 =λf ( x ) + (1 − λ ) f ( x 0 ) .j =1j =1Очевидно, что при фиксированных значениях x0 и x функция ƒ(x)является линейной функцией параметра λ:[]f ( x) = λ f ( x ) − f ( x 0 ) + f ( x 0 ) .Если сколь угодно близко x устремить к x0, то всегда будет ƒ(x)≥ƒ(x0),но это противоречит определению условного экстремума в точке x0.Следовательно, точка x0 является и точкой абсолютного экстремума.Докажем теперь, что экстремум всегда достигается в крайней точкеопределения задачи.Допустим, что x* не является крайней точкой в многограннике U, тоесть можно найти точки x1 и x2 такие, что x* окажется на соединяющемих отрезке.
Тогда очевидно, чтоf ( x* ) = [ f ( x 1 ) − f ( x 2 )]λ* + f ( x 2 ), 0 < λ* < 1или~~f ( x* ) = [ f ( x 2 ) − f ( x 1 )]λ * + f ( x 1 ), 0 < λ * < 1 .Если ƒ(x1)≠ƒ(x2), то тогда получаем противоречие с тем, что x* –абсолютный экстремум, а, следовательно, и ƒ(x*)≥ƒ(x1) и ƒ(x*)≥ƒ(x2).22Противоречия не будет, если ƒ(x1)=ƒ(x2).
Очевидно, что это справедливо, еслиx1 и x2 принадлежат гиперплоскости вида z=const=z*.Очевидно, что z* не может быть внутренней точкой U. Значит этагиперплоскость (прямая) может касаться U , и в этом случае она навернякапройдет через крайнюю точку – точку типа x*.Теорема доказана.Линейная форма (2.1.1) в случае двух переменных принимает вид:(1.19)L = c1 x1 + c2 x2Это есть уравнение прямой в плоскости (x1, x2), пересекающей оси x1 иx2 в точкахL Lи соответственно (рис.2.3.2).c1 c2x2AdBx10Рис.
1.9. Угол α= arccosc221c +c.22Величины c1 и c2 определяют наклон прямой, причём угол наклона коси x1 задается формулой:22c22 L2 + c12 L2 L c1 + c2L2 L2α = arccos, так как AB = 2 + 2 ==,c1 c2c12 ⋅ c22c1 ⋅ c2c12 + c22c2а22OB L L c1 + c2cos α == :.AB c1c1 ⋅ c223(1.20)L определяет расстояние от начала координат до прямой, котороеопределяется так:OB ⋅ AB = AB ⋅ d ⇒d=L L⋅c1 c2L ⋅ L ⋅ c1 ⋅ c2LOB ⋅ OA===.ABL c12 + c22 c1 ⋅ c2 ⋅ L c12 + c22c12 + c22c1 ⋅ c2(1.21)Дадим теперь геометрическую интерпретацию задачи линейногопрограммирования. Если требуется определить такиеx1иx2, которыепридали бы линейной форме экстремальное значение, то геометрически этоозначает, что необходимо провести прямую L {см.
(2.3.3)}, проходящуюхотя бы через одну точку области и имеющую минимальное илимаксимальное расстояние d от начала координат (рис.2.3.3а).x2x2GLd0L(L >0)x1d0G (L > 0)x1Рис. 1.10. Геометрическая интерпретация задачи линейного программирования для случаевминимума (а) и максимума (б).В случае максимизации это расстояние должно быть минимальным дляL< 0 (см. рис. 2.3.3а) и максимальным (см. рис. 2.3.3б) для L > 0.Кроме этого, возможны два варианта: прямая имеет с допустимойобластью одну общую точку в вершине области или совпадает с одним из ееребер. Во втором варианте (рис. 2.3.4) имеет место вырожденный случай, тоесть линейная функция цели совпадает с левой частью одного изограничений.24x2Gd(L > 0)0x1Рис. 1.11. Геометрическая интерпретация задачи линейного программирования для вырожденногослучая.Возможны также случаи, когда целевая функция не ограничена сверху(рис.
2.3.5) и система ограничений задачи несовместна (рис. 2.3.6).x2x2G f max0C1 C 2 C 3x1Рис. 1.12. Целевая функция f(x) не0x1Рис. 1.13. Несовместная системаограничена сверху.ограничений.Замечание.Так как при построении некоторой поверхности уровняf ( x ) = c1 x1 + c2 x 2 = h ,где h – некоторая константа, при n = 2, эта поверхность представляетпрямую c1x1+c2x2=h, то эта прямая в плоскости (x1, x2) пересекает оси ox1 и ox2в точкахhhuсоответственно (см. рис.
2.3.7).c1c2Следовательно, для нахождения оптимального решения следуетпередвигать линию уровня, проходящую через многоугольник решений, вrнаправлении вектора C , перпендикулярного данной линии уровня, до тех25пор, пока она не пройдет через последнюю ее общую точку смногоугольникомрешений.Координатыэтойпоследнейточки(невырожденный случай) или точек (вырожденный случай) и определяетоптимальный план данной задачи.x2Ahc2rCD0hc1BCx1Рис.
1.14. Поверхность уровня f(x)=c1x1+c2x2=h.Обозначим ∠CBA через α, ∠DOB через β, ∠OBA через γ .tgγ =h L L ⋅ c1 c1: == .c2 c1 L ⋅ c2 c2Пусть K1 – угол наклона прямой c1x1+c2x2= hкоси ox1, а K2 – уголнаклона вектора C к оси ox1.K1 = tgα = tg (1800 − γ ) = −tgγ = −c1.c2Из условия ортогональности прямой c1x1+c2x2 = h и вектора C имеемK1⋅K2 = – 1, то естьK2 = −c11=−= 2.cK1c1− 1c2Следовательно, уравнение вектора C , проходящего через точку (0,0)T,имеет вид:x2 − 0 = K 2 ( x1 − 0) , то есть x2 =26c2x1 .c1Таким образом, в качестве направляющего вектора C , следует братьrвектор C = (c1 , c2 )T .Такимобразом,нахождениеминимальногозначенияфункцииотличается от поиска ее максимального значения при тех же ограниченияхrлишь направлением движения вдоль вектора C = (c1 , c 2 ) T , во втором случаеон движется в противоположном направлении.1.07 Геометрический поиск решения задачи линейногопрограммирования для двухмерного случаяЗадача линейного программирования для частного случая n=2 имеетвид:найти x1, x2 , которые доставляют экстремум функцииz = F ( x1 , x2 ) = c1 x1 + c2 x 2 ,(1.22)при{}ai1 x1 + ai 2 x2 ≤ bi , i = 1, m ,(1.23)x j ≥ 0, j = 1,2 .(1.24)Поиск решения состоит из следующих шагов:Построение прямых, уравнения которых соответствуют ограничениями(2.3.7) и (2.3.8) при замене в них знаков неравенств на знаки равенств.Определение полуплоскостей, определяемых в каждом из ограниченийзадачи.Нахождение многоугольника решений.rПостроение вектора C = (c1 , c2 )T .Построение прямой c1x1+ c2x2=h, проходящей через многоугольникрешений.27rПередвижение прямой c1x1+ c2x2=h в направлении вектора C ,результатом чего является либо нахождение точки, в которой целеваяфункция принимает экстремальное значение, либо установление фактанеограниченности функции сверху(при нахождении максимальногозначения) или снизу (при нахождении минимального значения) на множествепланов.Определение координат точки экстремума и вычисление значенияцелевой функции в этой точке.Примеры.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
