Имя материала: Справочник по математике для экономистов

Автор: В.И. Ермаков

9.2. задачи линейного программирования

Оптимизационная задача (V,f, П), в которой целевая функция

является линейной функцией на V=R", а П — множеством решений некоторой системы линейных уравнений и линейных неравенств от п неизвестных, называется задачей щмещшео жирования. При этом система линейных уравнений и линейных неравенств, определяющая допустимое множество Q, называется системой ограничений задачи линейного программирования. Задача линейного программирования будет поставлена, если:

П

а)         указана линейная целевая функция /= £ ypcf,

j-i

б)        записана система ограничений

я

£ aijXj=bj, ієі, /сМ={1, 2, т),

 

. £ OijXj^bi, ієМІ,

Xj^OJeJ, J<=kN={,2, .-, n}

(часто бывает полезно в системе ограничений особо выделить неравенства вида 0);

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

ции) принадлежит данная задача. (Любую задачу максимизации

можно свести к задаче минимизации, поменяв знаки у коэффици-

ентов целевой функции.)

Любую задачу линейного программирования можно записать в следующем виде: /=£Ъх}(т1п), (9.1)

7-і

£ацХ}=К ієі, /сА/={1, 2, m}, (9.2) j-i

^ацХ^ЬьІєММ, (9.3)-/-і

Xj^OJeJ, I£N={1, 2,     л}. (9.4)

В частности, если 1=0 (I=M), то система (9.2) — (9.3) состоит только из линейных неравенств (уравнений).

Матрица А размера т х л, у которой на месте (i, j) стоит коэффициент при Xj в г'-м ограничении системы (9.2) — (9.3), т. е.

hi аіг ■■ А — a2i а22 ■■■агп

,ат ат2 —

 

называется матрицей условий, а столбцы этой матрицы

агп

— векторами условий задачи (9.1) —(9.4). Вектор В называется векщором ограничений задачи (9.1) — (9.4);

 

в--К

 

Свойство задач линейного программирования 1 °. Допустимое множество задачи линейного программирования либо пусто, либо является выпуклым подмножеством пространства R".

2°. Если допустимое множество задачи линейного програми-рования не пусто, а целевая функция ограничена снизу (для задачи минимизации) на этом множестве, то задача линейного программирования имеет оптимальное решение.

3°. Оптимальные решения задачи линейного программирования (если они существуют) всегда находятся на границе допустимого множества и образуют выпуклое подмножество пространства R".

Рассмотрим примеры экономических задач, приводимых к задаче линейного программирования.

Задача о рационе. В хозяйстве имеется п видов кормов,

каждый из которых содержит т разновидностей питательных

веществ. Известно, что одна единицаj-то вида кормов (/'= 1, 2,

т) содержит <1ц единиц г-го питательного вещества (i"=l, 2, т)

и имеет стоимость Су Требуется составить такой рацион, который

бы удовлетворил всем потребностям Ьіі (i'= 1, 2        m) в питатель-

ных веществах и имел наименьшую стоимость.

Обозначим количество у'-го корма в рационе х}, х^О (j=, 2,

я

л), а/ — стоимость этого рациона. Тогдаf= £ CjXj.

j~i

Рацион должен удовлетворять всем потребностям в питательных веществах. Значит,

л

YJaijXi^bl,i=12, ...,т.

 

Таким образом, мы получим задачу линейного программирования:

я

/=1СУ*ЛШІП)>

я

Y,aijXj^bi, i=l, 2          т,

xj>0,j=l, 2, л.

Простейшая задача планирования производства. Предприятие располагает т видами ресурсов и может выпускать некоторую однородную продукцию л различными технологическими способами. За единицу времени использования у-го технологического способа 0=1) 2, л) расходуется'ai} единиц 1-го ресурса (('= 1, 2, т) и выпускается с, единиц продукции. Требуется спланировать работу предприятия так, чтобы оно выпускало наибольшее количество продукции при условии, что ресурса і'-го вида нельзя израсходовать более чем bt единиц (i=l, 2, т).

Пусть Xj, Xj^Q (j—l, 2, л) — время использования предприятием j-ro технологического процесса. Бели при этом/— количество выпущенной продукции, то

л

/= X cjxj-

j-l

Работая по этому плану, предприятие израсходует Y*aoxj единиц /-го ресурса. Значит, J

я

YaijXj^bi, i=l, 2, т, и мы снова имеем задачу линейного программирования:

л

 

/-і

п

XX        i'=l, 2, т,

xj^0,j= 1, 2, п.

Важным примером задачи линейного программирования является транспортная задача (см. п. 9.12).

 

9.3. Графический метод решения двумерных задач линейного программирования

Дана задача линейного программирования

/= У }х і + Угх2 (тах);          (9- -s)

anxl+a11x2^bi, а21хх + a22x2^b2,

amixl + am2x2^bm,

 

(9-6)

 

В КОТОруЮ ВХОДЯТ ТОЛЬКО ДВа НеИЗВеСТНЫХ JCj и х2.

Каждое из неравенств системы (9.6) определяет на координатной плоскости (ху, х2) некоторую полуплоскость. Следовательно, допустимое множество ft задачи (9.5) — (9.6) есть пересечение конечного числа полуплоскостей, т. е. некоторая многоугольная область на плоскости (х1, х,).

Для решения задачи (9.5) — (9.6) графическим методом прежде всего необходимо построить многоугольную область ft, а затем перпендикулярно вектору Г=(у1, у2) провести прямую / так, чтобы она пересекала область Q.

Прямая / перемещается параллельно самой себе в направлении вектора Г до тех пор, пока не перестанет пересекать область ft (для задачи минимизации прямую / необходимо перемещать в противоположном направлении).

Если при таком перемещении прямая /все время будет пересекать область £ї„ то целевая функция не ограничена сверху на допустимом множестве и задача (9.5) — (9.6) не имеет оптимального решения (рис. 9.1).

В противном случае пересечение области Q прямой / в том ее положении, когда дальнейшее перемещение дает пустое пересечение с £2, является множеством оптимальных решений задачи (9.5) - (9.6) (рис. 9.2).

О Пример. Предприятие располагает тремя видами сырья и может выпускать одну и ту же продукцию двумя способами. При этом за 1 ч работы первым способом выпускается 20 единиц продукции, а вторым способом — 30 единиц продукции. Количество сырья (кг) того или иного вида, расходуемого за 1 ч при различных способах производства, и запасы сырья (кг) приведены в таблице. Требуется найти план производства, при котором будет выпущено наибольшее количество продукции.

 

 

 

Способ

 

Сырье

 

производ-

 

 

 

ства

1

2

3

Первый

to

20

15

Второй

20

10

15

Запасы

100

100

90

сырья

 

Обозначим через щ вщмя (ч) использования соответственно первого и второго способов производства. Имеем задачу линейного программирования /= 20^ + 30jc2 (max);

г іохі+гох^юо,

20^ + 10*2^100, і  15*!+ 15л2^90,

которую можно решать графическим способом. На рис. 9.3 изображены допустимое множество Q и оптимальное решение а0 этой задачи.

Любая точка из допустимого множества П является планом работы предприятия, для реализации которого хватит имеющихся запасов сырья. Оптимальное решение ас0 — это план из допустимого множества ІЇ, при котором будет выпущено наибольшее количество продукции.

Очевидно, что а0 является точкой пересечения прямых /j и /3) имеющих уравнения К)*! + 20х2= 100 и 15xj4-15;c2 = 90 соответственно.

Решая систему этих двух уравнений, получаем ху = 2, х2 = 4.

Таким образом, для производства наибольшего количества продукции при имеющихся запасах сырья необходимо 2 ч применять первый способ производства и 4 ч — второй способ.

При этом будет изготовлено /(а0) = 20- 2 + 30 -4 = 160 единиц продукции. #

 

9.4. Каноническая форма задачи линейного программировании

Задача линейного программирования имеет каноническую форму, если в ее систему ограничений входят только линейные уравнения и условия неотрицательности для всех неизвестных, т. е. в задаче (9.1) — (9.4) 1=М = {,2,т), а /= JV=={1, 2,п). Задача линейного программирования в канонической форме имеет следующий вид:

f=iyjxj(min), (9.7)

 

Y,OjXj=bh ' = 1, 2,    т; (9.8)

 

x&Q,j=,2, (9-9)

 

Задачу линейного программирования (9.7) — (9.9) в канонической форме можно записать в виде n

£ AjXj=B, Xj3>0, j= 1, 2, n, j-*

где Аг Ар Л„ — векторы условий, л В — вектор ограни-

чений этой задачи.

Любую задачу линейного программирования можно свести к задаче линейного программирования в канонической форме. В самом деле, рассмотрим задачу (9.1) — (9.4).

Каждое неизвестное хр jbNJ, заменим на разность yj—Zj

ДВуХ НОВЫХ Неотрицательных НеИЗВеСТНЫХ Ур Zj.

После этого в неравенства системы (9.3) введем по новому неизвестному tj(ieMI), полагая

 

2! ач xj + Z ао ІУу - zh + h = К ієМІ.

 

Получим задачу линейного программирования         в канонической

форме:

Г = ІУМ+ £ Yjty-zj) (min),     (9.10)

 

Y,a.jXj+ £ ^v'OV  Zj)=bj, і є/, (9.11)

£аих,+ Z fly(yj-z,) + /,=*hieAf/, (9.12) Xj^0,j'e/;^, Zj^0JeNJ; f(>0, ієЛГ/. (9.13)

 

При этом задача (9.10) — (9.13) будет иметь оптимальное решение тогда и только тогда, когда оптимальное решение было и у исходной задачи (9.1) — (9.4).

Кроме того, зная координаты оптимального решения задачи (9.10) —(9.13) х\% jeJ, у], г), ;'eNJ, /?, ієМ1, легко найти оптимальное решение исходной задачи, полагая Xj—xJ при jeJ

И Xj = yj—Zj При JEj.

9.5. Опорные решения задачи линейного программирования в канонической форме

Допустимое решение а задачи (9.7) — (9.9) в канонической форме называется опорным решением этой задачи, если векторы условий Ati А,2, а,, где ilt І2, .... ік — номера всех ненулевых координат а, образуют линейно независимую систему векторов.

О Например, векторы cti = (Q; 0; */2) и я2=(1; 0; 1; 1) являются допустимыми решениями задачи

f=3xl+ 4х2 - хъ + х4 (min),

Xl+   ■x2+^3 + JC4=:3>

[2xt + 2x2 - x3 4- x4 = 2, Xj^QJ=l, 2, 3,4.

Векторы условий A3 = ^ j^, ^4 = ^j^ образуют, очевидно, ли-

нейно независимую систему. Значит, является опорным реше-

нием данной задачи. Векторы Л^^у» ^з = (^    = ли-

нейно зависимы. Поэтому а2 не является опорным решением. #

Свойства опорных решений

Г. Если допустимое множество задачи (9.7) — (9.9) в канонической форме не пусто, то эта задача имеет опорное решение.

2°. Опорные решения задачи (9.7) — (9.9) являются крайними точками допустимого множества этой задачи. (Допустимое множество всегда выпукло.)

3°. Задача (9.7) — (9.9) в канонической форме имеет лишь конечное число различных опорных решений (либо не имеет их вовсе).

Чтобы найти некоторое опорное решение задачи (9.7) — (9.9), достаточно выбрать базис системы Av А2, А„ векторов условий этой задачи так, чтобы вектор ограничений В раскладывался по нему с неотрицательными коэффициентами.

Если Aiv Aiv    А{ — такой базис и В= Ai{dil+ А^^ +... + AtdlT, 4,^0, d^O,4,^0,то а = (0;0; </„; 0;0; di2; 0;0; d,- 0; 0) является опорным решением задачи (9.7) — (9.9).

Базис Л,,, Ап, Air системы векторов условий Ах, А2, .... А„ задачи (9.7) — (9.9) называется базисом опорного решения а= = (d1; d2     d„) этой задачи, если d,=0 при іФі^, і2, .... іГ.

О Рассмотрим, например, опорное решение ос = (1; 0; 0; 1) задачи

/= Xl + х2 - хг + х4 (min),

j*!- x2 + 2x2+jc4 = 2, ^0,>l, 2, 3, 4.

Здесь = (J)> ^2 = ( 2} ^3 = (-1)' ^* = (_ l) и ^' Л» Аг — базисы системы. Так как вторая и третья координаты вектора а равны 0, то А1, АА является базисом опорного решения ос. С другой стороны, четвертая координата ос отлична от нуля. Следовательно, Ах, А2 не будет базисом а. #

У любого опорного решения задачи (9.7) — (9.9) не может быть более чем г ненулевых (положительных) координат, где г=

=г (Ах, А2, .... А„) (г(А1, Аг         А„) — ранг системы векторов

условий). Опорное решение называется невырожденным, если число его ненулевых координат точно равно г и вырожденным — в противном случае.

Любое опорное решение имеет базис. При Этом у невырожденного опорного решения базис только один, а вырожденное опорное решение может иметь несколько различных базисов.

Опорные решения играют важную роль при решении задачи линейного программирования в канонической форме, так как если эта задача имеет оптимальное решение, то одно из ее оптимальных решений обязательно будет ее опорным решением. Таким образом, оптимальное решение задачи линейного программирования в канонической форме можно искать только среди ее опорных решений (а их лишь конечное число).

 

Страница: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 | 101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 | 126 | 127 | 128 | 129 | 130 | 131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 140 | 141 | 142 | 143 | 144 | 145 | 146 | 147 | 148 | 149 | 150 | 151 | 152 | 153 | 154 | 155 | 156 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 | 171 | 172 | 173 | 174 | 175 | 176 | 177 | 178 | 179 | 180 | 181 | 182 | 183 | 184 | 185 | 186 | 187 | 188 | 189 | 190 |