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

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

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

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

Задача дробно-линейного программирования в общем виде записывается следующим образом:

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

,

где с_j, d_j, b_i, a_ij - постоянные коэффициенты.

.

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

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

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

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

.

Для решения этой задачи находят область допустимых решений.

Линии уровня проходят через начало координат. При некотором фиксированном L прямая займет определенное положение. При изменении значений L прямая будет поворачиваться вокруг начала координат (рис. 28).

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

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

.

Построим область допустимых решений - ? АВС (рис. 30).

Рисунок 30 - Область допустимых решений

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

Найдем координаты точки С.

,

получаем

х_опт = (3; 1), .

Следовательно, предприятию следует выпускать 3 изделия вида А и 1 изделие вида В. При этом средняя себестоимость одного изделия будет минимальной и равной 2,25 тыс. руб.

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

Обозначим

при условии

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

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

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

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

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

.

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

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

.

Обозначим

, , .

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

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

.

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

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

.

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

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

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

, , , .

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

, , .

Задание 14. Решить задачи дробно-линейного программирования двумя способами:

1. с дробной целевой функцией,

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

1.

.

2.

.

3.

.

4.

.

5.

.

6.

.

7.

.

8.

.

9.

.

10.

.

Цена 1 м тканей первого типа 2 у. е., второго типа - 2 у. е. В 1 м ткани первого типа содержится 2 ед. натуральных и 2 ед. искусственных волокон. В 1 м ткани второго типа содержится 2 ед. натуральных и 2ед. искусственных волокон. На производство тканей должно быть израсходовано не менее n тыс.ед. натуральных и не более m тыс.ед. искусственных волокон. Определить план производства тканей с общей минимальной себестоимостью.

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