Учебное пособие рассмотрено и рекомендовано к публикации на заседании кафедры «Экономика отраслей и рынков»




НазваниеУчебное пособие рассмотрено и рекомендовано к публикации на заседании кафедры «Экономика отраслей и рынков»
страница12/12
Дата публикации01.10.2013
Размер1.09 Mb.
ТипУчебное пособие
vbibl.ru > Математика > Учебное пособие
1   ...   4   5   6   7   8   9   10   11   12

5 10 15 20 25 30 35 40 х1

Рис.П.2. Графическое представление задачи П.2

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

Целевая функция принимает наименьшее значение в точке В.

Визуально на графике координаты этой точки х1  7, х2  17.

Сделаем аналитическую проверку:

=0.52 – 110 = –9,

1 = 202 – 1100 = –60,

2 = 0.5 100 – 20 10 = –150.

Откуда х1 = –60 / –9 = 6.67, х2 = –150 / –9 = 16.67.

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

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

В обоих примерах множество допустимых планов определяется точками выпуклого многогранника, полученного в результате пересечения полупространств, заданных линейными неравенствами (П.1) и (П.2). Линейная целевая функция при двух переменных задает на плоскости семейство параллельных прямых, при трех переменных – семейство параллельных плоскостей в трехмерном пространстве, а в случае n переменных – семейство параллельных (n-1)–мерных пространств (гиперплоскостей) в n-мерном пространстве.

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

В силу этого подобный класс задач называют задачами линейного программирования.

Геометрически решение задачи линейного программирования сводится к следующим этапам:

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

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

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

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

Из анализа решения примеров делаем важный вывод:

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

Решение (план), которому соответствует вершина многогранника, называется базисным. Для нахождения базисного плана необходимо решить систему из n линейных уравнений с n неизвестными.

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

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

Дана система m линейных неравенств с n переменными

autoshape 3171 a11 х1 + a12 х2 + …+ a1n хnb1

a21 х1 + a22 х2 + …+ a2n хnb2

……………………………….. (П.3)

am1 х1 + am2 х2 + …+ amn хn  bm

и линейная функция

F = c1х1 + c2х2 + … + cnхn . (П.4)

Необходимо найти такое решение системы Х = (х1, х2,… , хn), где

хj  0 (j=1,2,…n), (П.5)

при котором линейная функция F (2.4) принимает оптимальное (максимальное или минимальное) значение.

Система (П.3) называется системой ограничений, а функция ^ F – целевой функцией, критерием или функцией цели.

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

F =  max( min)

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

bi (i=1,2,…,m),

xj  0 (j=1,2,…n).

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

В рассматриваемой задаче все неравенства вида “  “, хотя могут быть и вида ““, каждое такое неравенство, как мы видели на примерах, определяет полупространство в n-мерном пространстве. Постоянные коэффициенты aij являются, как правило, нормами расхода i-го ресурса на производство единицы j-го изделия (продукта). Коэффициенты bi задают предельные объемы использования i-го ресурса. Коэффициенты cj определяют удельную прибыль (или затраты) от производства единицы j-го изделия (продукта).

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

1.Ограничения могут оказаться несовместными, и задача не имеет решения.

  1. Целевая функция не ограничена в области допустимых планов, ее максимум ( или минимум)  +  (- ).

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

  3. Существует некоторое множество оптимальных решений (планов).

Если задача экономически поставлена правильно, то 1-й и 2-ой случаи исключаются.

^ 6. Двойственная задача линейного программирования.

В П.2 мы рассматривали общую задачу линейного программирования. Рассмотрим теперь другую экономическую задачу на том же предприятии с теми же исходными данными.

Необходимо определить такие цены

(y1  0, y2  0,…, ym  0 ) (П.6)

всех ресурсов, чтобы сумма потраченных средств на их приобретение была бы минимальна, т.е.

Z = b1 y1 + b2 y2 +…+ bm ym min. (П.7)

С другой стороны, предприятию будет выгодно продать ресурсы в случае, если выручка от их продажи будет не менее той суммы, которую предприятие может получить при изготовлении продукции из этих ресурсов. Т.к., на производство единицы продукции j расходуется a1j единиц ресурса 1, a2j единиц ресурса 2,…, amj единиц ресурса m, то для обеспечения выгодности продажи ресурсов необходимо выполнение следующих неравенств:

autoshape 3172 a11 y1 + a21 y2 +…+ am1 ymс1,

a12 y1 + a22 y2 +…+ am2 ymс2,

…………………………………. (П.8)

a1n y1 + a2n y2 +…+ amn ymсn,

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

Цены ресурсов y1, y2,…, ym получили различные названия: учетные, неявные, теневые. В отличие от «внешних» цен с1, с2 ,…, сn на продукцию, известных, как правило, до начала производства, цены ресурсов y1, y2,…, ym являются внутренними, ибо они определяются непосредственно в результате решения задачи, поэтому их чаще называют объективно обусловленными оценками ресурсов (Л.В.Канторович).

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

Z = 12 y1 + 18 y2 +15 y3  min. (П.9)

autoshape 219 2 y1 + 2 y2 + y3  5,

y1 + 3 y2 + 3 y3  6, (П.10)

y1  0, y2  0, y3  0.

Из алгебраических соображений легко показать, что FZ, откуда maxF=minZ, если они существуют (основная теорема двойственности).

В нашем примере 2.1 maxF = minZ = 40.5, и объективно обусловленные оценки y1= 0.75, y2 = 1.75, y3 = 0, вычисленные простым счетом в П.5, являются решением двойственной задачи (П.9)-(П.10).

Действительно, 120.75 + 181.75 + 150 = 40.5.

Из выражения (П.9) видно, что если увеличить в условии задачи какое-либо ресурсное ограничение bi на единицу, то Z (и следовательно F) также увеличится ровно на yi.

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

Рассмотрим теперь пример П.2 и построим для него двойственную задачу. Напомним, что в этом примере из сена и концентратов необходимо составить суточный рацион питания, калорийность которого 20 кормовых единиц, содержание белка 2000 гр., а кальция 100 грамм. Цена сена 1.5, а концентратов 2.5 усл.единиц за 1 кг. Пусть y1, y2, y3 - наша оценка (за единицу) полезности каждого из этих показателей. Тогда общая (условная) оценка рациона питания:

Z = 20 y1 + 2000 y2 +100 y3.

Мы будем стремиться максимизировать Z. Если 1 кг. сена содержит 0.5 кормовых единиц, 50г белка и 10 г кальция, то оценка его питательного содержания, т.е. 0.5 y1 + 50 y2 + 10 y3 , не может превышать его рыночной цены (1.5). Аналогично этому для концентратов оценка питательных веществ, равная y1 + 200y2 + 2y3, не может превышать 2.5. Следовательно, двойственную задачу можно сформулировать таким образом:

Найти такие оценки питательных веществ, чтобы

Z = 20 y1 + 2000 y2 +100 y3  mах (П.11)

при условии

autoshape 220 0.5 y1 + 50 y2 + 10 y3  1.5,

y1 + 200 y2 + 2 y3  2.5, (П.12)

y1  0, y2  0, y3  0.

Мы получили двойственную задачу к примеру П.2, в котором требовалось найти минимальную стоимость входящих в рацион продуктов питания при заданных рыночных ценах на эти продукты и при соблюдении ограничений в отношении потребности в питательных веществах. После введения условных оценок показателей питательности возникает двойственная задача (П.11)–(П.12), где требуется максимизировать условную оценку рациона питания при соблюдении ограничений, согласно которым расходы в расчете за единицу продукта не могут превышать его заданной рыночной цены. Цель первой, прямой задачи заключается в том, чтобы закупаемые продукты были, возможно, более дешевыми, удовлетворяя вместе с тем требованиям в отношении питательной ценности, а цель сопряженной двойственной задачи – в том, чтобы при заданных рыночных ценах на продукты получить рацион наиболее высокопитательный.

Имея краткую запись общей задачи линейного программирования в виде:

F =  max

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

bi (i=1,2,…, m),

xj  0 (j=1,2,…n).

можно так же кратко записать двойственную к ней задачу:

m

Z = biyi  min

i=1

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

m

aijyi  cj (j=1,2,…, n),

i=1

yi  0 (i=1,2,…, m).

Пример П.3. Дана исходная задача:

максимизировать линейную функцию F = 2х1 + 3х2  max

при ограничениях x1 + 3x2  18,

2x1 + x2  16,

x2  5,

3x1  21,

x1  0, x2  0.

Требуется составить задачу, двойственную к исходной задаче.

Решение.

Сформулируем двойственную задачу:

Z = 18 y1 + 16y2 + 5 y3 + 21 y4  min

при ограничениях y1 + 2y2 + 3y4  2,

3y1 + y2 + y3  3,

line 3153 yi  0, i = 1, 4.



1   ...   4   5   6   7   8   9   10   11   12

Похожие:

Учебное пособие рассмотрено и рекомендовано к публикации на заседании кафедры «Экономика отраслей и рынков» iconУчебное пособие рассмотрено и рекомендовано к печати на заседании...
...

Учебное пособие рассмотрено и рекомендовано к публикации на заседании кафедры «Экономика отраслей и рынков» iconЭкономика предприятия (Экономика предприятия и отрасли): учебное...
Рекомендовано в качестве учебного пособия Редакционно-издательским советом Томского политехнического университета

Учебное пособие рассмотрено и рекомендовано к публикации на заседании кафедры «Экономика отраслей и рынков» iconУчебное пособие для вузов под ред. В. М. Мапельман и Е. М. Пенькова...
Учебное пособие предназначено для студентов вузов и всех интере­сующихся философской проблематикой

Учебное пособие рассмотрено и рекомендовано к публикации на заседании кафедры «Экономика отраслей и рынков» iconУчебное пособие для студентов факультета «Мировая Экономика и Международные...
Учебное пособие для студентов факультета Мировая Экономика и Международные Отношения

Учебное пособие рассмотрено и рекомендовано к публикации на заседании кафедры «Экономика отраслей и рынков» iconУчебное пособие. Уфа, рио багсу, 1999. 128 с. Рекомендовано к изданию...
Абдуллин а. Р. Основы глобалистики: Учебное пособие. Уфа, рио багсу, 1999. – 128 с

Учебное пособие рассмотрено и рекомендовано к публикации на заседании кафедры «Экономика отраслей и рынков» iconМетодические рекомендации по подготовке к семинарским занятиям Иркутск 2012
Рассмотрено и рекомендовано к изданию кафедрой «Философия и социальные науки» Иркутского государственного университета путей сообщения...

Учебное пособие рассмотрено и рекомендовано к публикации на заседании кафедры «Экономика отраслей и рынков» iconУчебное пособие Допущено Министерством сельского хозяйства Российской...
Сурков И. М., Коротеев В. П. Резервы повышения эффективности сельскохозяйственного производства (методика расчета и мероприятия по...

Учебное пособие рассмотрено и рекомендовано к публикации на заседании кафедры «Экономика отраслей и рынков» iconУчебное пособие по русскому языку для самостоятельной работы студентов...
Учебное пособие рекомендовано для студентов всех факультетов неязыковых вузов. Предназначено для самостоятельной работы на начальном...

Учебное пособие рассмотрено и рекомендовано к публикации на заседании кафедры «Экономика отраслей и рынков» iconУчебное пособие Владим гос ун-т; 2007
Из книги "Экономика недвижимости", учебное пособие — Владим гос ун-т; 2007

Учебное пособие рассмотрено и рекомендовано к публикации на заседании кафедры «Экономика отраслей и рынков» iconПрограмма по дисциплине «Экономика организации» принята на заседании...
Государственного образовательного стандарта высшего профессионального образования по специальности 080105. 65 (060400) Финансы и...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
vbibl.ru
Главная страница