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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

ДРОБНО-ЛИНЕЙНОЕ ПРОГРПАММИРОВАНИЕ



СОДЕРЖАНИЕ

Введение

Экономическая и геометрическая интерпретации задач дробно- линейного программирования (ДЛП)

Графический метод решения задачи ДЛП

Сведение задачи ДЛП к задаче линейного программирования

Решение задачи ДЛП симплекс-методом

Заключение

Список использованной литературы



ВВЕДЕНИЕ

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



Экономическая и геометрическая интерпретации задач дробно- линейного программирования

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

Дробно-линейное программирование относится к нелинейному программированию, так как имеет целевую функцию, заданную в нелинейном виде.

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

(1)

при условиях

, (i=1,...,m) , (2)

Xj?0 (j=1,…,n), (3)

где сj , dj ,bj и аij - некоторые постоянные числа,

(j=1,…,n), и

в области неотрицательных решений системы линейных уравнений (2). При этом будем предполагать,

что

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

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

Рассмотрим задачу, состоящую в определении максимального значения функции:

(4)

при условиях ai1x1+ai2x2 bi (i=1,…,m), (5)

x1 ,x2. (6)

Будем считать, что

Чтобы найти решение задачи (4)-(6), сначала находим многоугольник решений, определяемый ограничениями (5) и (6). Предполагая, что этот многоугольник не пуст, полагаем значение функции равным числу h так, что прямая:

, (7)

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

Рисунок 1 - Поворот линий уровня вокруг начала координат.

При этом возможны следующие случаи (рис. 2).



Рисунок 2 - Варианты областей допустимых решений.

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

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

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

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

Итак, процесс нахождения решения задачи (4)-(6) включает следующие этапы:

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

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

3. Находят многоугольник решений задачи.

4. Строят прямую (7), уравнение которой получается, если положить значение целевой функции (4) равным некоторому постоянному числу.

5. Определяют точку максимума или устанавливают неразрешимость задачи.

6. Находят значение целевой функции в точке максимума.

Математическая модель задачи ДЛП

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

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

Тип оборудования	Затраты времени на обработку одного изделия, ч
	А	В
I	2	8
II	1	1
III	12	3
Затраты на производство одного изделия, тыс. руб.	2	3



Оборудование I и III типов предприятие может использовать не более 26 ч и 39 ч соответственно, оборудование II типа целесообразно использовать не менее 4 ч.

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

Решение. Составим математическую модель задачи. Пусть х1 - количество изделий вида А, которое следует изготовить предприятию, х2 - количество изделий вида В. Общие затраты на их производство составят (2х1+3х2) тыс. руб., а средняя себестоимость одного изделия будет равна:

Математическая модель задачи примет вид:

(8)

при ограничениях, которых получим ниже.

Затраты времени на обработку указанного количества изделий на каждом из оборудования соответственно составят часов, часов и часов. Так как оборудование I и III типов может быть занято обработкой изделий вида А и В не более 26 и 39 часов, а оборудование II типа - не менее 4 ч, то должны выполнятся следующие неравенства:

(9)

По своему экономическому смыслу переменные x1 и x2 могут принимать только лишь неотрицательные значения:

x1 , x2 (10)

Таким образом, математическая постановка задачи состоит в определении неотрицательного решения системы линейных неравенств (9), реализующего минимум функции (8). Чтобы найти решение задачи, прежде всего построим многоугольник решений. Как видно из рис. 3, им является треугольник ВCD. Значит, функция (8) принимает минимальное значение в одной из точек: В, С или D. Чтобы определить, в какой именно, положим значение функции F равным некоторому числу, например 11/4. Тогда

или

-3x1+x2=0 (11)

Уравнение (11) определяет прямую, проходящую через начало координат. Координаты точек, принадлежащих этой прямой и многоугольнику решений, являются планами задачи, при которых значение функции (8) равно 11/4. В данном случае к указанным точкам относятся лишь одна точка В (1; 3). Ее координаты определяют план задачи, при котором значение функции равно 11/4.



x2

13

12

11

10 2x1+8x2=26

9

8

7

6

5

4 B

3 C

2

1 D x1+x2=4 12x1+3x2=39

-1 -1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 x1

-2

Рисунок 3.

Возьмем теперь h=5/2, т.е. положим

или

-x1+x2=0 (12)

Уравнение (12), так же как и (11), определяет прямую, проходящую через начало координат. Ее можно рассматривать как прямую, полученную в результате вращения по часовой стрелке вокруг начала координат прямой (11). При этом координаты точек, принадлежащих прямой (12) и многоугольнику решений, являются планами задачи, при которых значение функции (8), равное 5/2, меньше, чем в точках прямой (11). Следовательно, если положить значение функции (8) равным некоторому числу h0:

, (13)

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

, где h<h0.

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

Найдем последнюю общую точку вращаемой прямой с многоугольником решений. Это точка D (3; 1) (рис. 3), в которой достигается минимум функции (8).

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

Fmin = =.

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

, (14)

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

Практически же дело обстоит гораздо проще. Найдя точки В (1; 3) и D (3; 1) (рис. 3),в которых функция (8) может принимать минимальное значение, вычислим ее значения в этих точках: F (B)=11/4, F (D)=9/4. Так как F (B)> F (D), то можно утверждать, что в точке D целевая функция принимает минимальное значение. Одновременно с этим заметим, что в точке B функция F принимает максимальное значение.

Сведение задачи дробно-линейного программирования к задаче линейного программирования

Сформулированная выше задаче (4)-(6) может быть сведена к задаче линейного программирования. Для этого следует обозначить

y0 = (15)

и ввести новые переменные

yj = y0xj (j=1,,,n). (16)

Используя введенные обозначения, исходную задачу (4)-(6) сведем к следующей: найти максимум функции

F= (17)

при условиях

i=1,,,m; (18)

(19)

yj (yj=1,,,n) и y0 . (20)

Задача (17)-(20) является задачей линейного программирования, а следовательно, ее решение можно найти известными методами. Зная оптимальный план этой задачи, на основе соотношений (16) получаем оптимальный план исходной задачи (4)-(6).

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

1. Сводят задачу (4)-(6) к задаче линейного программирования (17)-(20).

2. Находят решение задачи (17)-(20).

3. Используя соотношения (16), определяют оптимальный план задачи (4)-(6) и находят максимальное значение функции (4).

Пример. Найти максимальное значение функции

(21)



при условиях

(22)

x1, x2, …, (23)

Решение. Сведем данную задачу к задаче линейного программирования. Для этого обозначим (x1+x2)-1 через y0 и введем новые переменные yj = y0xj (j = 1,…,5). В результате приходим к следующей задаче: найти максимум функции

F = 2y1 + y2 (24)

при условиях

(25)

y1+y2=1

y0, y1, …, y5 (26)

Задача (24)-(26) является задачей линейного программирования. Ее решение находим методом искусственного базиса (табл. 2).

Оптимальным планом задачи (24)-(26) является y1*=9/10; y2*=1/10; y3*=y4*=0; y5*=15/10; y0*=1/10.

Учитывая, что yj = y0xj, находим оптимальный план задачи (21)-(23): Х*=(9; 1; 0; 15). При этом плане Fmax = 19/10.

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

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

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

.

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

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

.

Обозначим

, , .



Тогда задача принимает вид:

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

.

Решим полученную задачу симплекс-методом. Введем дополнительную переменную, чтобы получить единичный базис:

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

.

Составляем симплекс-таблицу.

Базис	План						z
	0	-10	4	1	1	0	0
	0	-10	1	4	0	1	0
z	2	8	3	2	0	0	1
L	-2M	-8M	-3M-2	-2M-1	0	0	0

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

Базис	План						z
	5/2	0	31/4	7/2	1	0	5/4
	5/2	0	19/4	13/2	0	1	5/4
	1/4	1	3/8	1/4	0	0	1/8
L	0	0	-2	-1	0	0	M

Базис	План						z
	10/31	0	1	14/31	4/31	0	5/31
	30/31	0	0	135/31	-19/31	1	15/31
	4/31	1	0	5/62	-3/62	0	2/31
L	20/31	0	0	-3/31	8/31	0	M+10/31

Базис	План						z
	2/9	0	1	0	26/135	-14/135	1/9
	2/9	0	0	1	-19/135	31/135	1/9
	1/92/3	1	0	0	-1/27	-1/54	1/18
L		0	0	0	11/45	1/45	M+1/3

Получили решение

, , , .

Тогда, возвращаясь к исходным переменным, получим:



, , .



ЗАКЛЮЧЕНИЕ

В процессе выполнения данной курсовой работы были решены следующие задачи:

1) раскрыты основные понятия дробно-линейного программирования;

2) рассмотрены методы решения задач дробно линейного программирования;

3) изучен алгоритм сведения модели дробно-линейного программирования к линейному;

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



СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Акулич И.Л. Математическое программирование в примерах и задачах. - М.: Высшая школа, 1986. 317 с.

2. Волошин Г.Я. Методы оптимизации в экономике. - М.: Дело и сервис, 2004. 320с.

3. Левин В.И. Интервальные методы оптимизации систем в условиях неопределенности. - Пенза: Изд-во ПТИ, 1999. 101с.

4. Кузнецов Ю.Н. Математическое программирование. -М.: Высшая школа, 1980. 300 с.

5. Кузнецов Ю.Н. Холод Н.И., Костевич Л.С. Руководство к решению задач по математическому программированию. - Мн.: Выш. шк., 1978.?158 с.

6. Математическое программирование и экономико-математические методы. Учебное пособие / И.И. Холявин - М.: 2009. - 58?63 с.

Размещено на Allbest.ru