Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

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



 

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

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

 

 

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

 

 

где cj, dj, bi, aij постоянные коэффициенты и djxj ≠0.

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

 

 

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

 

 

Будем считать, что d1x1 + d2x2≠ 0.

Для решения этой задачи найдем область допустимых ре­шений, определяемую ограничениями (28.2). Пусть эта область не является пустым множеством.

Из выражения (28.1) найдем х2:

 

 

Прямая x2 = kx1 проходит через начало координат. При некотором фиксированном значении L угловой коэффициент k прямой тоже фиксирован и прямая займет определенное поло­жение. При изменении значений L прямая х2 = kx1 будет по­ворачиваться вокруг начала координат (рис. 28.6).

 

 

Установим, как будет вести себя угловой коэффициент k при монотонном возрастании L. Найдем производную от k по L:

 

 

Знаменатель производной всегда положителен, а числитель от L не зависит. Следовательно, производная имеет постоян­ный знак и при увеличении L угловой коэффициент будет толь­ко возрастать или только убывать, а прямая будет поворачи­ваться в одну сторону. Если угловой коэффициент прямой име­ет положительное значение, то прямая вращается против ча­совой стрелки, при отрицательном значении k — по часовой стрелке. Установив направление вращения, находим вершину или вершины многогранника, в которых функция принимает max(min) значение, либо устанавливаем неограниченность за­дачи.

 

 

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

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

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

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

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

 

Алгоритм решения

 

1. Находим область допустимых решений.

2. Определяем угловой коэффициент k и устанавливаем на­правление поворота целевой функции.

3. Находим точку max(min) целевой функции или устана­вливаем неразрешимость задачи.

 

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

 

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

Обозначим: rj прибыль предприятия от реализации еди­ницы изделия j-гo вида;

xj количество выпущенной продукции j-гo вида;

sj цена единицы продукции j-гo вида;

cj — себестоимость производства единицы изделия j-гoвида;

dj затраты на производство одного изделия j-гo вида.

Задача рентабельности (Рз) затрат на производство изде­лий имеет вид

 

 

Задача рентабельности (Рn) продаж имеет вид

 

 

Задача определения затрат (Зр) в расчете на рубль товар­ной продукции записывается в виде

 

 

Задача нахождения себестоимости изделия записывается как

 

 

Указанные математические модели имеют системы ограниче­ний в зависимости от условий задачи.

 

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

 

Рассмотрим использование дробно-линейного программи­рования для нахождении себестоимости изделий.

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

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

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

 

 

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

 

 

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

 

 

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

 

 

ΔАВС — область допустимых решений (рис. 28.11).

 

 

Найдем x2: L = (2x1 + 3x2) / (x1 + x2), 2x1 + 3х2 = Lx1 + Lx2, x2 (3 - L) = x1(L - 2),

 

 

Угловой коэффициент прямой равен k = (L - 2)/(3 — l), тогда

 

 

Так как dk/dL > 0, то функция k = (L - 2)/(3 - L) возрастает. Это соответствует вращению прямой против часовой стрелки. Следовательно, в точке С (рис. 28.11) целевая функция будет иметь наименьшее значение (глобальный минимум).

Найдем координаты точки С. Решая систему

 

 

получим С (3, 1), опт = (3, 1), L =9/4.

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

 

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

 

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

Обозначим

 

 

при условии

 

 

и введем новые переменные уj = y0xj.

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

 

 

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

 

 

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

Пример 7. Дана задача дробно-линейного программирования

 

 

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

 

 

Решение. Обозначим: x1 + 2x2 + 1 = 1/у0, y0 > 0, тогда L = 2x1y0 - x2y0.

Обозначим: x1y0 = y1, х2у0 = у2, х3у0 = у3, х4у0 = y4.

Преобразуем систему ограничений, умножив обе части всех ограничений на у0, и перейдем к переменным у0, y1, y2, y3, y4. Задача примет вид

 

 

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

 

 

 

Получили задачу линейного программирования, решаем ее симплексным методом (табл. 28.2).

Получим

 

 

тогда

 

 

Ответ: опт = (2, 0, 0, 2), Lmax = 4/3.

 

 




Поиск по сайту:

©2015-2020 studopedya.ru Все права принадлежат авторам размещенных материалов.