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

9.2. задачи линейного программирования: Справочник по математике для экономистов, В.И. Ермаков, 2007 читать онлайн, скачать pdf, djvu, fb2 скачать на телефон Предназначен для студентов экономических вузов. Может быть использован аспирантами и преподавателями вузов и колледжей, а также экономистами различных специальностей в практической работе.

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, Аг А„) — ранг системы векторов

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

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

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

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

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

Обсуждение Справочник по математике для экономистов

Комментарии, рецензии и отзывы

9.2. задачи линейного программирования: Справочник по математике для экономистов, В.И. Ермаков, 2007 читать онлайн, скачать pdf, djvu, fb2 скачать на телефон Предназначен для студентов экономических вузов. Может быть использован аспирантами и преподавателями вузов и колледжей, а также экономистами различных специальностей в практической работе.