Линейное программирование

Тема 15. Основные понятия теории оптимизации.

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

Успешность решения подавляющего большинства экономических задач зависит от наилучшего, наивыгоднейшего способа использования ресурсов. И от того, как будут распределены эти, как правило, ограниченные ресурсы, будет зависеть конечный результат деятельности.

Суть методов оптимизации (оптимального программирования) заключается в том, чтобы, исходя из наличия определенных ресурсов, выбрать такой способ их использования (распределения), при котором будет обеспечен максимум или минимум интересующего показателя. [1]

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

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

Оптимальное программирование обеспечивает получение практически ценных результатов, так как по своей природе оно вполне соответствует характеру исследуемых технико-экономических процессов и явлений. С математической и статистической точек зрения этот метод применим лишь к тем явлениям, которые выражаются положительными величинами и в своей совокупности образуют объединение взаимозависимых, но качественно различных величин. Этим условиям, как правило, отвечают величины, которыми характеризуются экономические явления. Перед исследователем экономики всегда имеется - некоторое множество разного рода положительных величин. Решая задачи оптимизации, экономист всегда имеет дело не с одной, а с несколькими взаимозависимыми величинами или факторами.

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

Задача становится разрешимой при введении в нее определенных оценок как для взаимозависимых факторов, так и для ожидаемых результатов. Следовательно, оптимальность результата задачи программирования имеет относительный характер. Этот результат оптимален только с точки зрения тех критериев, которыми он оценивается, и ограничений, введенных в задачу.

Отталкиваясь от вышесказанного, для любых задач оптимального программирования характерны три следующих момента: [2]

1) наличие системы взаимозависимых факторов;

2) строго определенный критерий оценки оптимальности;

3) точная формулировка условий, ограничивающих использование наличных ресурсов или факторов.

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

Математически это может быть сведено к нахождению экстремального значения некоторой функции, то есть к задаче типа:

Найти max (min) f(x) при условии, что переменная х (точка х) пробегает некоторое заданное множество Х:

f(x) ® max (min), х I Х (4.1)

Определенная таким образом задача называется задачей оптимизации. Множество Х называется допустимым множеством данной задачи, а функция f(x) - целевой функцией. [3]

Итак, оптимизационной является задача, которая состоит в выборе среди некоторого множества допустимых (т. е. допускаемых обстоятельствами дела) решений (Х) тех решений (х), которые в том или ином смысле можно квалифицировать как оптимальные. При этом допустимость каждого решения понимается в смысле возможности его фактического существования, а оптимальность - в смысле его целесообразности.[4]

Очень многое зависит от того, в каком виде задается допустимое множество Х. Во многих случаях это делается с помощью системы неравенств (равенств): [5]

q1 (х1, х2, … , хn) {? , = , ?} 0,

q2 (х1, х2, … , хn) {? , = , ?} 0, (4.2)

……………………………..

qm (х1, х2, … , хn) {? , = , ?} 0,

где q1, q2, … ,qm - некоторые функции, (х1, х2, … , хn) = х - способ, которым точка х задается набором из нескольких чисел (координат), являясь точкой n-мерного арифметического пространства Rn. Соответственно множество Х есть подмножество в Rn и составляет множество точек (х1, х2, … , хn) I Rn и удовлетворяющих системе неравенств (2.2.2).

Функция f(х) становится функцией n переменных f(х1, х2, … , хn), оптимум (max или min), который требуется найти.

Понятно, что следует найти не только само значение max (min) (х1, х2, … , хn), но и точку или точки, если их больше одной, в которых это значение достигается. Такие точки называются оптимальными решениями. Множество всех оптимальных решений называют оптимальным множеством. [6]

Задача, описанная выше, есть общая задача оптимального (математического) программирования, в основе построения которой лежат принципы оптимальности и системности. Функция f называется целевой функцией, неравенства (равенства) qi (х1, х2, … , хn) {? , = , ?} 0, i = 1, 2, … , m - ограничениями. [7] В большинстве случаев в число ограничений входят условия неотрицательности переменных:

х1 ? 0, х2 ? 0, … , хn ? 0,

или части переменных. Впрочем, это может быть и необязательным.

В зависимости от характера функций-ограничений и целевой функции различают разные виды математического программирования: [8]

1. линейное программирование - функции линейны;

2. нелинейного программирования - хотя бы одна из этих функций нелинейна;

3. квадратичного программирования - f(х) является квадратичной функцией, ограничения линейны;

4. сепарабельное программирование - f(х) представляет собой сумму функций, различных для каждой переменной, условия - ограничения могут быть как линейными, так и нелинейными;

5. целочисленное (линейное или нелинейное) программирование - координаты искомой точки х являются только целыми числами;

6. выпуклое программирование - целевая функция - выпуклая, функции - ограничения - выпуклые, то есть рассматриваются выпуклые функции на выпуклых множествах и т. п.

Наиболее простым и часто встречающимся является случай, когда эти функции линейны и каждая из них имеет вид:

а1х1 + а2х2 + … аnхn + b ,

то есть имеет место задача линейного программирования. Подсчитано, что в настоящее время примерно 80-85% всех решаемых на практике задач оптимизации относятся к задачам линейного программирования.[9]

Сочетая в себе простоту и реалистичность исходных посылок, этот метод вместе с тем обладает огромным потенциалом в области определения наилучших с точки зрения избранного критерия планов.

Первые исследования в области линейного программирования, ставившие своей целью выбор оптимального плана работы в рамках производственного комплекса относятся к концу 30-х годов нашего века и связаны с именем Л.В. Канторовича.[10] В отечественной научной традиции именно его принято считать первым разработчиком этого метода.

В 30-е гг., в период интенсивного экономического и индустриального развития Советского Союза, Канторович был в авангарде математических исследований и стремился применить свои теоретические разработки в практике растущей советской экономики. Такая возможность представилась в 1938 г., когда он был назначен консультантом в лабораторию фанерной фабрики. Перед ним была поставлена задача разработать такой метод распределения ресурсов, который; мог бы максимизировать производительность оборудования, и Канторович, сформулировав проблему с помощью математических терминов, произвел максимизацию линейной функции, подверженной большому количеству ограничителей. Не имея чистого экономического образования, он тем не менее знал, что максимизация при многочисленных ограничениях--это одна из основных экономических проблем и что метод, облегчающий планирование на фанерных фабриках, может быть использован во многих других производствах, будь то определение оптимального использования посевных площадей или наиболее эффективное распределение потоков транспорта.

Говоря о развитии этого метода на Западе, следует сказать о Тьяллинге Купмансе, американском экономисте-математике голландского происхождения.

В миссии торгового флота Купманс пытался так разработать маршруты флотов союзников, чтобы снизить до минимума затраты на доставку грузов. Задача была крайне сложной: тысячи торговых судов везли миллионы тонн грузов по морским путям между сотнями портов, рассеянных по всему миру. Эта работа предоставила возможность Купмансу применить свои математические знания к решению фундаментальной экономической проблемы - оптимальному распределению дефицитных ресурсов между конкурирующими потребителями.

Купманс разработал аналитическую методику, названную анализом деятельности, которая решительно изменила подход экономистов и руководителей к распределению маршрутов. Впервые он описал эту методику в 1942 г., назвав ее «Соотношение между грузами на различных маршрутах» ("Exchange Ratios Between Cargoes on Various Routes"), где показал возможность подхода к проблеме распределения как к математической проблеме максимизации в пределах ограничений. Величина, подлежащая максимальному увеличению, -- это стоимость доставленного груза, равная сумме стоимостей грузов, доставленных в каждый из портов. Ограничения были представлены уравнениями, выражающими отношение количества расходуемых факторов производства (например, судов, времени, труда) к количеству груза, доставленному в различные места назначения, где величина любой из затрат не должна превышать имеющуюся в распоряжении сумму.

При работе над проблемой максимизации Купманс разработал математические уравнения, которые нашли широкое применение как в экономической теории, так и в практике управления. Эти уравнения определяли для каждой из затрат на производство коэффициент, равный цене этой затраты в условиях идеальных конкурентных рынков. Таким образом была установлена основополагающая связь между теориями эффективности производства и теориями распределения через конкурентные рынки. Кроме того, уравнения Купманса представляли большую ценность для центральных планирующих органов, которые могли использовать эти уравнения для определения соответствующих цен на различные затраты, оставляя при этом выбор оптимальных маршрутов на усмотрение местных директоров, обязанность которых состояла в максимизации прибыли. Метод анализа деятельности мог широко применяться любыми руководителями при планировании процессов производства.

В 1975 году Л.В. Канторовичу и Тьяллингу Ч. Купмансу была присуждена Нобелевская премия «за вклад в теорию оптимального распределения ресурсов».

Говоря о первых исследованиях в области линейного программирования, нельзя также не упомянуть еще об одном американском ученом - Джордже Д. Данциге. Конкретная формулировка метода линейного программирования восходит к его работе, выполненной им по заказу ВВС США во время Второй Мировой войны, когда возникла проблема координации действий одной большой организации в таких вопросах, как накопление запасов, производство и содержание оборудования и материально-технического снаряжения, причем имелись альтернативы и ограничения. Кроме того, в свое время Дж. Данцинг работал совместно с В.В. Леонтьевым, и симплекс-метод решения линейных оптимизационных задач (наиболее часто применяемый для их решения) появился в связи с одним из первых практических применений метода межотраслевого баланса.

Тема 16. Общий вид задачи линейного программирования.

Линейное программирование (ЛП) - математический метод отыскания максимума или минимума линейной функции при наличии ограничений в виде линейных неравенств или уравнений («линейные» здесь означает, что на графике функции будут изображаться в виде прямых, обозначающих первые степени соответствующих величин). [11]

В общем виде постановка задачи ЛП заключается в следующем. Требуется найти экстремум (максимум или минимум) линейной целевой функции

f(х) = с1х1 + с2х2 + … + сnхn (4.3)

где х = (х1, х2, … , хn), при ограничениях (условиях), представленных с помощью системы линейных уравнений или неравенств:

а11х1 + а12х2 + … а1nхn {? , = , ?} b1 ,

а21х1 + а22х2 + … а2nхn {? , = , ?} b2 , (4.4)

………………………………………

аm1х1 + аm2х2 + … аmnхn {? , = , ?} bm ,

хj ? 0, j = 1, n .

где хj - искомые величины, содержащие решение поставленной задачи, bi и сj (i = 1, m, j = 1, n) - заданные постоянные величины, характеризующие условия задачи. [12]

Обычно включаемое в систему тривиальное условие [13] неотрицательности переменных хj ? 0 (j = 1, n) вытекает из реального экономического смысла разрешаемости задач.

Систему ограничений (4.4) называют функциональными ограничениями задачи ЛП, а ограничения хj ? 0 - прямыми. [14]

Наиболее часто встречается две разновидности задач ЛП: [15]

1) Каноническая задача ЛП. В этом случае система ограничений, помимо тривиальных ограничений (2.2.5) включает в себя только уравнения. В этом случае задача имеет следующий вид: найти экстремум функции

n

f(х) = a cjхj

j = 1 (4.5)

при наличии ограничений

а11х1 + а12х2 + … а1nхn = b1 ,

а21х1 + а22х2 + … а2nхn = b2 , (4.6)

……………………………..

аm1х1 + аm2х2 + … аmnхn = bm ,

хj ? 0, bi ? 0, i = 1, m, j = 1, n .

2) Стандартная задача ЛП. Это означает, что система условий состоит только из неравенств, в число которых входят тривиальные ограничения:

n

max (min) f(x) = a cjxj

j = 1

при наличии ограничений

а11х1 + а12х2 + … а1nхn {? , ?} b1 ,

а21х1 + а22х2 + … а2nхn {? , ?} b2 , (4.7)

……………………………..

аm1х1 + аm2х2 + … аmnхn {? , ?} bm ,

хj ? 0, bi ? 0, i = 1, m, j = 1, n .

Стандартная задача ЛП может быть сведена к канонической. Добавив в систему ограничений некоторые дополнительные переменные хn+k ? 0 со знаком "-" в случае ограничений типа ? и со знаком "+" в случае ограничений типа ?, можно превратить ее из системы неравенств в систему уравнений.

Переход от задачи на минимум к задаче на максимум (и наоборот) осуществим путем умножения целевой функции на - 1.

В качестве примера можно привести следующую задачу.[16]

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

Общая формулировка задачи соответствует условиям (4.5) и (4.6). Первая строка системы уравнений (4.6)

а11х1 + а12х2 + … а1nхn = b1,

в данном случае будет означать следующее:

а11 - количество единиц производственного ресурса вида 1, используемых на предприятии первого типа;

а12 - количество единиц ресурса вида 1, используемых на предприятии второго типа и т. д.

b1 - общее количество ресурса вида 1 (для предприятий всех типов);

х1, х2 и т. д. - искомое количество предприятий типов 1, 2 и т. д.

Вторая строка упомянутой системы содержит аналогичные величины для ресурса вида 2 и т. д.

Функция цели соответствует формуле (4.5). Требуется обратить в минимум величину

y = с1х1 + с2х2 + … + сnхn ,

где сj (j = 1, n) - показатель, характеризующий издержки предприятия.

Пусть m - общее число различных видов ресурсов, которыми располагает собственник, а n - число типов предприятий, между которыми эти ресурсы должны быть распределены. При этом известно, какое количество однородных ресурсов различного вида (i = 1, m) может быть реализовано на каждом из предприятий данного типа (j = 1, n). Известно также относительное значение издержек на каждом из предприятий (ij).

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

Решение задачи сведется к выполнению ограничений, заданных уравнениями типа (4.6) с учетом условия минимума целевой функции.

Имеется четыре вида ресурсов, которые могут быть распределены между шестью предприятиями, отличающимися друг от друга различиями в экономических условиях их деятельности. В зависимости от последних для предприятия каждого типа актуальны следующие относительные уровни издержек:

Таблица 4.1 Относительные издержки на предприятиях

Тип предприятия 1 2 3 4 5 6	Издержки 0,4 0,5 0,2 0,8 0,6 0,3

Пусть система уравнений, учитывающая ряд ограничений, сопряженных с распределением ресурсов по предприятиям, имеет вид, аналогичный условиям (4.6):

4х1 + х4 = 16,

2х2 + х5 = 10,

х3 + 2х4 + 6х5 = 76,

4х1 + 3х2 + х6 = 24,

хj ? 0, bi ? 0, i = 1, m, j = 1, n .

- для 1-го вида ресурсов

- для 2-го вида ресурсов

- для 3-го вида ресурсов

- для 4-го вида ресурсов

Смысл уравнений является следующим: первое означает, что ресурс вида 1 может быть размещен на предприятии 1-го типа в количестве 4 единицы и на предприятии 4-го типа в количестве 1 единица при общем лимите 16 единиц, второе - ресурс вида 2 может размещаться в количестве 2 на предприятии типа 2 и в количестве 1 единица на предприятии 5-го типа при лимите в 10 единиц. Аналогично раскрывается смысл остальных уравнений-ограничений. Последнее условие говорит о том, что число предприятий не может быть отрицательным.

В соответствии с таблицей 4.1 целевая функция, описывающая суммарно издержки всех предприятий имеет вид

y = 0,4*х1 + 0,5*х2 + 0,2*х3 + 0,8*х4 + 0,6*х5 + 0,3*х6 .

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

y = 0,4*х1 + 0,5*х2 + 0,2*х3 + 0,8*х4 + 0,6*х5 + 0,3*х6 > min.

Тема 17. Геометрия задачи линейного программирования.

Рассмотренная выше общая задача ЛП имеет явно выраженную геометрическую интерпретацию. Геометрическое представление задачи ЛП служит отправной точкой для наиболее часто используемого метода решения - симплекс метода.

Рассмотрим задачу ЛП в стандартной форме записи:

n

max (min) f(x) = a cjxj

J = 1

при ограничениях

а11х1 + а12х2 + … а1nхn ? b1 ,

а21х1 + а22х2 + … а2nхn ? b2 , (4.8)

……………………………..

аm1х1 + аm2х2 + … аmnхn ? bm ,

хj ? 0, j = 1, n .

Напомним, что множество Х, заданное в данном случае с помощью линейных ограничений, есть подмножество допустимых значений хj в множестве Rn.

Рассмотрим эту задачу в случае n = 2, т. е. множество Х допустимых планов определено в R2 - на плоскости.

Пусть система неравенств (4.8) с тривиальным ограничением хj ? 0 (j = 1, n) совместна (имеет хотя бы одно решение):

а11х1 + а12х2 ? b1 ,

а21х1 + а22х2 ? b2 ,

………………………………....

аm1х1 + аm2х2 ? bm

х1, х2 ? 0.

Каждое неравенство этой системы геометрически определяет полуплоскость с граничной прямой аjiх1 + аi2х2 ? bi (i = 1, …, m). Условия неотрицательности определяют полуплоскости с граничными прямыми х1 = 0 и х2 = 0. Система совместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством [17] и представляет собой совокупность точек, координаты (х1, х2) каждой из которых составляют решение данной системы.

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

Если в системе ограничений n = 3, то каждое неравенство геометрически представляет собой полупространство трехмерного пространства R3, граничная плоскость которого аi1х1 + аi2х2 + аi3х3 = bi, а условия неотрицательности - полупространства с граничными плоскостями соответственно хj = 0 (j = 1, 2, 3). Если система ограничений совместна, то эти полупространства, как выпуклые множества, пересекаясь, образуют в трехмерном пространстве R3 общую часть Х, которая будет являться многогранником решений.

Пусть в системе ограничений указанной задачи n > 3, тогда каждое неравенство определяет полупространство пространства Rn (n-мерного) с граничной гиперплоскостью аi1х1 + аi2х2 + … + аinхn = bi (i = 1, …, m), а условия неотрицательности - полупространства с граничными гиперплоскостями хj = 0, j = 1, …, n.

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

Целевая функция задачи ЛП тоже является выпуклой. Она описывается уравнением плоскости (или гиперплоскости - для числа переменных больше трех) f(х) = с1х1 + с2х2 + … + сnхn . Представим, что в вершинах выпуклого многоугольника области допустимых планов мы установим «столбы», высота которых определяет значения целевой функции в данной вершине. На эти «столбы» наложим плоскость (целевую функцию). Очевидно, что максимального и минимального значения целевая функция задачи ЛП достигает либо в вершине выпуклого многогранника, либо на одной из его граней. [18]

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

В описанной выше задаче о распределении ограниченных ресурсов между предприятиями различных типов n - m = 6 - 4 = 2 (n число неизвестных, m - число уравнений-ограничений). То есть каждое из ограничений, а также целевая функция (линейная) могут быть представлены геометрически в двухмерном пространстве.[19]

Из уравнений-условий можно некоторые переменные можно определить через другие, а именно x3, х4, х5, х6 через х1 и х2. Тогда из уравнений-условий следует:

х3 = 8х1 + 12х2 - 16,

х4 = 16 - 4х1,

х5 = 10 - 2х2,

х6 = 24 - 4х1 - 3х2.

Целевая функция, если выразить ее только через две переменные (х1 и х2), примет вид

y = -2,4*х1 + 0,8*х2 + 22,8 .

В этих выражения x3, х4, х5, х6 - это зависимые переменные, выраженные через независимые переменные х1 и х2.

Если сопоставить преобразованные уравнения-ограничения и последнее из ограничений исходной формулировки задачи (хj ? 0), то

х3 = 8х1 + 12х2 - 16 ? 0,

х4 = 16 - 4х1 ? 0,

х5 = 10 - 2х2 ? 0,

х6 = 24 - 4х1 - 3х2 ? 0.

х1 ? 0;

х2 ? 0.

Чтобы представить ограничения и целевую функцию графически, изобразим две координатные оси, соответствующие независимым переменным х1 и х2. Относительно них и будет производиться построение.

Разделив неравенства условия получившейся системы на некоторые числа, получим

x3 = x1 + 1,5*х2 - 2,

х4 = 4 - х1,

х5 = 5 - х2,

х6 = 6 - х1 - 0,75*х2,

х1 ? 0,

х2 ? 0.

Каждому из неравенств будет соответствовать полуплоскость, в пределах которой находятся допустимые значения хj (j = 1, 2, …, 6). Графики, описываемые этими неравенствами, изобразим на нашей координатной плоскости:

Например, неравенству x2 ? 0 соответствует полуплоскость вверх от оси х1. Аналогично, неравенству х5 = 5 - х2 соответствует полуплоскость вниз от граничного значения данного неравенства (х5 = 0). Таким же образом можно построить границы, определяемые и другими уравнениями.

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

Целевой функции соответствует семейство параллельных прямых. Рассмотрим, к примеру, одну из них, проходящую через начало координат, что имеет место при у = 22,8 (см. рис. 4.3). Она имеет наклон вправо относительно оси х2. Задаваясь различными значениями у, можно построить множество прямых, проходящих через точки, в которых значение переменной х2 равно 0. При этом, чем меньше значение у, тем правее будет располагаться соответствующая прямая.

Из всех планов нам более всего интересен оптимальный, при котором у достигает минимума. Тогда нас в наибольшей степени должна интересовать прямая, находящаяся как можно дальше вправо от прямой у = 22,8 и проходящая через многоугольник ABCDEF - прямая уmin.

Видно, что единственной точкой, соответствующей оптимальному плану, будет та вершина многоугольника ABCDEF, которая одновременно с тем, что она принадлежит многоугольнику области допустимых планов, отвечает требованию минимизации у - вершина С многоугольника. Из уравнений прямых, DC и BC, пересекающихся в этой точке, следует что х1 = 4, а х2 = 0.

Подставив полученные значения х1 = 4 и х2 = 0 в уравнения, в соответствии с которыми можно определить значения других, зависимых, переменных, получим следующий оптимальный план, которому будет соответствовать минимум целевой функции у:

х1 = 4,

х2 = 0,

х3 = 8*4 + 12*0 - 16 = 16,

х4 = 16 - 4*4 = 0,

х5 = 10 - 2*0 = 10,

х6 = 24 - 4*4 - 3*0 = 8.

При этом величина издержек будет минимальной:

y = 0,4*4 + 0,5*0 + 0,2*16 + 0,8*0 + 0,6*10 + 0,3*8 = 13,2

ЛИТЕРАТУРА http://kinovecher.ru/noplay/

[1] Абчук В.А. Экономико-математические методы: Элементарная математика и логика. Методы исследования операций. - СПб.: Союз, 1999. - С. 58

[2] Немчинов В.С. Экономико-математические методы и прикладные модели. - М.: Мысль, 1965. - С. 80

[3] см., например, Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. В 3-х ч. Ч. 1. - М.: Финансы и статистика, 1998. -С. 127

[4] Математика. БЭС / Гл. ред. Ю.В. Прохоров.- 3-е изд.- М.: Большая Российская энциклопедия, 1998.- С. 248

[5] Экономико-математические методы и прикладные модели/ Под. ред. Федосеева В.В. - М.: ЮНИТИ, 1999. - С. 21

[6] Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. В 3-х ч. Ч. 1. - М.: Финансы и статистика, 1998. - С. 128

[7] Экономико-математические методы и прикладные модели/ Под. ред. Федосеева В.В. - М.: ЮНИТИ, 1999. - С. 21

[8] Грешилов А.А. Как принять наилучшее решение в реальных условиях. - М.: Радио и связь, 1991. - С. 25

[9] Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. В 3-х ч. Ч. 1. - М.: Финансы и статистика, 1998. - С. 129

[10] см., например: Канторович Л. В., Горстко А.Б. Оптимальные решения в экономике. - М.: Наука, 1972. - 231 с.

[11] Абчук В.А. Экономико-математические методы: Элементарная математика и логика. Методы исследования операций. - СПб.: Союз, 1999. - С. 58

[12] Экономико-математические методы и прикладные модели/ Под. ред. Федосеева В.В. - М.: ЮНИТИ, 1999. - С. 25

[13] Солодовников А.С., Бабайцев В.А., Браилов А.В., Шандра И.Г. Математика в экономике. В 2-х ч. Ч. 1. - М.: Финансы и статистика, 1999. - С. 134

[14] Экономико-математические методы и прикладные модели/ Под. ред. Федосеева В.В. - М.: ЮНИТИ, 1999. - С. 26

[15] Солодовников А.С., Бабайцев В.А., Браилов А.В., Шандра И.Г. Математика в экономике. В 2-х ч. Ч. 1. - М.: Финансы и статистика, 1999. - С. 134

[16] из: Абчук В.А. Экономико-математические методы: Элементарная математика и логика. Методы исследования операций. - СПб.: Союз, 1999. - С. 60

[17] То есть наряду с любыми двумя своими точками содержит и отрезок, их соединяющий.

[18] Грешилов А.А. Как принять наилучшее решение в реальных условиях. - М.: Радио и связь, 1991. - С. 54

[19] см. Абчук В.А. Экономико-математические методы: Элементарная математика и логика. Методы исследования операций. - СПб.: Союз, 1999. - С. 62 - 64

[20] Грешилов А.А. Как принять наилучшее решение в реальных условиях. - М.: Радио и связь, 1991. - С. 53

[21] Там же.

[22] Математика. БЭС / Гл. ред. Ю.В. Прохоров.- 3-е изд.- М.: Большая Российская энциклопедия, 1998. - С. 543

[23] Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. В 3-х ч. Ч. 1. - М.: Финансы и статистика, 1998. - С. 156

[24] Абчук В.А. Экономико-математические методы: Элементарная математика и логика. Методы исследования операций. - СПб.: Союз, 1999. - С. 66

[25] Математическая экономика на персональном компьютере/ пер. с яп.: Под ред. М. Кубонива: Под ред и с предисл. Е.З. Демиденко - М.: Финансы и статистика, 1991. - С. 222

[26] Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. В 3-х ч. Ч. 1. - М.: Финансы и статистика, 1998. - С. 158

[27] Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. В 3-х ч. Ч. 1. - М.: Финансы и статистика, 1998. - С. 166

[28] Там же, С. 168

[29] см. Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. В 3-х ч. Ч. 1. - М.: Финансы и статистика, 1998. - С. 169 - 171.

[30] см., например, Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. В 3-х ч. Ч. 1. - М.: Финансы и статистика, 1998. - С. 172 - 179; Экономико-математические методы и прикладные модели/ Под. ред. Федосеева В.В. - М.: ЮНИТИ, 1999. - С. 61 - 64; Кремер Н.Ш., Путко Б.А., Тришин И.М., Фридман М.Н. Исследование операций в экономике: Учебное пособие для ВУЗов/ под ред. проф. Кремера Н.Ш. - М.: ЮНИТИ, 2000. - С. 94 - 97.

[31] Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. В 3-х ч. Ч. 1. - М.: Финансы и статистика, 1998. - С. 176

[32] Экономико-математические методы и прикладные модели/ Под. ред. Федосеева В.В. - М.: ЮНИТИ, 1999. - С. 67

[33] Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. В 3-х ч. Ч. 1. - М.: Финансы и статистика, 1998. - С. 191

[34] Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. В 3-х ч. Ч. 1. - М.: Финансы и статистика, 1998. - С. 191

[35] Там же, С. 187-189

[36] Экономико-математические методы и прикладные модели/ Под. ред. Федосеева В.В. - М.: ЮНИТИ, 1999. - С. 70

[37] Кремер Н.Ш., Путко Б.А., Тришин И.М., Фридман М.Н. Исследование операций в экономике: Учебное пособие для ВУЗов/ под ред. проф. Кремера Н.Ш. - М.: ЮНИТИ, 2000. - С. 108.

[38] Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. В 3-х ч. Ч. 1. - М.: Финансы и статистика, 1998. - С. 194

[39] Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. В 3-х ч. Ч. 1. - М.: Финансы и статистика, 1998. - С. 196

[40] Кремер Н.Ш., Путко Б.А., Тришин И.М., Фридман М.Н. Исследование операций в экономике: Учебное пособие для ВУЗов/ под ред. проф. Кремера Н.Ш. - М.: ЮНИТИ, 2000. - С. 110.

[41] см., например, Экономико-математические методы и прикладные модели/ Под. ред. Федосеева В.В. - М.: ЮНИТИ, 1999. - С. 69; Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. В 3-х ч. Ч. 1. - М.: Финансы и статистика, 1998. - С. 215 - 218.