Математические анализы в экономике

1. Дайте алгоритм графического метода решения задач линейного программирования.

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

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

2. Дайте постановку задачи об использовании ресурсов и постройте соответствующую модель.

1. Задача об оптимальном использовании ресурсов при производственном планировании.

Общий смысл задач этого класса сводится к следующему.

Предприятие выпускает n различных изделий. Для их производства требуется m различных видов ресурсов (сырья, материалов, рабочего времени и т.п.). Ресурсы ограничены, их запасы в планируемый период составляют, соответственно, b1, b2,..., bm условных единиц.

Известны также технологические коэффициенты aij, которые показывают, сколько единиц i-го ресурса требуется для производства единицы изделия j-го вида (     ).

Прибыль, получаемая предприятием при реализации изделия j-го вида, равна cj.

В планируемом периоде значения величин aij, bi и cj остаются постоянными.

Требуется составить такой план выпуска продукции, при реализации которого прибыль преприятия была бы наибольшей.

Далее приведем простой пример задачи такого класса.

 

Компания специализируется на выпуске хоккейных клюшек и наборов шахмат. Каждая клюшка приносит компании прибыль в размере $2, а каждый шахматный набор - в размере $4. На изготовление одной клюшки требуется четыре часа работы на участке A и два часа работы на участке B. Шахматный набор изготавливается с затратами шести часов на участке A, шести часов на участке B и одного часа на участке C. Доступная производственная мощность участка A составляет 120 н-часов в день, участка В - 72 н-часа и участка С - 10 н-часов.

Сколько клюшек и шахматных наборов должна выпускать компания ежедневно, чтобы получать максимальную прибыль?

 

Условия задач указанного класса часто представляют в табличной форме (см. таблицу 2.1).

Таблица 2.1 - Исходные данные задачи об использовании производственных ресурсов

производственные  участки	затраты времени на единицу продукции, н-час		доступный фонд  времени, н-час
	клюшки	наборы шахмат
А	4	6	120
В	2	6	72
С	-	1	10
прибыль на единицу  продукции, $	2	4

 

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

Обозначим: x1 - количество выпускаемых ежедневно хоккейных клюшек, x2 количество выпускаемых ежедневно шахматных наборов.

Формулировка ЗЛП:

= 2x1 + 4x2 → max;
4x1 + 6x2≤ 120,  2x1 + 6x2 ≤ 72,  x2 ≤ 10;
x1 ≥ 0,   x2 ≥ 0.

Подчеркнем, что каждое неравенство в системе функциональных ограничений соответствует в данном случае тому или иному производственному участку, а именно: первое - участку А, второе - участку В, третье - участку С.

 

3. Опишите метод последовательного улучшения плана задач линейного программирования.

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

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

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

 

 

 

 

 

 

Пример. Найти решение системы неравенств

максимизирующее (минимизирующее) функцию  . На неизвестные   накладываются условия неотрицательности.

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

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

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

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

Таким образом, функция   достигает минимум в точке D, а   максимум – в точке А.

Найдём координаты точек D и А из решения систем линейных уравнений:

Определим соответствующие экстремальные значения целевой функции:

   

 

 

 

start="5"

 

Рис. 6.1. Графический метод решения задачи линейного программирования