Графическое решение задачи распределения ресурсов

Пусть для двух видов продукции П₁ и П₂ требуются трудовые, материальные и финансовые ресурсы. Наличие ресурсов каждого вида и их нормы расхода, необходимые для выпуска единицы продукции, приведены в табл. 5.1.

Таблица 5.1

Характеристика	Вид продукции	располаг.
	П1	П2	ресурс
Резервы:
трудовые
материальные
финансовые
выпуск			---
прибыль		8,5	---
план	х1	х2	---

составим математическую модель задачи.

ìx₁+4x₂ £ 14

ï3x₁+4x₂ £ 18

(5.11) í6x₁+2x₂ £ 27

îx₁ ³ 0, x₂ ³ 0.

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

ìx₁/14+x₂/7/2 £ 1

ïx₁/6+x₂/9/2 £ 1

(5.12) íx₁/9/2+x₂/27/2 £ 1

îx₁ ³ 0, x₂ ³ 0.

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

F=x₁+x₂ ® max (5.13)

Эту зависимость представим в виде x₂= F-x₁. Из графика данного уравнения (Рис. 5.1) следует, что tga = -1, при этом a =135^о, а величина F равна отрезку, отсекаемому прямой функции цели на оси координат. Если прямую перемещать параллельно самой себе в направлении, указанном стрелками, то эта величина будет возрастать. Очевидно, что оптимальным решением будут координаты точки С (x^*₁; x^*₂). При этом F=F^*.

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

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

À Найти вершины ОДР, как точки пересечения ограничений.

Á Определить последовательно значения целевой функции в вершинах.

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

à Координаты оптимальной вершины являются оптимальными значениями искомых переменных.

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

Тот факт, что оптимальное решение находится на вершине ОДР, дает еще два очень важных вывода:

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

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

Как видно на Рис. 5.1, вершина, координаты которой являются оптимальным решением, определяется углом наклона прямой, описывающей целевую функцию. Значит, каждая вершина будет соответствовать оптимальному решению для некоторой целевой функции. Поясним это на рассмотренном ранее примере. Раньше мы находили оптимальное решение по максимизации суммарного выпуска F₁=x₁+x₂ ® max. Найдем оптимальные решения еще для четырех целевых функций:

F₂=x₂ ® max (максимизация выпуска продукции П₂)

F₃=x₁ ® max (максимизация выпуска продукции П₁)

F₄=4x₁+8,5x₂ ® max (максимизация прибыли)

F₅=(1+3+6)x₁ + (4+4+2)x₂ = 10х₁+10х₂ ® max (минимизация используемых ресурсов).

Для каждой целевой функции, так же как и для F₁, можно построить линию целевой функции и определить вершину, в которой целевая функция будет иметь оптимальное значение. Результаты решения задачи по пяти целевым функциям сведем в таблицу 5.2, из анализа которой можно сделать вывод: координаты каждой вершины могут быть оптимальным решением в некотором смысле.

Таблица 5.2

Целевая функция	Вершина	x1	x2	x1+x2	Прибыль	Используемый ресурс
F1=x1+x2 ® max	C		1,5	5,5	28,75
F2=x2 ® max	A		3,5	3,5	29,75
F3=x1 ® max	D	4,5		4,5
F4=4x1+8,5x2 ® max	B				33,5
F5= 10х1+10х2

Дата добавления: 2014-01-06