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

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

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

Решить задачу для самостоятельной работы из п. 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. Минимизировать (для выполнения условий по бюджету).

Дата добавления: 2014-12-29