Название: Математические модели принятия решений в экономике - Розен В. В.

Жанр: Экономика

Рейтинг:

Просмотров: 903


Лекция 4. задачи линейного программирования

 

, Общая задача линейного программирования. Задача 4. Задача про­изводственного планирования. Задача 5. Задача о смеси. Задача 6. Задача о перевозках (транспортная задача). • Основной принцип линей­ного программирования. Понятие о симплекс-методе. Особенности су­ществования решений в задачах линейного программирования. • Двой­ственность в линейном программировании. Экономический смысл двойственности.

1. Задача линейного программирования представляет собой частный случай задачи оптимизации при наличии ограничений, который характеризуется тем, что:

а)         целевая функция является линейной;

б)         система ограничений, выделяющая допустимую область D, представляет собой систему линейных неравенств.

Общая задача линейного программирования (ОЗЛП) может быть задана в следующем виде: найти m&xf(xi,.. ., хп) при огра­ничениях

gi{xi, ...,i„)< h,

             (4-І)

9т{.Х , . . . , Xji) < bjn,

г^е fi 9i, ■ ■ ■, gm — линейные функции n переменных; при этом, как правило, накладываются граничные условия неотрицательности переменных: хі > 0 для всех і — 1, п.

Замечание. К общей задаче линейного программирования легко приводится случай, когда вместо максимума требуется найти минимум Целевой функциии в системе ограничений (4.1) знаки неравенств проти­воположны, а также если некоторые ограничения имеют вид равенств: 3ЗДача нахождения минимума функции / эквивалентна задаче нахожде-*°*я Максимума функции —/; изменение направления знака неравенства эквивалентно умножению обеих частей неравенства на —1, а равенство эквивалентно двум противоположенным неравенствам.

ОЗЛП на плоскости (т. е. относительно двух переменных) имеет следующий вид: найти максимум функции

f(x,y) = Ах + Ву + С

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

ах + Ьіу < сі,

             (4.2)

ЄітХ + bmy cm.

Так как каждое неравенство a,jx + bjy < Cj (j = l,m) определяет полуплоскость, ограниченную прямой ajx + bjy = Cj, то допустимая область V, выделяемая системой ограничений (4.2), представляет собой в этом случае пересечение конечного числа полуплоскостей, называемое выпуклым многоугольным (или многогранным) множеством. Если выпуклое многоугольное множество ограни­чено, оно будет выпуклым многоугольником.

ОЗЛП в пространстве (т.е. относительно трех переменных) принимает вид: найти максимум линейной функции

f(x, y,z) = Ах + By + Cz + D

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

ах + Ъу + Cz < d

             (4.3)

ЄЬт.Х ~~ Ьту -- CmZ ^ djn.

Здесь каждое неравенство ajX+bjy + Cjz < dj (j — l,m) определяет полупространство, ограниченное плоскостью ajX + bjy + CjZ — dj; пересечение конечного числа полупространств называется выпук­лым многогранным множеством (ВММ); если это множество ограничено, то оно представляет собой выпуклый многогранник.

Та же терминология принимается и для общего случая п пере­менных (термин плоскость заменяют в общем случае на гиперплос­кость). Итак, с геометрической точки зрения ОЗЛП состоит в на­хождении максимума линейной функции в допусти-мой области, которая представляет собой выпуклое многогранное множество.

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

Задача 4. Задача производственного планирования.

Содержательная постановка задачи такова. Предприятие может производить продукцию различных типов 1,...,п, имея запас ре­сурсов типов 1,. .., т. Пусть а — количество ресурса типа j, ко­торое требуется для производства единицы продукции типа г; б-7 — наличный запас ресурса типа j, а С( — прибыль от реализации еди­ницы продукции типа г (г = 1, п, j = 1, m). Все эти данные можно свести в таблицу (табл. 4.1).

Производственный план (короче — план) формально можно за­дать ВеКТОрОМ X = (Xl, . . . ,Хп), ГДЄ неотрицательное ЧИСЛО Xi > О

указывает количество продукции г'-го типа (г = 1, п), производимое в случае принятия этого плана (некоторые Хі могут быть равны нулю — это означает, что соответствующий тип продукции при этом плане не производится). Перейдем к определению оптималь­ного плана.

Определение, а) План называется допустимым, если он может быть реализован, т. е. если для его реализации хватает ресурсов всех типов.

б) План называется оптимальным, если, во-первых, он яв­ляется допустимым, и, во-вторых, дает максимальную прибыль среди всех допустимых планов.

Выразим теперь условия допустимости и оптимальности плана. Так как при плане х = (х,..., хп) расход ресурса j-ro типа равен aixi + ■ ■ ■ + aJnxn, а запас ресурса j-ro типа равен Ь3, то для того Чтобы план был реализуемым «по ресурсу j», надо, чтобы выпол­нялось неравенство ах + ■ ■ ■ + aJnxn < bJ; реализуемость плана «в целом» означает его реализуемость по каждому виду ресурсов и сводится, таким образом, к системе линейных неравенств

'axi +  h ахп < bl,

< a{xi + ■■■ + а{хп < b (4.4)

Kafx1 + --- + a^xn

к которой должны быть добавлены граничные условия неотрицате-тельности переменных: Х > 0,..., хп > 0.

Далее, прибыль от реализации плана х = (хх,...,хп) равна сХ + • ■ • + спхп. Таким образом, задача нахождения оптимального плана сводится к следующей оптимизационной задаче:

найти максимум линейной функции

 

f(xi, ...,хп) = СіХі -    h спхп

в допустимой области Т>, выделяемой системой линейных нера­венств (4.4) при граничных условиях хг > 0 (г = 1,п). Это — частный случай общей задачи линейного программирования.

• Пример 4.1. Найдем оптимальный план для задачи производст­венного планирования, заданной табл. 4.2.

х + 2у < 15, 16в + 6у < 96, 9х + 7у < 69

при граничных условиях неотрицательности х > 0, у > 0. Допусти­мая область V представляет собой многоугольник (рис. 4.1), ограничен­ный следующими прямыми: (її) : х + 2у = 15; (h) : 16х + 6у = 96; (^з) : 9х + 7у = 69; (/4) : х = 0; (/5) : у = 0. Целевая функция имеет вид: f(x,y) = 5х + 7у, а семейство линий уровня — это семейство пря­мых Ъх + 1у = с, где с — константа. Градиентом целевой функции здесь является постоянный вектор g = grad / с координатами (5; 7), который

 

Подпись:
перпендикулярен всем линиям уровня. Задача нахождения глобального максимума функции f(x,y) в допустимой области V в данном случае мо­жет быть решена графическим способом (см. лекцию 3, п. 2). Точка гло­бального максимума функции f(x,y) в области V это та вершина М*, через которую проходит линия уровня при наибольшем возможном зна­чении константы с (геометрически точка М* получается перемещением прямой Ъх + 7у = с в направлении градиента до тех пор, пока она еще пересекает область Т>). Приближенно значения координат (х*у*) точ­ки М" могут быть найдены по графику (рис. 4.1). Для нахождения точ­ных значений (х*;у*) составим систему из уравнений прямых (1) и (h), пересечением которых является эта точка:

(4.5)

Г х + 2у = 15, 9х + 7у = 69.

Решая систему, находим х* — 3, у" = 6. Задача 5. Задача о смеси.

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

Здесь а3\% — количество питательных веществ j-ro типа, которое содержится в единице продукта г'-го типа, сг — стоимость единицы продукта г-го типа, Ъ3 — минимальная норма питательного вещест­ва типа j в смеси (г = 1, п; j = 1, m).

Смесь называется допустимой, если содержащееся в ней коли­чество питательного вещества каждого типа не ниже минимальной нормы.

Смесь называется оптимальной, если она допустима и среди всех допустимых смесей имеет наименьшую стоимость.

Условия допустимости смеси х = (х,..., хп) сводятся к системе линейных неравенств

'ахх Н Ь alnxn > б1,

< ахх + ■ ■ ■ + а^Хп > bi, (4.6)

kofa;i + -v+o^a;„>b'n,

где х > 0,..., хп > 0.   ' '

Так как стоимость смеси х равна СХ + • ■ ■ + спхп, то задача нахождения оптимальной смеси сводится к следующей оптимиза­ционной задаче:

найти минимум функции f(x,..., хп) = с^х-^ + • • ■ + спхп в области Т>, заданной системой линейных неравенств (4.6) при условии неотрицательности переменных.

С учетом замечания на с. 39 сформулированная задача является частным видом общей задачи линейного программирования.

Задача 6. Задача о перевозках (транспортная задача).

Имеется п пунктов производства (или хранения) некоторого про­дукта и m пунктов потребления этого продукта. Количество дан­ного продукта в пункте г равно сг, а потребность в нем в пункте j равна bJ (г = 1, п, j = 1, m). Стоимость перевозки единицы про­дукта из пункта г в пункт j равна d. Как оптимальным образом спланировать перевозки?

Решение этой задачи состоит в следующем. Составить план перевозок — значит для каждого пункта производства г и для каждого пункта потребления j указать количество х3 продукта, которое должно перевозиться из і в j при этом плане. Таким образом, математически план перевозок может быть задан в виде неотрицательной матрицы х = \х3г\ (г = l,n; j = l,m). Установим условия допустимости (т.е. реализуемости) такого плана. Общее

m

количество продукта, вывозимое из пункта г, есть ^ х3, а общее

.7 = 1

п

количество продукта, доставляемого в пункт j, равно ^ х.

План будет допустимым, если, во-первых, для каждого пункта производства вывезенное количество продукта не превышает его наличного количества, и, во-вторых, должны быть удовлетворены потребности в данном продукте всех пунктов потребления. Итак, условия допустимости плана х — ЦхЩ принимают следующий вид:

m

^х\<сг, i = T~R, (4.7) j=i

n

Y,xl=V,      j =17^. (4.8)

г=і

(Заметим, что условия допустимости могут быть выполнены тогда, когда общая потребность в данном продукте не превышает его

т п

общего запаса, т.е. когда ]Г) Ъ3 < ]Г) сг.)

3=1 г=1

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

Общая стоимость всех перевозок при плане перевозок х = \х^\ может быть представлена в виде

п тп г = 1 j = l

(считается, что стоимость перевозок продукта пропорциональна его количеству).

Итак, задача нахождения оптимального плана перевозок сводит­ся к нахождению минимума функции (4.9) при ограничениях (4.7), (4.8) и граничных условиях неотрицатетельности переменных. Дан­ная задача с учетом замечания на с. 39 является частным случаем общей задачи линейного программирования.

2. Сформулируем основной принцип линейного программирова­ния. Он базируется на следующем утверждении.

Правило 4.1. Линейная функция п переменных, заданная в области Т) С R™ и отличная от постоянной, может достигать глобального экстремума только на границе области Т>.

Для простоты записи рассмотрим случай функции трех пере­менных

f(x, у, z) = Ах + By +Cz + D.

Градиент функции / является здесь постоянным вектором с коор­динатами (А, В, С), причем так как функция / отлична от посто­янной, ее градиент не равен нулю. На основании принципа стацио­нарности и замечания к нему (см. лекцию 3, п. 1) получаем, что функция / не может достигать глобального экстремума ни в ка­кой внутренней точке области Т>. Отсюда и следует утверждение правила 4.1.

Рассмотрим теперь линейную функцию /, заданную на выпук­лом многограннике Т> С R™. Так как выпуклый многогранник пред­ставляет собой замкнутое и ограниченное множество, то согласно теореме Вейерштрасса (см. лекцию 3, п. 1) функция / достигает на нем глобального максимума; учитывая правило 4.1, приходим к следующему утверждению.

Следствие. Линейная функция /, заданная на выпуклом мно­гограннике Т> С R™, достигает как глобального минимума, так и глобального максимума на границе многогранника Т>.

Теперь, чтобы сформулировать основной принцип линейного программирования, остается сделать одно уточнение к указанно­му следствию; оно состоит в том, что линейная функция, заданная

на выпуклом многограннике, достигает своих экстремумов в неко­торых вершинах этого многогранника.

Обоснуем это утверждение, ограничиваясь случаем функции трех переменных. Согласно приведенному выше следствию, гло­бальный экстремум функции / достигается на границе многогран­ника V. Граница выпуклого многогранника представляет собой объединение выпуклых многоугольников. Предположим, что функ­ция / достигает, например, глобального максимума в некоторой внутренней точке Мо многоугольника Р, представляющего собой часть границы выпуклого многогранника V (рис. 4.2). Тогда гра­диент функции / в точке Мо должен быть перпендикулярен плос­кости многоугольника Р. В самом деле, если бы это было не так, то можно было бы сдвинуться из точки Мо в некоторую точку Mi £ Р ло направлению вектора а, составляющему острый угол с векто­ром g = grad/ІМо- Так как разность /(Mi) - /(М0) представима в виде скалярного произведения g на вектор смещения MqMi, то учитывая, что g • МоМ > 0, получаем /(Мх) > /(Мо) в противо­речие с тем, что Мо — точка глобального максимума функции / в области Т>. Из условия перпендикулярности градиента g плоскости Многоугольника Р сразу следует, что функция / является постоян­ной на Р, значит, она достигает глобального максимума в любой вершине многоугольника Р.

Итак, получаем следующее правило.

Правило 4.2 (Основной принцип линейного программирова­ния). Линейная функция, заданная на выпуклом многограннике D С IR™, достигает как глобального минимума, так и глобаль­ного максимума в некоторых вершинах этого многогранника.

 

На правиле 4.2 основаны общие алгоритмы нахождения реше­ния задач линейного программирования. В принципе можно най­ти точки глобального экстремума линейной функции, заданной на выпуклом многограннике, с помощью перебора его вершин. Од­нако технические сложности процедуры перебора вершин много­гранника настолько существенны, что, за исключением простей­ших случаев, этот метод в практическом отношении бесполезен. Самый известный алгоритм решения задач линейного программи­рования — симплекс-метод — использует «направленный перебор», когда, например, при поиске глобального максимума, вначале нахо­дят какую-нибудь вершину допустимого многогранника, а затем пе­реходят к таким соседним вершинам этого многогранника, в кото­рых значения целевой функции увеличиваются (алгоритм симплекс-метода детально описан во многих учебниках).

В заключение отметим некоторые особенности, относящиеся к существованию решений в задачах линейного программирования (в качестве иллюстрации используются задачи линейного програм­мирования на плоскости). Может быть несколько основных случаев.

Допустимая область Т> есть пустое множество (рис. 4.3). Это означает, что система ограничений является несовместной. Тогда ни допустимых, ни оптимальных решений нет.

Допустимая область Т> ограничена. Тогда она представля­ет собой выпуклый многогранник, который является всегда замк­нутым. Так как линейная функция непрерывна, то, в силу теоре­мы Вейерштрасса (см. лекцию 3), в этом случае целевая функция достигает в области Т> как глобального минимума, так и глобаль­ного максимума. По правилу 4.2 точками глобального минимума и глобального максимума являются некоторые вершины выпукло-

 

го многогранника D (рис. 4.4). При этом один из экстремумов, а также оба они могут достигаться во всех точках некоторого реб­ра многогранника V (в общем случае — во всех точках некоторого многогранника меньшей размерности); последняя ситуация показа­на на рис. 4.5.

Рис. 4.7

(3) Допустимая область D не ограничена. Тогда она представ­ляет собой выпуклое многогранное множество, не являющееся вы­пуклым многогранником. В этом случае в зависимости от направ­ления градиента grad / целевая функция / может иметь в области V оба экстремума (рис. 4.6), а также иметь экстремум одного вида и не иметь другого (рис. 4.7).

3. Рассмотрим кратко одно из важнейших понятий линейного программирования — понятие двойственности. Общая задача ли­нейного программирования полностью определяется матрицей (а3г) размера п х т, к которой добавлены вектор-строка Ь = (Ь1,.. ., Ьт) и вектор-столбец с = (сі,..., с„)г (табл. 4.4).

В компактной записи система ограничений такой задачи имеет вид следующей системы линейных неравенств:

п

£)a?a:,

при граничных условиях х, > 0 (г = 1, п), а целевая функция имеет вид

f(xl,...,Xn)=ClXl-       Ь СпХп = (с, х).

Напомним, что общая задача линейного программирования состо­ит в максимизации целевой функции (с, х) при системе ограниче­ний (4.10). Назовем эту задачу прямой задачей линейного про­граммирования.

Тогда двойственная ей задача линейного программирования формально строится по той же матрице, в которой строки и столб­цы меняются ролями и, кроме того, знаки неравенств в системе ограничений меняются на обратные. Для записи системы ограни­чений двойственной задачи, во-первых, введем двойственные пере­менные у — (у1,.. ., ут). Система ограничений двойственной зада­чи имеет вид следующей системы линейных неравенств:

т

Х>г^>Сг,       *=Т7^, (4.11)

При граничных условиях у3 > 0 (j = l,m), а целевая функция 5(2/1,...j2/m)=012/1+--- + bm2/m = (b,2/).

Бели прямая задача линейного программирования состоит в нахож­дении максимума целевой функции, то двойственная задача состоит в нахождении минимума целевой функции (о, у) при системе огра­ничений (4.11).

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

В заключение этой темы укажем экономический смысл двойст­венности на примере задачи о смеси (см. п. 1).

Рассмотрим задачу о смеси, заданную таблицей типа табл. 4.5, где {#!,...,#„} — первичные продукты, из которых составляется смесь, а в качестве питательных веществ берутся белки (Б), жиры (Ж) и углеводы (У). Прямая задача линейного программирования в данном случае имеет следующий вид:

найти минимум функции f(x і,.. ., xn) = сХ ! + ••• + cnxn при системе ограничений

{

ах 1-І  Ь ахг Л           f- ахп > Ъ1, ахх + --- + а2хг + --- + а2пхп > о2, (4.12) ах і + • • • + а3хг Н   + ахп > Ь3

4 граничных условиях х і > 0,..., хп > 0.

Построим двойственную задачу линейного программирования. Система ограничений двойственной задачи принимает вид

'aly1 + а2у2 + ау3 < сь

 

< агУ + а2у2 + а3у3 < а, (4.ІЗ)

 

с граничными условиями у1 > О, у2 > О, у3 > 0. Целевая функция двойственной задачи есть д^у1, у2, у3) = Ь1?/1 + Ь2у2 + Ь3у3. Двойственная задача формулируется следующим образом:

найти максимум функции д(у1, у2, у3) при системе ограничений (4.13).

В чем состоит в данном случае экономический смысл двойст­венной задачи?

Предположим, что некая фирма А продает первичные продукты {Пі,..., Пп} по цене Сі за единицу продукта Щ (i = 1,п). Возни­кает конкурирующая фирма В, которая предлагает покупателям не сами первичные продукты Пі,..., Пп, а белки, жиры и углеводы «в чистом виде» (например, в виде таблеток, или «на вес»). Пусть у1, у2, у3 — цена «единицы белков», «единицы жиров» и «единицы уг­леводов» соответственно. Так как единица продукта Пг может быть заменена набором, состоящим из а ед. белков, а2 ед. жиров и а?ед. углеводов (будем записывать такой набор в виде аБ ф а?Ж© фа3У), то покупатель сможет предпочесть такой набор единице продукта П только в том случае, когда стоимость этого набора будет не больше стоимости единицы продукта Щ, т.е. когда

ajy1 + а2у2 + а3у3 < а,

но это и есть как раз неравенство, входящее в систему ограничений двойственной задачи. Далее, если покупатель приобретает белки, жиры и углеводы «в чистом виде», то для получения требуемой смеси он должен приобрести набор, состоящий из Ь1 ед. белков, Ь2 ед. жиров и Ь3ед. углеводов, т.е. набор

ЬХБ @Ъ2Ж ®Ъ3У.

Стоимость такого набора равна Ь1?/1 + Ъ2у2 + Ь3у3, что совпадает с целевой функцией двойственной задачи.

 

Итак, в данном случае смысл двойственных переменных у1, у2, у3 — это цены, назначаемые за единицу белков, жиров и углеводов соответственно.

Экономический смысл оптимального вектора цен у = (у1 ,у2,у3) состоит в следующем.

а)         Допустимость вектора цен у = (у1, у2, у3) означает, что «це- ны должны быть не слишком высокими»; точнее, такими чтобы покупателю было выгодно вместо покупки единицы каждого про- дукта Щ купить по этим ценам эквивалентный ему набор

аБ фа2Ж ©а3У,       г = T~n.

б)         Оптимальность вектора цен состоит в том, что «цены долж- ны быть не слишком низкими». Точнее, среди всех допустимых век- торов цен оптимальный вектор цен характеризуется тем, что при покупке набора ЬХБ © Ь2 Ж © Ь3 У по оптимальным ценам он при- носит фирме В наибольший доход.


Оцените книгу: 1 2 3 4 5