Letysite.ru

IT Новости с интернет пространства
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Функции целевого программирования

Пример задачи целевого программирования;

Постановка задачи целевого программирования

Задания для самостоятельной работы

Решить задачу для самостоятельной работы из п. 6.9 с помощью Excel.

Результаты работы необходимо оформить в виде отчета, который должен содержать:

1. Описание проблемы принятия решения;

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

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

4. Сеть с оптимальным планом транспортировки.

ТЕМА 8. Целевое программирование

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

В методе весовых коэффициентов единственная целевая функция формируется как взвешенная сумма исходных частных целевых функций.

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

Рассмотрим основные этапы решения на следующем примере.

Новое рекламное агентство Simpson & Son, в составе которого 10 рекламных агентов, получило контракт на рекламу нового продукта. Агентство может провести рекламную акцию на радио и телевидении. В таблице (см. Табл. 1) приведены данные об аудитории, охватываемой каждым видом рекламы, стоимость этой рекламы и количество необходимых рекламных агентов. Все данные относятся к одной минуте рекламного времени.

Табл. 46 Данные рекламного агентства Simpson & Son

Реклама на радио и телевидении должна охватить не менее 45 миллионов человек, но контракт запрещает использовать более 6 минут рекламы на радио. Рекламное агентство может выделить на этот проект бюджет, не превышающий $100 000. Как наилучшим образом агентству спланировать рекламную акцию?

Обозначим через и количество минут рекламного времени, закупленного соответственно на радио и телевидении.

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

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

1. Минимизировать недостаток рекламной аудитории;

2. Минимизировать перерасход бюджета.

Нетрудно убедиться, что у этой задачи ЛП нет допустимого решения.

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

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

Переменная равна значению недостатка аудитории до 45 миллионов, а — избытку (превышению) аудитории над 45 миллионами. Так, если и , то обеспечивается аудитория в 44 миллиона человек, т.е. и общие расходы равны 99,5 тысяч долларов, т.е. . Аналогично и для переменных .

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

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

1. Минимизировать (для выполнения условий по рекламной аудитории);

2. Минимизировать (для выполнения условий по бюджету).

Целевое программирование (GP)

Целевое программирование — концепция, развивающая идеи линейного программирования, в основе которой лежит простое эвристическое соображение — стараться в качестве наилучшего выбрать такой возможный вектор, который в критериальном пространстве расположен ближе всех остальных допустимых векторов к некоторому «идеальному» вектору или же к целому множеству «идеальных» векторов.

Как известно, в рамках линейного программирования задача оптимизации может быть корректно поставлена и решена только при наличии единствен ного количественно определенного критерия оптимальности. Обычно это минимум затрат или максимум прибыли. Но реальные практические задачи в большинстве своем многокритериальны, т.е. ЛПР преследует несколько целей одновременно. В линейном программировании предусматривается возможность объединения нескольких целей в одну, но только если частные критерии измеряются в одних и тех же единицах (например, в рублях). В реальной жизни цели могут быть настолько разнообразными и противоречивыми (например, престиж фирмы, охрана окружающей среды, поддержание определенного социально-психологического климата в коллективе и т.д.), что свести их в одну не представляется возможным. Поэтому в 1950—1960-е гг. для реализации моделей линейного программирования в подобного рода задачах были разработаны идеи целевого программирования.

Читать еще:  Ошибка 0х80131700 как исправить

Родоначальниками целевого программирования считаются А. Варне и В. Купер, использовавшие в 1953 г. эвристические соображения для решения многокритериальной задачи линейного программирования. В 1961 г. они изложили свой метод’. Позже на эту тему были написаны десятки (если не сотни) статей и выпущено несколько книг. Авторы одного из наиболее полных современных курсов по этой тематике D. Jones, М. Tamiz [1] [2] отмечают труды S. М. Lee [3] , J. Р. Ignizio [4] и С. Romero [5] . Несмотря на указываемое многими авторами (например, В. Д. Ногиным [6] ) отсутствие логического фундамента, заменяемого эвристическими соображениями, методы целевого программирования широко используются при решении различных многокритериальных прикладных задач. Одним из первых известных инженерных приложений целевого программирования послужила выполненная J. Р. Ignizio оптимизация расположения антенн на разгонном модуле для вывода па орбиту космических летательных аппаратов «Сатурн», который применялся, в том числе, и для вывода на орбиту пилотируемого космического корабля «Аполлон», впервые доставившего человека на Луну.

  • [1] Charnes A., Cooper W. W. Management models and industrial applications of linear programming. New York : Wiley, 1961.
  • [2] Jones D., Tamiz M. Practical Goal Programming. New York : Heidelberg ; London : Springer.2010′. 172 p.
  • [3] Lee S. M. Goal programming for decision analysis. Philadelphia : Auerback, 1972.
  • [4] Ignizio J. P. Goal programming and extensions. Lexington, MA : Lexington Books, 1976.
  • [5] 3 Romero C. Handbook of critical issues in goal programming. Oxford : Pergamon Press, 1991.
  • [6] 11 Ногин В.Д. Принятие решений при многих критериях. СПб.: ЮТАС, 2007. 104 с.

Целевое программирование

Постановка задачи

Целевое программирование (ЦП) — это относительно новая концепция, развивающая идеи линейного программирования (ЛП) и призванная помочь в разработке управленческих решений в условиях многих целей. Как известно, одним из условий, при которых задача оптимального планирования может быть сформулирована и решена в рамках ЛП является наличие единого, четко сформулированного и количественно определенного критерия оптимальности плана в виде целевой функции. Обычно это минимум затрат или максимум прибыли. Но практика хозяйственной деятельности показывает, что это не единственные, а порой и не самые главные цели, которые приходится ставить и решать, планируя работу на перспективу. В ЛП предусматривается возможность объединения нескольких целей в одну, но в этом случае цели должны измеряться в одних и тех же единицах ( например, в рублях). В реальной жизни цели настолько разнообразны, а порой и противоречивы, что свести их в одну не всегда представляется возможным. Это цели и престижа фирмы, и охраны окружающей среды, и налаживания международных связей, и организация грамотной логистики и грузоперевозок, и поддержания определенного социально-психологического климата в коллективе и т.д., которые и в отдельности измерить не просто.

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

Ясно, что в условиях многих целей и ограниченности ресурсов не все цели могут быть достигнуты. В ЦП предусматривается такая возможность и для ее отражения вводится новый тип переменных, показывающий степень отклонения достигнутого уровня целей от желаемого (запланированного). Такие переменные будем называть отклонениями. Не следует смешивать их с балансовыми переменными, рассматриваемыми в ЛП. Балансовые переменные в ЛП показывают, на сколько правая часть ограничения отличается от левой, а переменные-отклонения в ЦП -степень недо- или перевыполнения конкретной цели. Кроме этих особенностей ЛП И ЦП отличаются конструкцией целевых функций. Если в ЛП непосредственно максимизируется или минимизируется одна конкретная цель, то в ЦП минимизируются отклонения между желаемыми и достигнутыми в пределах ограничений по ресурсам уровнями многих целей. Отсюда и роль отклонений. Если в ЛП балансовые переменные являются вспомогательными, то в ЦП отклонения играют решающую роль и формируют целевую функцию.

В условиях многих целей, их сложности и противоречивости, а так же ограниченности ресурсов, одни цели могут быть достигнуты за счет других. А это приводит к необходимости установления определенной иерархии целей так, чтобы цели нижнего приоритета выполнялись бы при условии реализации целей высшего приоритета. А поскольку возможна ситуация, когда не все цели могут быть достигнуты, то ЦП реализует алгоритм достижения возможного (удовлетворительного) уровня многих целей. Этим оно отличается от ЛП, в котором получают оптимальное решение для одной цели.

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

Читать еще:  Ошибка 4013 iphone 5s

Как уже отмечалось, будучи сформулированной, задача ЦП может быть решена методами, используемыми идеей ЛП. Не следует задачи ЦП отождествлять с многокритериальными задачами или с задачами векторной оптимизации. Это особые разделы математического программирования, которые здесь не рассматриваются.

Рассмотрим реализацию основных идей и методов решения задач ЦП на примере.

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

1. Получить не менее 30 ед. прибыли.

2. По возможности максимально использовать ресурс 1 вида.

3. Желательно не перерасходовать ресурс 2 вида.

4. Обеспечить контрактную поставку продукции 2 вида не менее 7 единиц.

Для формулировки модели задачи предположим, что прибыль от реализации единицы продукции равна соответственно 7 и 6 единиц, расход 1ресурса на выпуск единицы каждого продукта равен 2 и 3 единицы, соответственно, а объем 1 ресурса равен 12 единиц. Для 2 ресурса соответственно 6 и 5, и 30 единиц.

Составим модель задачи ЦП.

Основные неизвестные модели: Хi — объем производства продукции 1 вида; X2 — второго.

По прибыли: 7x1+6x2+d1 — -d1 + =30 слева записан объем прибыли с учетом недовыполнения 1-й цели (d1-) или ее перевыполнения (d1+ ). Если цель будет недовыполнена, то величина недовыполнения (d1-) будет больше нуля (d1 — >0) а перевыполнения (d1+) равна нулю (d1- = 0). И наоборот, в случае перевыполнения цели d1 + >0, a d1 — =0.

Если цель будет выполнена в точности, то d1+ = d1- = 0. В любом случае, по крайней мере одна из этих переменных будет равна нулю. Поскольку первая по приоритетности цель предусматривает получение не менее 30 ед.прибыли. то в целевой функции будем минимизировать недовыполнение, т.е. для этой цели, Z = P1d1-, где Р1 — весовой коэффициент.

соответственно недо- и перевыполнение 2-й цели. Для максимизации использования 1-го вида ресурса будем минимизировать d2-, следовательно, на этом этапе Z=P1d1 — +P2d2, причем P1>>P2 (P1 много больше P2).

Для реализации 4-й цели необходимо произвести продукции 2-го вида не менее 7 ед. следовательно, целевое ограничение примет вид: x2+d1 — -d1 + =7, а целевая функция: Z = P1d — + P2d2 — + P3d3 + + P4d4

Целевая функция

Функция, связывающая цель (оптимизируемую переменную) с управляемыми переменными в задаче оптимизации.

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

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

См. также

  • Бурак Я. И., Огирко И. В. Оптимальный нагрев цилиндрической оболочки с зависящими от температуры характеристиками материала // Мат. методы и физ.-мех. поля. — 1977. — Вып. 5. — С.26-30

Wikimedia Foundation . 2010 .

Смотреть что такое «Целевая функция» в других словарях:

целевая функция — — [Я.Н.Лугинский, М.С.Фези Жилинская, Ю.С.Кабиров. Англо русский словарь по электротехнике и электроэнергетике, Москва, 1999 г.] целевая функция В экстремальных задачах — функция, минимум или максимум которой требуется найти. Это… … Справочник технического переводчика

Целевая функция — [target function] в экстремальных задачах функция, минимум или максимум которой требуется найти. Это ключевое понятие оптимального программирования. Найдя экстремум Ц.ф. и, следовательно, определив значения управляемых переменных, которые к нему… … Экономико-математический словарь

целевая функция — 3.1.8 целевая функция (business function): Набор процессов, обеспечивающих достижение конкретной цели деятельности. Источник: Р 50.1.041 2002: Инфор … Словарь-справочник терминов нормативно-технической документации

целевая функция — tikslo funkcija statusas T sritis automatika atitikmenys: angl. objective function vok. Zielfunktion, f rus. функция цели, f; целевая функция, f pranc. fonction de cible, f … Automatikos terminų žodynas

Целевая функция — функция, экстремальное значение которой ищется на допустимом множестве в задачах математического программирования (См. Математическое программирование) … Большая советская энциклопедия

ЦЕЛЕВАЯ ФУНКЦИЯ — функция цели название оптимизируемой функции в задачах математического программирования … Математическая энциклопедия

Целевая функция — (условное название, относительно корректно может быть применено только к системам, созданным с определенной целью человеком), в объективном мире не существует, там имеет место системообразующий фактор … Теоретические аспекты и основы экологической проблемы: толкователь слов и идеоматических выражений

Целевая функция потребления — [objective function in con­sump­tion] 1. Этим термином, а также несколькими равнозначными ему или почти равнозначными (функция уровня жизни, функция благосостояния, функция общественной полезности, функция потребления и др.) обозначают в… … Экономико-математический словарь

Читать еще:  Не устанавливается вк ошибка 504

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

целевая функция автоматизированной медицинской системы — целевая функция АМС Совокупность действий автоматизированной медицинской системы, обеспечивающая эффективное выполнение заданной медицинской программы. [ГОСТ 27878 88] Тематики системы и комплексы медицинские Обобщающие термины системы и… … Справочник технического переводчика

Линейное программирование

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

Все или некоторые уравнения системы ограничений могут быть записаны в виде неравенств.
Чтобы составить математическую модель задачи ЛП, необходимо:

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

Задача условной оптимизации называется задачей линейного программирования (ЛП), если целевая функция и все функции ограничений являются линейными функциями: (5.1)
где ci,bj,aij постоянные коэффициенты. Это есть стандартная форма задачи ЛП. В общем случае ограничения могут иметь знак „» или „=». Однако, умножая неравенство на -1 и заменяя равенство двумя неравенствами „≤» и „≥», можно придти к стандартной форме. Кроме того, взяв вместо f(x) функцию — f(x), можно получить задачу на минимум.
Обозначим через c=(c1 ,…,cn) — вектор коэффициентов целевой функции, b =(b1,…,bk) — вектор свободных членов ограничений, — матрицу коэффициентов ограничений и запишем нашу задачу в векторной форме: (5.2)
где — скалярное произведение двух векторов c и x. Такая компактная запись удобна для теоретических исследований.
Несколько примеров задач, которые сводятся к задачам линейного программирования:

Задача оптимального раскроя материала. Фирма изготовляет изделие состоящее из р деталей. Причем в одно изделие эти детали входят в количествах k1 . kr . С этой целью производится раскрой m партий материала. В i-ой партии имеется bi единиц материала. Каждую единицу материала можно раскроить на детали n способами. При раскрое единицы i-ой партии j-м способом получается аijr деталей r-го вида. Требуется составить такой план раскроя материала, чтобы из них получить максимальное число изделий.

Транспортная задача. Имеется n поставщиков и m потребителей одного и того же продукта. Известны выпуск продукции у каждого поставщика и потребности в ней каждого потребителя, затраты на перевозки продукции от поставщика к потребителю. Требуется построить план транспортных перевозок с минимальными транспортными расходами с учетом предложения поставщиков и спроса потребителей.

Задача о назначениях на работу. Имеется n работ и n исполнителей. Стоимость выполнения работы i исполнителем j равна cij. Нужно распределить исполнителей на работы так, чтобы минимизировать затраты на оплату труда.

3адача о смесях (о рационе). Из m видов исходных материалов каждый из которых состоит из n компонент, составить смесь, в которой содержание компонент должно быть не меньше b1 . bn. Известны цены единиц материалов с1 . сm и удельный вес j-го компонента в единице i-го материала. Требуется составить смесь, в которой затраты будут минимальными.

Задача о рюкзаке. Имеется n предметов. Вес предмета i равен рi , ценность – сi (i=1. n). Требуется при заданной ценности груза выбрать совокупность предметов минимального веса.

Основные свойства задачи линейного программирования

Для любой задачи ЛП можно составить двойственную к ней задачу по следующим правилам.
1. Привести исходную задачу ЛП к стандартной форме.
2. Ввести новые переменные по числу основных ограничений исходной задачи.
3. Составить новые ограничения из новых переменных в виде линейных неравенств, знаки которых противоположны знакам неравенств исходной задачи, коэффициентами которых служат элементы транспонированной матрицы исходной задачи, а свободными членами — коэффициенты при целевой функции исходной задачи.
4. Для новых переменных написать условия неотрицательности.
В результате для исходной задачи (5.1) получим следующую двойственную задачу ЛП: (5.3)
Задача (5.1) относительно задачи (5.3) называется прямой задачей ЛП . Векторная форма задачи (5.3) имеет вид: (5.4)
Рассмотрение взаимно двойственных задач ЛП полезно как с теоретической, так и с практической точек зрения. Это видно из следующих утверждений.
1. Если одна из задач (5.1) и (5.3) имеет оптимальное решение, то и другая имеет оптимальное решение, причем
2. Если целевая функция одной из задач неограниченна, то ограничения другой задачи несовместны (т.е. множество допустимых решений пусто).
3. Для того, чтобы допустимое решение и были оптимальными решениями соответствующих задач (5.1) и (2.3) , необходимо и достаточно, чтобы

4. Для любых допустимых решений x 0 и y 0 справедливо неравенство f(x 0 ) ≤ z(y 0 ); если f(x 0 ) = z(y 0 ), то x 0 и y 0 — оптимальные решения задач (5.1) и (5.3).
5. Если прямая задача (5.1) моделирует максимизацию дохода при ограниченных ресурсах, то двойственная задача (5.3) при тех же предпосылках моделирует минимизацию затрат при фиксированном уровне дохода.

Ссылка на основную публикацию
Adblock
detector