INFONKO.RU

Модели линейного программирования

Общая линейная распределительная задача

Пусть предприятие может изготавливать изделия трех наименований П1, П2, П3. Известно, что для изготовления каждого изделия требуется три вида ресурсов, Объемы выпуска продукции измеряются в рублях.

Характеристики Виды продукции Располагаемые ресурсы
П1 П2 П3
Объем выпуска продукции
Ресурсы:
Трудовые 0,2 0,3 0,4
Материальные 0,5 0,4 0,3
Финансовые 0,6 0,8 1,2

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

Об = 7х1 + 12х2 + 13х3 max

0,2х1 + 0,3х2 + 0,4х3 < 35

0,5х1 + 0,4х2 + 0,3х3 < 42

0,6х1 + 0,8х2 + 1,2х3 < 100

хj ³ 0 , j = 1,3.

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

Таблица 1

Характеристики Виды продукции Располагаемые ресурсы
П1 П2 П3
Объем выпуска продукции
Качество продукции
Ресурсы:
Трудовые 0,2 0,3 0,4
Материальные 0,5 0,4 0,3
Финансовые 0,6 0,8 1,2

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

1) Метод последовательных уступок

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

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

Об = 7х1 + 12х2 + 13х3 max

9х1 + 7х2 + 10х3 ³ Кзад.

0,2х1 + 0,3х2 + 0,4х3 < 35

0,5х1 + 0,4х2 + 0,3х3 < 42

0,6х1 + 0,8х2 + 1,2х3 < 100

хj ³ 0 , j = 1,3.

Результаты решения этой задачи для различных Кзад. приведены в таблице 2.

Таблица 2

Характеристика Вариант
К зад. Неограничен
К
Об
П 1
П 2 29,5
П 3 47,8
Резерв ресурсов:
Трудовых 0,7
Материальных
Финансовых 1,2

Выводы:

1) Повышение требований к качеству продукции приводит к уменьшению объема ее выпуска.

2) В зависимости от требований к качеству продукции меняется структура плана.

3) Дальнейший рост выпуска продукции лимитируется ресурсами.

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



К1=9х1 + 7х2 + 10х3 max

7х1 +12х2 +13х3 ³ Об зад.

0,2х1 + 0,3х2 + 0,4х3 < 35

0,5х1 + 0,4х2 + 0,3х3 < 42

0,6х1 + 0,8х2 + 1,2х3 <100

хj ³ 0, j=1,3

Результаты решения задачи при различных значениях Обзад. – в таблице 3.

Выводы:

1) Структура плана меняется.

2) Повышение качества лимитирует ресурсы.

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

4) В варианте 6 достигнуто полное использование всех ресурсов. При этом качество продукции оказывается на самом низком уровне.

Таблица 3

Характеристики Вариант
Об зад. Неограничен
Об
К
П 1 48,6
П 2 23,8
П 3
Резерв ресурсов:
трудовых 1,7 0,9
Материальных
финансовых

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

Значения Об расставлен по мере возрастания качества К продукции.

Вариант
К
Об

Можно построить графически:


2) Многопараметрическая оптимизация

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

Возможной реализацией такого компромиссного подхода является формирование специальной целевой функции.

Два метода, обеспечивающие получение компромиссных решений:

а) компромиссная целевая функция;

б) оптимизация в смысле многоцелевого программирования.

а) Компромиссная целевая функция

КЦФ должна удовлетворять следующим требованиям:

1) приведение параметров, имеющих, как правило, различную размерность, к безразмерной форме;

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

3) увеличение значения целевой функции для улучшающих параметров и уменьшение для ухудшающих параметров.

Пример целевой функции, удовлетворяющей этим требованиям:

К - количество параметров, по которым производится оптимизация;


- нормирующая величина, обеспечивающая безразмерность параметров;

- коэффициент веса, задающие степень компромисса.

Значение величины можно назначать различными способами. Наиболее распространены два способа.

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

Во втором случае, если заданной величины нет, можно решить задачу при максимизации этой величины:

Полученное в результате оптимизации значения принять за нормирующее, т.е .

Коэффициенты веса назначаются при обеспечении условия с помощью экспертных оценок, получение которых мы уже рассмотрели.

Рассмотрим на примере прежней задачи. Оптимизация проводится по двум параметрам: объему и качеству выпускаемой продукции. Целевую функцию можно записать следующим образом:

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

Обн =1340

Кн =1028

Получим модель:

Об =7х1 + 12х2 + 13х3

К =9х1 + 7х2 + 10х3

0,2х1 + 0,3х2 + 0,4х3 < 35

0,5х1 + 0,5х2 + 0,3х3 < 42

0,6х1 + 0,8х2 + 1,2х3 < 100

хj³0, j = 1,3.

Результатом решения этой задачи при различных значениях коэффициентов a1 и a2 приведены в таблице 4.

Таблица 4

Характеристика Вариант
a1 1,0 0,5
a2 0,5 1,0
Е 94,4
Об
К
П 1
П 2
П 3
Резерв ресурсов:
трудовых 1,7
материальных
финансовых

Выводы:

1) Применительно к объему выпуска наиболее выгодна продукция П 2. По мере снижения коэффициента веса a1 ее выпуск уменьшается. Самая невыгодная – П1, которая при a1 =1,0 вообще не выпускается.

2) Наиболее выгодной с позиции качества является продукция П1, наиболее невыгодной П2, которая при a2 = 1,0 не выпускается.

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

б) Метод многоцелевого программирования

Решается задача последовательно по двум целевым функциям: максимизации объема и максимизации качества.

Получим результаты, согласно которым при располагаемых ресурсах максимально возможные значения объема выпуска и качества продукции соответственно равны 1340 и 1028. Одновременно такие значения получены быть не могут.

Примем, что необходимо обесп6ечить одновременно выполнение экономических показателей

Об = 1500

К = 1100

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

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

Об = 7х1 + 12х2 + 13х3= 1500

К = 9х1 + 7х2 + 10х3= 1100

0,2х1 + 0,3х2 + 0,4х3 < 35

0,5х1 + 0,5х2 + 0,3х3 < 42

0,6х1 + 0,8х2 + 1,2х3 < 100

хj³0, j = 1,3.

Решения у данной задачи нет (имеет несовместное решение).

Кроме того, в рассматриваемой системе нет целевой функции.

Для получения совместного решения, а также назначения целевой функции введем дополнительные переменные у1-у8 и заменим систему в виде

Об = 7х1 + 12х2 + 13х3 + у1 = 1500

К = 9х1 + 7х2 + 10х3 + у2 = 1100

0,2х1 + 0,3х2 + 0,4х3 + у3 = 35+у6

0,5х1 + 0,5х2 + 0,3х3 + у4 = 42+у7

0,6х1 + 0,8х2 + 1,2х3 + у5 = 100+у8

Смысл дополнительных переменных:

у1, у2 - показывают, насколько полученные значения объема выпуска и качества продукции отличаются от заданных;

у3, у4, у5 - определяют неиспользованный ресурс;

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

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

Введенные дополнительные переменные позволяют формулировать различные многопараметрические функции.

Рассмотрим две из них:

1) Е1=у1 + у2 ® min

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

3) Е2= у6 + у7 + у8 ® min

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

Результаты решения:

Характеристики Целевая функция
Е1 Е2
Е
Об
К
П1 45,8
П2 98,3
П3
у1
у2
у3
у4
у5
у6 3,6
у7 20,2
у8 6,1

Общая форма записи задачи может быть представлена как:

j=1, n i=1, m p=1,p

После введения дополнительных переменных эту систему запишем в виде:

j=1, n i=1, m p=1,p

Целевая функция может быть сформулирована следующим образом:

где m+p - число параметров, по которым ведется оптимизация;

ai - коэффициент веса, определяющий уровень компромисса между оптимизируемыми параметрами;

yi - дополнительные переменные, вводимые в целевую функцию;

bi - нормирующий элемент, аналогичный в компромиссной целевой функции.

Если нет каких-либо ограничений, исключающих получение значения yi = 0 (как это было в рассмотренных примерах), то величину bi можно не вводить. Если же в решении yi = 0 не может быть достигнуто, то следует вводить bi.

Контрольные вопросы самопроверки

1. Предложите ситуацию, в которой следует использовать модели теории очередей.

2. Предложите ситуацию, в которой следует использовать модели управления запасами.

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

Литература

1. Грамилов А.А. Как принять наилучшее решение в реальных условиях. - М.: ФиС,1991.

2. Ларичев О.И. Теория и методы принятия решений. – М.: ЛОГОС, 2000.

3. Мексон М.Х., Альберт М. Хедоури Ф. Основы менеджмента. – М.: Дело, 1997.

4. Черноруцкий И.Г. Методы оптимизации и принятия решений. – С.-П.: Лань, 2001.

Лекция 12



infonko.ru/rezhimnoe-i-operativnoe-obespechenie-otnositsya-k.html infonko.ru/rezhim-obrabotki-sili-i-momenti-sil-rezaniya.html infonko.ru/rezhim-pitaniya-pri-zanyatiyah-ozdorovitelnim-begom-i-hodboj.html infonko.ru/rezhim-raboti-asinhronnoj-mashini.html infonko.ru/rezhim-raboti-i-tehnicheskaya-proizvoditelnost.html infonko.ru/rezhim-raboti-predpriyatiya-i-fond-vremeni.html infonko.ru/rezhim-raboti-sinhronnogo-dvigatelya-pri-postoyannom-momente-i-peremennom-toke-vozbuzhdeniya.html infonko.ru/rezhim-raboti-sportivnih-sekcij.html infonko.ru/rezhim-regeneracii-informacii.html infonko.ru/rezhim-sluzhebnih-pomeshenij.html infonko.ru/rezhim-sozdat-sluzhebnuyu-zapisku-na-uregulirovanie-raznoglasij-po-razdelu-ii-pril-2.html infonko.ru/rezhim-svarki-listovogo-nastila.html infonko.ru/rezhim-ustanovit-nalichie-ili-otsutstvie-rashozhdenij-koreshok-akta.html infonko.ru/rezhim-vhozhdeniya-v-proceduru-prinyatiya-vozdushnih-vann-dlya-novichkov.html infonko.ru/rezhim-vstavki-i-zameni-simvolov.html infonko.ru/rezhisserskie-postanovochnie-priemi.html infonko.ru/rezhisserskij-zamisel-spektaklya-stepen-ego-obraznoj-konkretnosti.html infonko.ru/rezhisserskoe-i-plasticheskoe-reshenie-sceni-poedinka-v-tragedii-v-shekspira-gamlet.html infonko.ru/rezhisserskoe-i-plasticheskoe-reshenie-sceni-u-lauri-v-tragedii-a-s-pushkina-kamennij-gost.html infonko.ru/rezhissura-teatralizovannih-predstavlenij-i-prazdnikov.html