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

Задание 1

Изложить материал по теме: Особые случаи решения ЗЛП графическим методом. Проиллюстрировать теоретические положения примерами.

 

Общая задача линейного программирования (ЗЛП) состоит в нахождении экстремального значения (максимума или минимума) линейной функции

   (1)

от n переменных при наложенных ограничениях

(2)

 

   (3)

 

где - заданные постоянные величины.

Линейная функция (1), для которой ищется экстремальное значение, называется целевой функцией. Условия (2) называются функциональными, а (3) – прямыми ограничениями задачи. Вектор , компоненты которого удовлетворяют функциональным и прямым ограничениям задачи называется допустимым решением ЗЛП. Все допустимые решения образуют область допустимых решений ЗЛП (ОДР). Допустимое решение, которое доставляет максимум или минимум целевой функции , называется оптимальным планом задачи.

Наиболее простым и наглядным методом решения задачи линейного программирования является графический метод. Он основан на геометрической интерпретации задачи линейного программирования и применяется при решении ЗЛП с двумя неизвестными:

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

Геометрически ЗЛП представляет собой отыскание такой угловой точки многоугольника решений, координаты которой доставляют максимальное (минимальное) значение линейной целевой функции, причем допустимыми решениями являются все точки многоугольника решений.

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

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

 

 

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

Графический метод решения ЗЛП состоит из 4-ех этапов:

1. Строится область допустимых решений ЗЛП.
2. Строится вектор-градиент целевой функции с началом в точке  (0,0): .
3. Линия уровня (a – постоянная величина) – прямая, перпендикулярная вектору-градиенту , - передвигается в направлении вектора-градиента в случае максимизации целевой функции до тех пор, пока не покинет пределов ОДР. При минимизации линия уровня перемещается в направлении, противоположном вектору-градиенту. Крайняя точка (или точки) ОДР при этом движении и является точкой максимума (минимума) .
4. Определяются координаты точки максимума (минимума). Для этого достаточно решить систему уравнений прямых, дающих в пересечении точку максимума (минимума). Значение , найденное в полученной точке, является максимальным (минимальным) значением целевой функции.

Особые случаи графического метода

1. Не единственность решения

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

2. Не ограниченность решений

Точка максимума бесконечно удалена и

Пример:

Найти максимум :

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

                                  

Решение:

1)

	0	1/2
	-1	0

 

О(0,0): 2*0-0≥1 не верно

	0	2
	-1	0

 

О(0,0): 0-2*0≤2  верно

 

ОДР задачи – выпуклый многоугольник

2) =(3,3)

Смотри рис. 1

Задача не имеет решения, так как целевая функция не ограничена сверху на ОДР.

 

3. Вырожденность решения

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

4. ОДР одна единственная точка.

Тогда точка максимума = точка минимума = ОДР

 

5. ОДР пуста.

Пример:

Найти максимум :

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

                                  

Решение:

1)

	0	0,25
	0,25	0

 

О(0,0): 0+0≤0,25  верно

	0	1/2
	-1	0

 

О(0,0): 2*0-0≥1  не верно

	0	2
	-1	0

 

О(0,0): 0-2*0≤2  верно

 

 

Смотри рис. 2

Задача не имеет решения, система ограничений несовместна. Область допустимых решений пуста.

 

Задание 2

Решить графическим методом типовую задачу оптимизации:

Инвестор, располагающий суммой в 300 тыс. ден. ед., может вложить свой капитал в акции автомобильного концерна А и строительного предприятия В. Чтобы уменьшить риск, акций А должно быть приобретено по крайней мере в 2 раза больше, чем акций В, причем последних можно купить не более чем на 100 тыс. ден. ед. Дивиденды по акциям А составляют 8% в год, по акциям В – 10 %. Какую максимальную прибыль можно получить в первый год? Построить экономико-математическую модель задачи, дать необходимые комментарии к ее элементам и получить решение графическим методом. Что произойдет, если решать задачу на минимум, и почему?

Решение:

1) - тысячи ден. единиц, которые нужно вложить в акции А.

    - тысячи ден. единиц, которые нужно вложить в акции В.

F – максимальный доход инвестора за 1 год.

 

1. ОДР

А)

 

	0	300
	300	0

 

О(0,0): 0+0≤300 верно

 

Б)

О(0,0): 0≤100 верно

В)

	0	200
	0	100

 

А(200,0): 200-2*0≥0 верно

Г)

ОДР задачи – треугольник АВС. Смотри рис.3

2. т. min, т. max

1000*

A(0,0) – т. min

B(200,100) – т. max

3. Определение оптимальных значений функции: ,

Решение задачи означает, что нужно вложить 200 акций в автомобильный концерн А и 100 акций в строительное предприятие В, чтобы получить максимальную прибыль 26 тыс. ден. ед.

Если решать задачу на минимум, то получим следующие выводы: если инвестор не будет приобретать акции, то он не получит прибыли.

 

Проверка

Задание 3

Рассчитать параметры моделей  экономически выгодных размеров заказываемых партий: На склад доставляют пиломатериалы на барже по 1500 т. В сутки со склада потребители забирают 100 т пиломатериалов. Накладные расходы по доставке партии пиломатериалов равны 3 тыс. руб. Издержки хранения 1 т пиломатериалов в течение суток равны 0,2 руб. Требуется определить:

1) длительность  цикла, среднесуточные накладные  расходы и среднесуточные издержки  хранения,

2) эти же величины  для размеров партии в 500 т и в 3000 т,

3) каковы оптимальный  размер заказываемой партии и  расчетные характеристики работы  склада в оптимальном режиме. Постройте график общих годовых  затрат.

Решение:

Параметры работы склада: М=100 т/сут., К=3 тыс. руб., h=0.2 руб./т-сут., Q=1500т

 

1)

- длительность цикла

- среднесуточные накладные расходы

-среднесуточные издержки хранения

 

2) Аналогичные расчеты проводятся  для  =500 т:

   - длительность цикла

  - среднесуточные накладные расходы

 

  - среднесуточные издержки хранения

 

и для =3000 т:

   - длительность цикла

  - среднесуточные накладные расходы

  - среднесуточные издержки хранения

 

3)

- оптимальный размер заказываемой партии

  - оптимальный средний уровень  запаса

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

- оптимальные средние издержки  хранения запасов в единицу  времени

4)

Построим график общих годовых затрат