Малыхин В.И. Математика в экономике

на

новую сумму. Найдите зависимость

от

цены

спроса

со

стороны

этих

людей

на

данный товар. Начертите графики спроса

при

разных

денежных

суммах, которые ежедневно расходуются

на

покупку

дан-

ного

товара.

Решение.

пределах некоторого

ин-

тервала изменения цены

спрос

будет

выражаться формулой:

Ь(р)

Q/р,

где

—

денежная сумма. Примерные графи-

ки

приведены

на

рис.

Задайте

полярной системе коор-

динат

вертикальные

горизонтальные

прямые линии.

Постройте графики функций

полярной

системе

координат:

а)

(спираль

Архимеда);

б)

я/<р

(гиперболическая спираль);

в)

10 sin

3(p

(трехлепестковая

роза).

Задайте параметрически линии

+ у

16,

Тема

ЛИНЕЙНЫЕ

МОДЕЛИ

ЭКОНОМИКЕ

3.1.

ЛИНЕЙНАЯ

МОДЕЛЬ ОПТИМАЛЬНОГО ПЛАНИРОВАНИЯ

Задача оптимального планирования.

теме

были

уже

описа-

ны

основные составляющие этой модели. Кратко повторим

их.

Пусть предприятие

из т

видов ресурсов производит

видов

про-

дукции. Предположим,

что для

производства одной единицы

у-го

вида продукции

расходуется

}}

единиц

/-го

вида

ресурса,

т.е.

{}

норма

расхода

/-го

ресурса

на

производствоу'-й

продукции. Матрица

(а

составленная

из

норм

расхода,

так и

называется

матрицей

норм

расхода

или

технологической.

Напомним,

чтоУ-й

столбец

А.

этой

матрицы

полностью

описы-

вает

расход ресурсов

на

производство

одной

единицыу-й

продукции,

/-я

строка описывает расход

(-го

ресурса

на

производство единицы

каждой

продукции

или при

единичной интенсивности каждой

тех-

нологии.

Пусть

с.

есть величина удельной прибыли

от

реализации одной

единицы

у'-и

продукции.

Эти

удельные прибыли образуют, вектор-

строку

С=

(с,

()

Тогда произведение

С-

Х=

с,х,

-К.,

пред-

ставляет собой величину прибыли, полученной

при

реализации

Х-

(х

{)

,..,

)

единиц произведенной продукции

(X—

вектор-стол-

бец,

но по

типографским соображениям иногда будем

его

записы-

вать

виде

вектора-строки).

Обозначим

эту

прибыль

f*(X).

Пусть

Ь,

обозначает

количество

единиц

/-го

ресурса,

запасен-

ного

на

складе. Запишем

эти

величины запасов

виде'

В -

(Ь,,...,

)

™

(Л

—

также

вектор-столбец).

Тогда

матрично-векторное

неравенство

АХ

< В

означает необходимость учитывать

ограниченность

запасов

ресурсов

при

рассмотрении

планов

производства.

Если

это

неравен-

ство

выполняется,

значит,

для

плана

хватит имеющихся запасов

ресурсов

В и

такой

план является

реальным

или,

как

говорят,

допус-

тимым.

Рассмотрим следующую

задачу

оптимального планиро-

вания;

найти

такой

план

производства

Х~

.,.,

который

бы

был

допустимым

обеспечивал

наибольшую

прибыль

из

всех

допусти-

мых

планов.

Эту

задачу записывают так;

с,*,

ч-...

с/

((

max,

ii*i

+•••

.Л

*Р

«>1

+•••'

**.

л-р

...,

О,

или

матрично-векторной

форме;

ДА)

C-J-»

max,

АХ**

В,

X>Q.

(Ограничение

X > 0

учитывает содержательный смысл задачи,

0 —

это

нулевой

вектор-столбец

такой

же

размерности,

что и

Л1)

Обозначим

множество всех планов, удовлетворяющих условиям:

в|Л

+»•

«|Л

+»•

«Л

*«»

ж,,

...,

х„

или

матрично-векторной форме:

АХ<

В,

Х>0

через

назовем

это

множество допустимым (множеством допусти-

мых

планов), тогда указанную выше

задачу

линейного программиро-

вания

(ЛП) можно сформулировать так: найти максимум

функции

Р(Х)

= С • X на

множестве

допустимых планов,

матрично-вектор-

ной

форме:

Р(Х)

max,

Некоторые общие сведения

линейном

программировании.

За-

дача оптимального планирования является самой важной

из

задач

так

называемого линейного программирования (ЛП),

Если

сформулировать задачу

ЛП без

экономической интерпре-

тации,

то она

такова;

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

при

линей-

ных

же

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

на

переменные.

При

этом

множество значений переменных,

удовлетворяющих

всем

(линейным)

ограничениям

задачи,

называется

допустимым

мпо'

жеством.

Допустимое

множество

представляет

собой

некоторое

мно-

гогранное

тело

линейном

числовом пространстве размерности,

равной числу переменных

задачи.

Линейная

же

функция, экстремум

которой

ищется, называется целевой

функцией,

Так, сформулированная чисто математическая задача называет-

ся

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

Сама

точка

экстремума,

если

она

существует, называется

опти-

мальным

решением

задачи

ЛП,

отличие

от

любой точки допустимого

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

решением)

задачи

ЛП.

Линейное

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

возникло

СССР.

конце 30-х

годов

XX в.

советский экономист-математик Леонид Витальевич

Канторович

открыл класс этих задач

придумал

некоторые

частные

методы

их

решения.

1975

фактически

за это

открытие

он был

удостоен Нобелевской премии

по

экономике,

что уже

свидетельст-

вует

большой важности задач

ЛП.

чисто

математической точки зрения задачи

ЛП

интересны

тем,

что

методы нахождения экстремумов

помощью производной

здесь

неприменимы.

Действительно,

рассмотрим простую задачу

П:

х — \

-ъ

max,

0<д;<3.

Поскольку

производная целевой

функции

равна

1, то

критических

то-

чек

исследуемом промежутке

нет и

найти

экстремум

по

классической схе-

ме

нельзя (рис.

1). И в

самом

деле,

максимум

целевой функции

точке

х= 3,

которая

не

является внутренней

точкой

области определения (методы

нахождения

экстремумов

помощью

производной рассматривались

еще в

школьной программе,

см.

так-

же

раздел

6.1).

На

практике иногда приходится решать такие задачи

ЛП, в ко-

торых

много видов ресурсов (иногда сотни

тысячи)

много видов

продукции

(тоже такого порядка).

Для

решения задач

ЛП

разработа-

ны

мощные математические методы

такие

задачи

сегодня

решают

только

на

компьютере.

Самый известный алгоритм решения задач

ЛП

— это так

называемый

симплекс-метод^

придуманный американ-

ским

математиком

Дж.

Данцигом

1949

г.

Теоретической основой

ЛП и

симплекс-метода являются

две

теоремы.

Ья

осношшя

теорема

ЛП.

Задача

ЛП

имеет

оптимальное

решение

тогда

только

тогда,

когда

целевая

функция

ограничена

па

допустимом

множестве

направлении

экстремума.

Эта

теорема

не

имеет

места

более общих ситуациях. Напри-

мер,

функция

\/х

ограничена

снизу

0 на

множестве

(0,

-1-°°),

но

точки

минимума

на

этом множестве

у нее

нет.

2-я

оенопная

теорема

ЛП.

Если экстремум

целевой

функции

задаче

ЛП

достигается,

то

он

достигается

некоторой

угло-

вой

точке допустимого

множества.

Точное определение угловой

точки

не

просто,

но нам оно не

нужно.

Нужно только понять,

что

допустимое множество

— то, на

котором ищется

экстремум,

— это

многранное

тело,

вершины это-

го

многогранного

тела

есть

угловые

точки.

Таких угловых

точек

—

конечное

число.

Сам

симплекс-метод

представляет

собой

направленный

пере-

бор

угловых точек допустимого множества

сторону приближения

искомой

точке экстремума.

При

анализе очередной угловой

точки

симплекс-метод указывает:

что эта

точка

—

искомая точка экстремума;

2) что

целевая функция задачи

не

ограничена

направлении

экстремума

и,

значит,

точки экстремума нет,

тем

самым

за-

дача

не

имеет решения;

какую угловую точку далее надо исследовать (при этом зна-

чение

целевой функции

следующей угловой точке будет

ближе

экстремуму).

Решение

задачи

ЛП

вручную

помощью

симплекс-метода

оформляется

виде специальных таблиц, называемых

симплексными

таблицами.

Однако решение задачи

ЛП уже

лишь

десятком

огра-

ничений

таким

же

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

так

что

применение

компьютера

просто

необходимо,

Решение

задач

ЛП с

двумя

переменными

графическим методом.

Решим

следующую

задачу

ЛП:

S(x

{

)

1х

{

2х

-»

max,

Зл,

я,

2х

На

плоскости возьмем

систему

координат (рис.

2).

Начало

— в

точ-

ке

0(0,

0), ось

{

направим вправо

горизонтально,

ось

—

вертикаль-

но

вверх. Приступим

построению

допустимого множества

3>,

Неравен-

ству

Зх,

< б

удовлетворяют точ-

ки

полуплоскости,

граница этой

полуплоскости есть прямая

линия

Зх,

- 6.

Проще

всего

эту

пря-

мую

построить

по

точкам пересече-

ния

ее с

осями координат (см.

п.

раздел

2.1).

Это

точки

(2,

0) и

(О,

6).

Чтобы узнать нужную полуплоскость, надо подставить

нера-

венство

Зх,

координаты какой-нибудь точки,

не

лежащей

на

прямой,

например точки 0(0,

0).

Неравенство

верно,

значит, иско-

мой

полуплоскрстыо

является

та, в

которой находится точка

0(0,

0). Это

показываем стрелкой.

Аналогично

поступаем

со

вторым ограничением. Получаем

еще

одну

полуплоскость

—

//.

Неотрицательность каждой переменной

дает

еще две

полуплоскости

—

правую

от

вертикальной

оси и

верх-

нюю

от

горизонтальной оси. Пересечение всех четырех полуплоско-

стей

дает

искомое допустимое множество

—

четырехугольник

ОАВС.

Слегка

заштрихуем его. Теперь

на нем

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

функции

S(x

Можно воспользоваться

2-й

основной теоремой

ЛП

(см,

выше).

данной ситуации

это

означает,

что

максимум

до-

стигается

какой-то

из

угловых точек

А,

В, С.

Координаты точек

О,

А, С

легко находятся:

0(0,

0),

Л(0,

3),

С(2,

0). Для

нахождения

координат

точки

надо

решить

систему

двух

уравнений:

Зх,

+х

-б,

+2х

Решая,

находим:

х,

6/5,

="12/5.

Теперь вычислим значения целе-

вой

функции

этих точках:

S(0)

О,

S(A)

S(£)

36/5,

S(Q

Видим,

что

максимум равен 36/5

достигается

он в

точке

5(6/5,

12/5).

Однако обычно экстремум находят

не

перебором угловых точек.

Рассмотрим линию

заданную уравнением

2х,

2х

е,

т.е.

ЯЦ,

)

е.

Заметим,

что в

каждой точке

значение функции

одно

и то же, а

именно

е.

Поэтому линия

так и

называется

—

линия

уровня

функции

S. На

рис.

показаны

две

линии уровня:

Заметим,

что

линии уровня

не

пересекаются

и в

данном случае

они

все

—

параллельные прямые линии, перпендикулярные своему нор-

мальному

вектору

-'(2,

(см.

п. 1,

раздел 2.1).

Этот

нормальный

вектор

показывает

направление,

котором

значения

функции

воз-

растают.

Поэтому

поисках максимума надо двигать линию уровня

направлении нормального вектора.

При

этом значения

исследуе-

мой

функции

будут возрастать. Последняя точка,

по

которой линия

уровня

еще

пересекает допустимое множество,

будет

точкой

максимума,

нашем случае

это

точка

В.

Итак,

ответ:

х,

6/5,

12/5; максимум функции

.У

равен 36/5.

Если

задаче нужно было найти минимум линейной функции,

то

линию уровня надо было двигать

сторону, противоположную

направлению

нормального вектора.

Из

общих теорем математического анализа

вытекает,

что

если

допустимое множество

задаче

ЛП

ограниченное,

то

целевая функ-

ция

имеет

на нем и

минимум,

максимум. Если

же

допустимое мно-

жество

не

ограничено,

то

экстремума может

и не

быть,

тогда

зада-

ча

ЛП не

имеет

решения.

На

рис.

показаны

решение

задачи

на

минимум

(рис.

3, а) и

решение

еще

одной задачи, когда точки мак-

симума

нет

из-за

неограниченности

целевой функции

направле-

нии

максимума (рис.

б).

Задачи целочисленного

ЛП.

Весьма часто некоторые

или все

переменные задачи являются

целочисленными,

т.е.

их

значениями

могут

быть только

целые

числа. Например, задача

трансформато-

рах

(см. раздел 1.2)

или

задачи

3, 4,

приведенные ниже. Такие задачи

решать много сложнее,

чем

обычные задачи

ЛП, хе. без

требования

целочисленности.

Для

решения таких задач разработаны спеииальт

ные

методы, например

так

называемый метод «ветвей

границ»

(ме-

тод

ВиГ).

Однако, если задача целочисленного

ЛП

имеет

две

пере-

менные,

то ее

можно

решить

графически.

Как и при

решении обыч-

ной

задачи

ЛП,

надо двигать линию уровня

направлении

экстрему-

ма и

уловить последнюю

целочисленную

точку.

Она и

даст

искомое

оптимальное

целочисленное решение (см. ниже задачу

2),

ЗАДАЧИ

Решите

задачу

ЛП:

1998х,

max,

я,

27,

2х

2^-2х

10,

ЯР

О,

>\.

Решете,

Складывая удвоенное

I -е

равенство

и 2-е

равенство,

получаем:

2я,

2х

32,

т.е.

я,

16.

Следовательно,

- П.

Учитывая,

сколь

различны коэффициенты

при

я,

целевой

функ-

ции,

приходим

выводу,

что

я,

должен быть

как

можно

больше,

значит,

— как

можно

меньше.

Получаем окончательно;

х,

ст

15;

максимальное

значение

целевой

функции

равно

026.

Решите

графически

задачу

целочисленного

ЛП;

10х,

9х

-»

шах,

Зх,

24, '

7л,

20х

140,

11,

х,,

—

целые

числа,

#,,

Что

собой

представляет

допустимое множество задачи, сколько

нем

элементов?

Решение. Сначала найдем

допус-

тимое

множество

без

учета

целочис-

ленности. Получим пятиугольник

OABCD

(рис.

4),

Подсчитаем, сколько

нем

точек,

обе

координаты

которых

целочисленны.

Таких точек

всего

39.

Их

множество

образует допустимое

множество задачи

(с

учетом

целочис-

ленности). Отложим нормальный

век-

тор

(10,

отточки

О.

Теперь

двигаем

прямую, перпендикулярную

этому

вектору,

в том

направлении, куда

ои

показывает.

Стараемся

уловить

по-

следнюю целочисленную точку.

Это

точка

(5, 4).

Максимальное

значение

целевой

функции

учетом

це-

лочисленности равно

95.

3. В

строительном тресте

тяжелых

и 10

легких экскаваторов.

Необходимость

в них

есть

трех

СУ,

выработка

которых

(в

куби-

ческих

метрах

за

сутки)

на

один тяжелый

один легкий экскаваторы

соответственно

таковы:

(150, 40), (180,

25),

(200, 30),

одно

СУ

можно

направить

не

более

экскаваторов. Составьте

решите

зада-

чу

определения числа тяжелых

легких

экскаваторов,

направляемых

каждое

СУ,

если

требуется

максимизировать

суммарную

суточную

выработку всех экскаваторов. Заметьте,

что это —

задача целочис-

ленного программирования.

Составьте задачу

ЛП для

нахождения минимального количе-

ства

листов

жести

13 х б м,

если требуется

не

менее

листов

2 х 3 и

листов

5x5.

Найдите

ответ

этой

задаче.

Это

также

задача

цело-

численного программирования.

Указание.

Рассмотрите

всевозможные

способы раскроя больших

ли-

стов

жести

на

средние

маленькие.

3.2. ДВОЙСТВЕННОСТЬ

ЛИНЕЙНОМ

.ПРОГРАММИРОВАНИИ

•

Теория

двойственности является центральной частью всего

ли-

нейного

программирования.

Она

имеет богатое экономическое

со-

держание.

Задача

торга.

Расссмотрим один цикл работы предприятия

технологической

матрицей

А,

векторами удельных прибылей

С и

запасов

ресурсов

В.

Соответствующая задача оптимального плани-

рования

развернутой форме;

i*i

+"-

max,

ii*i

+»•

*,.

.0)

«*Л

*,,

...,x

>0.

Предположим,

что к

Владельцу предприятия пришел Покупа-

тель

предложил продать

ему все или

часть

ресурсов,'запасенных

Владельцем. Почему

бы и

нет?

нормальной экономике

не

может

быть категорических отказов,

все

дело

цене. Начинается

торг

во-

круг

цен на

ресурсы

или,

лучше

сказать,

оценок ресурсов, потому

что

торг происходит

не на

рынке,

мало

ли

какие соображения могут

быть

и у

Владельца

и у

Покупателя. Обозначим оценку

/Чо

ресурса

через

у,.

Покупатель сразу

же

обозначил свою цель

заплатить

по-

меньше,

т.е.

уД

+ ... +

min.

Однако

Владельца свои резоны. Посмотрите, говорит

он, за

единицуу-й

продукции

получу прибыль

с,

истрачу

на

производство

единицы

этой

продукции

(а

...,

)

единиц различных

ресурсов,

поэтому разумно

так

оценить ресурсы, чтобы

ум„

+...

+ у а ,

с,

это

должно быть верно

для

всех видов продукции.

нов

°ЛП

СТе

аргументы

Вла

ель

ча

Покупателя

получим

У\

+-м

-»

max,

J'i

i,+~+J'A

(2)

J'A

<<V

^•.,^>0.

ти

n^Lf

зывает

Явственной

исходной

задаче

(1),

вместе

ничечтп

бразуют

ЭД"у

°Р^а.

Заметим,

что

каждому огра-

петРтГ,

ДН

3адаЧЧ)

каадом

ес

УР

У>

поставлена

соот-

ветствие двойственная переменная.

Из

дальнейшего будет

ясно,

что

оое

задачи

Имеют

оптимальные

решения. Оптимальное значение

двойственной

переменной,

соответствующей

данному

ресурсу,

назы-

вается

двойственной

оценкой

ресурса.

Симметричная пара

двойственных

задач.

Запишем задачу

(2) в

матрично-векторной форме.

Для

этого оценки ресурсов соберем

вектор-строку

У-

...,

Запишем также рядом

исходную

за-

дачу

(1). Получим

так

называемую

симметричную пару двойственных

задан:

Р(Х)

С-

Х-*

max,

S(Y)

Y-

-»

min,

АХ<В,

YB>C,

(3)

О,

Повторим,

как по

исходной задаче составить

двойственную:

тип

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

каждому ограничению исходной задачи ставится

соответ-

ствие переменная двойственной задачи;

свободные члены исходной задачи становятся коэффициен-

тами

при

переменных

целевой функции

двойственной

за-

дачи;

каждый столбец

коэффициентов

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

мирует ограничение двойственной задачи,

при

этом

тип не-

равенства меняется; коэффициенты

при

переменных

целе-

вой

функции исходной

задачи*становятся

свободными чле-

нами

соответствующих

неравенствах

двойственной задачи.

Этот

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

и для

составления

задачи,

двойственной

задаче

ЛП,

записанной

виде (2).

Таким образом, чтобы

данной задаче

ЛП

составить двойственную,

эту

задачу надо привести

виду

(1),

если задача была

на

максимум,

или

виду (2), если задача была

на

минимум,

после

этого

восполь-

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

Например, напишем

задачу,

двойственную

задаче

ЛП:

10х,

min,

*l>

*2>

°'

Так

как эта

задача

— на

минимум, преобразуем

все

неравенства

виду

«не

менее»

(>).

Получим

эквивалентную задачу

ЛП:

10х,

Зх

2л:

min,

- X

ЯР

> 0.

Малыхин В.И. Математика в экономике

Подождите немного. Документ загружается.