Курс лекци Русакова по методам оптимизации (1083216), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Пусть для производства двух видов изделий A и B используется 3вида сырья, причем необходимые данные сведены в следующую таблицу.Таблица 1.1При этом изделия A и B могут производиться в любых соотношениях.Требуется составить план выпуска, обеспечивающий максимальнуюприбыль.Решение:Предположим, что изготовлено x1 изделий вида A и x2 изделий вида B.28В силу условий задачи должны выполнятся условия:12 x1 + 4 x2 ≤ 300;4 x1 + 4 x2 ≤ 120;(1.25)3x1 + 12 x2 ≤ 252;x1 ≥ 0, x2 ≥ 0.Общая прибыль от реализации изделий составитF = 30 x1 + 40 x 2 .(1.26)Таким образом, имеем следующую математическую постановку задачи.Среди всех неотрицательных решений системы линейных неравенств(2.3.9) найти такое, при котором функция F { см. (2.3.10)} принимаетмаксимальное значение.Для решения задачи воспользуемся геометрической интерпретацией.Заменим все неравенства системы ограничением на равенства.

В результатеполучаем уравнения прямых:12 x1 + 4 x2 = 300 (I)4 x + 4 x = 120(II)2 13x1 + 12 x2 = 252 (III) .x = 0(IV) 1 x2 = 0(V)(1.27))Изобразим эти прямые на рисунке 2.3.8.Каждая из построенных прямых делит плоскость на две полуплоскости,причём координаты одной полуплоскости удовлетворяютисходномунеравенству, а другой – нет.Чтобы определить истинную полуплоскость, берем какую-либо точку,принадлежащую одной из полуплоскостей и проверяем, удовлетворяет лиона данному неравенству. Если удовлетворяет, то это–искомаяполуплоскость, иначе – другая полуплоскость. Например, для прямой I:12x1+4x2=30 возьмём точку (0,0)T. Если подставим координаты этой точки вуравнение I, то получим 0<30, то есть координаты точки удовлетворяют29исходномунеравенству.Следовательно,полуплоскость,которойпринадлежит точка (0,0)T является искомой.Пересечение полученных полуплоскостей определяет многоугольникрешений OABCDEK.

Осталось найти точку, в которой F принимаетrмаксимальное значение. Для этого строим вектор C = (30,40) и прямую30x1+40x2 = h, где h – некоторая константа, причём такая, что прямая имеетобщие точки с многоугольником решений.30 x1+ 40 x 2 = 480BCAOD0K EРис. 1.15. Многоугольник решений – OABCDEK.Пусть h=480. Строим прямую 30x1+40x2=480. Если взять какую-либоточку, принадлежащуюпрямой и многоугольнику решений, то еёкоординаты определяют такой план производства, при котором прибыль отреализации равна 480.Полагая далееhравным некоторому числу, большему чем 480,получаем различные параллельные прямые. Если они имеют общие точки смногоугольником решений, то эти точки определяют планы производства Aи B, при котором прибыль превосходит 480.30ПеремещаяпостроеннуюпрямуювнаправлениивектораrCубеждаемся, что последней общей точкой её с многоугольником решенийявляется точка B, координаты которой и определяют оптимальный планвыпуска изделий A и B.Найдём координаты точки B, как точки пересечения прямых II и III:4 x1 + 4 x2 = 120 33x1 + 12 x2 = 252 4⇒12 x1 + 12 x2 = 360−12 x1 + 48 x2 = 100836 x2 = 768;x2 = x2* = 18;12 x + 12 x2 = 360− 13x1 + 12 x2 = 2529 x1 = 108;x1 = x2* = 12.Итак, координатами точки B является:x1* =12 ;x*2 =18 .Следовательно, изготовив 12 единиц изделий вида A и 18 единицизделий вида B, получаем максимальную прибыльFmax=30⋅12+40⋅18=1080.2.

Найти значение x1 и x2 , доставляющие экстремальные значения(минимум и максимум) функции F = x1 + x2 при ограничениях:2 x1 + 4 x2 ≤ 16− 4 x + 2 x ≤ 812 x1 + 3x2 ≥ 9 .x ≥ 0 1 x2 ≥ 031(*)Заменим все неравенства в ограничениях равенствами, в результатеполучаем уравнения прямых:2 x1 + 4 x2 = 16− 4 x + 2 x = 812 x1 + 3x2 = 9x = 0 1 x2 = 0(I)(II)(III) .(IV)(V)Изобразим эти прямые на рисунке (см.

рис. 2.3.9).x22 x1- 4 x1+ 2x2 = 8+ 4 x 2 = 16rCx1 + 3x 2 = 9x1x1 + x2 = 4Рис. 1.16. Многоугольник решений АВС.Анализ показывает, что многоугольником решений задачи являетсяrтреугольник ABC, а вектором – C = (1,1)T .Для нахождения экстремальных значений функции F=x1+x2 возьмемF=4, так как при этом значении прямая 4=x1+x2 имеет общую точку смногоугольником решений.Передвигая данную прямую параллельно самой себе в направленииrвектора C находим, что её последней общей точкой с многоугольникомрешений является точка C.

Следовательно, в этой точке функция принимаетмаксимальное значение.32Так как точка C является пересечением I и III прямых, то еекоординаты удовлетворяют системе из уравнений этих прямых:2 x1 + 4 x 2 = 16.x+3x=9 12∆=2 416 42 16= 2; ∆ 1 == 12; ∆ 2 ==2⇒1 39 31 9⇒ x1∗ = 6; x 2∗ = 1 ⇒ Fmax = F ( x1∗ , x 2∗ ) = x1∗ + x 2∗ = 7.Длянахожденияпередвигаем прямуюминимальногоx1+ x2 = 4значенияцелевойфункцииFв направлении, противоположномrнаправлению вектора C = (1,1)T .Последней общей точкой прямой и многоугольника решений являетсяточка A. Следовательно, минимальное значение функция F принимает вточке A, удовлетворяющей системе: x1 + 3x2 = 9. x1 = 0Итак, x1∗ = 0; x2∗ = 3; Fmin = x1∗ + x2∗ = 3 .3. Найти максимальное значение функцииF = −16 x1 − x2 + x3 + 5 x 4 + 5 x5 , при условиях2 x1 + x2 + x3 = 10− 2 x + 3x + x = 6124.2x+4x−x=825 1 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0Решение:Здесь ограничения заданы в виде равенств, число которых m=3, ачисло неизвестныхгеометрическиравно 5.Поэтому,чтобырешитьзадачуна плоскости, её следует свести к задаче, в которой числонеизвестных равно 2.

Исключим33переменные x3, x4 и x5 из целевойфункции. Дляэтого воспользуемся уравнениями системы ограниченийx3 = 10 − 2 x1 − x2 ; x4 = 6 + 2 x1 − 3 x2 ; x5 = 8 − 2 x1 − 4 x 2и подставим x3, x4, x5 , выраженные через x1 и x2 , в целевую функцию.В результате имеем:F = −16 x1 − x2 + (10 − 2 x1 − x2 ) + 5(6 + 2 x1 − 3x2 ) − 5(8 − 2 x1 − 4 x2 ) = 2 x1 + 3x2 .Ограничения при этом имеют вид:(I)2 x1 + x2 ≤ 10− 2 x + 3x ≤ 6(II)12(III)2 x1 + 4 x2 ≤ 8 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0.Построим многоугольник решений полученной задачи (рис.2.3.10).Построим функцию 2 x1 + 3 x 2 = 12 (12 взято произвольно).Строим вектор C = (2;3)T .Максимальное значение целевая функция принимает в точке C, то естьв точке пересечения I и II кривыхНайдем координаты точки C.2 x1 + x2 = 10;− 2 x1 + 3x2 = 6 ⇒ x1∗ = 3; x2∗ = 4.342 x1+ x2 = 10− 2 x1+ 3 x2 = 62 x1+ 4 x2 = 8Рис.

1.17. Многоугольник решений ABCD.Вдоль каждой из граничных прямых, значение одной из переменных,исключенной при переходе к соответствующему неравенству равно 0.Поэтому в каждой из вершин полученного многоугольника решений покрайней мере две переменные исходной задачи принимает нулевые значения,так, например, в точке C x3= 0 и x4= 0.Подставляя найденные значения x1∗ и x2∗ в III уравнение системыограничений исходной задачи,то есть в уравнение 2 x1 + 4 x 2 − x5 = 8 , имеем:2 ⋅ 3 + 4 ⋅ 4 − x 5∗ = 8 ∗5 ⇒ x 5∗ = 14 .Следовательно, оптимальным планом рассматриваемой задачи являетсяплан x = (3; 4; 0; 0; 14) .

Максимальное значение целевой функции равноFmax = −16 ⋅ 3 − 4 + 5 ⋅ 14 = 18или, что то же самое, Fmax = 2 ⋅ 3 + 3 ⋅ 4 = 18 .35Задание.Для предыдущей задачи найти минимальное значение целевойфункции.4.НайтимаксимальноезначениефункцииF = 6,5 x1 − 7,5 x3 + 23,5 x4 − 5 x5при условиях: x1 + 3x2 + x3 + 4 x4 − x5 = 122 x − x + 12 x − x = 14 1345 x1 + 2 x2 + 3x4 − x5 = 6 x1 ,..., x5 ≥ 0 .(I)(II)(III)(IV)Решение:Число неизвестных здесь равно 5. Поэтому, чтобы решить задачугеометрически на плоскости, ее следует свести к задаче, в которой числонеизвестных равно 2. Для этого воспользуемся методом последовательногоисключения неизвестных.1.

Из I и III уравнений x1 + 3x2 + x3 + 4 x4 − x5 = 12 x1 + 2 x2 + 3x4 − x5 = 6имеем:x 2 + x3 + x 4 = 6 .(1.28)2. Из I и II уравнений− 2 x1 − 3x2 − x3 − 4 x4 + x5 = −12− x3 + 12 x4 − x5 = 142 x1имеем:x1 − 3 x2 − 2 x3 + 8 x4 = 2 .(*)Из уравнения (2.3.12) имеем:x 2 = 6 − x3 − x 4 .36(1.29)Подстановка x2 из (2.3.13) в (*) даёт:x1 − 18 + 3x3 + 3x4 − 2 x3 + 8 x4 = 2 ⇒x1 + x3 + 11x4 = 20.(1.30)3.

Из II и III уравнений2 x1 − x3 + 12 x4 − x5 = 14.− 2 x1 − 4 x2 + 6 x4 + 2 x5 = −12 (III уравнение, умноженноое на (-2))Сложив оба уравнения имеем:− 4 x 2 − x3 + 6 x 4 + x5 = 2 .(1.31)Подстановка x2 из (2.3.13) даёт:− 24 + 4 x3 + 4 x4 − x3 + 6 x4 + x5 = 2 ⇒3x3 + 10 x4 + x5 = 26.(1.32)Следовательно, имеем условие x 2 + x3 + x 4 = 6 x1 + x3 + 11x4 = 20 .3x + 10 x + x = 2645 3(1.33)Переходим к условиям в виде неравенств, то есть убрав x1, x2, x5 изуравнений (2.3.17), получим условия, в которых есть только две переменныеx3 и x4: x3 + x 4 ≤ 6 x3 + 11x4 ≤ 20 .3x + 10 x ≤ 264 3Обращаемся к целевой функции.

Из уравнений (2.3.17) x1 и x5 имеютвид:x1 = 20 − x3 − 11x4 ;x5 = 26 − 3x3 − 10 x4 .Подставим эти выражения в целевую функцию. В результате имеем:F = 6,5 x1 − 7,5 x3 + 23,5 x4 − 5 x5 = 130 − 6,5 x3 − 71,5 x4 − 7,5 x3 + 23,5 x4 − 130 ++ 15 x3 + 50 x4 = x3 + 2 x4 .37Следовательно,исходнаязадачалинейногопрограммированиязаписывается так.Найти максимальное значение F = x3 + 2x 4 при условиях x3 + x4 ≤ 63x + 10 x ≤ 26 34.x+11x≤2034 x3 ≥ 0; x4 ≥ 0Таким образом, преобразованная система содержит две переменных.Следовательно, можно воспользоваться геометрическим методом: строитьпрямые, определить многоугольник решений и находить в нем крайниеточки.Задание.В примере № 4 определить максимальное и минимальное значениецелевой функции.1.08 СимплексметодрешениязадачлинейногометодоптимальногопрограммированияСимплекс-метод–этоспециальный(направленного) перебора, используемый при решении задач линейногопрограммирования.Симплекс-методобеспечиваетсходимостькэкстремальной точке за конечное число шагов, так как он предусматриваетпоследовательный оптимальный просмотр вершин многогранника, числокоторыхконечно,экстремума.38иявляетсяоптимальнойпроцедуройотысканияСимплекс-метод заключается в последовательном переходе от однойвершины области допустимых значений к другой, соседней, в которойзначение функции цели лучше, чем в исходной точке.Известно, что если решение задачи линейного программированиясуществует, то оно достигается в одной из вершин многогранника решений.Симплекс-методпозволяетнайтикрайнююточкуобластимногогранника решений ν и определить является ли эта точка точкой типаx*.

Характеристики

Список файлов лекций