9.2. задачи линейного программирования
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 cjxjj-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) = 202 + 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 4x4 = 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, Аг А„) — ранг системы векторов
условий). Опорное решение называется невырожденным, если число его ненулевых координат точно равно г и вырожденным — в противном случае.
Любое опорное решение имеет базис. При Этом у невырожденного опорного решения базис только один, а вырожденное опорное решение может иметь несколько различных базисов.
Опорные решения играют важную роль при решении задачи линейного программирования в канонической форме, так как если эта задача имеет оптимальное решение, то одно из ее оптимальных решений обязательно будет ее опорным решением. Таким образом, оптимальное решение задачи линейного программирования в канонической форме можно искать только среди ее опорных решений (а их лишь конечное число).
Обсуждение Справочник по математике для экономистов
Комментарии, рецензии и отзывы