Линейное программирование. Анализ оптимального решения
Основные определения, понятия, постановка задачи
Линейное программирование – наука о методах исследования и отыскания экстремальных (наибольших и наименьших) значений линейной функции, на неизвестные которой наложены линейные ограничения.
Эта линейная функция называется целевой, а ограничения, которые математически записываются в виде уравнений или неравенств, называются системой ограничений.
В общем виде математическая модель задачи линейного программирования (ЛП) записывается как
Z(x) = ∑Ci Xi → max(min)
при ограничениях:
где Xi - неизвестные; aij , bj , Ci - параметры.
Все или некоторые уравнения системы ограничений могут быть записаны в виде неравенств.
Допустимым решением (планом) задачи линейного программирования называется вектор X = (х1, х2, ,...хn, ) удовлетворяющий системе ограничений.
Допустимое решение, при котором целевая функция достигает своего экстремального значения, называется оптимальным решением задачи линейного программирования и обозначается Хопт.
Чтобы составить математическую модель задачи ЛП, необходимо:
a) Ввести обозначения переменных;
b) исходя из цели экономических исследований, составить целевую функцию;
c) учитывая ограничения в использовании экономических показателей задачи и их количественные закономерности, записать систему ограничений.
Пример решения задачи.
|
|
Большой универсальный магазин собирается заказать новую коллекцию костюмов. Решено заказать 4 модели костюмов. Три модели – это костюмы широкого потребления: (1) костюмы из полиэстера, (2) шерстяные костюмы и (3) костюмы из хлопка. Четвертый тип – это дорогие импортные модельные костюмы. Имеющийся у менеджеров магазина опыт и специальные исследования позволяют оценить средние затраты рабочего времени продавцов на продажу одного костюма каждого типа, затраты на рекламу и площадь в расчете на один костюм каждого типа.
Тип костюма | Прибыль на один костюм | Рабочее время продавцов | Затраты на рекламу | Площадь на один костюм (кв. фут) |
Полиэстер | $35 | 0.4 | $2 | 1.00 |
Шерсть | $47 | 0.5 | $4 | 1.50 |
Хлопок | $30 | 0.3 | $3 | 1.25 |
Импорт | $90 | 1.0 | $9 | 3.00 |
Магазин предполагает, что сезон будет длиться 90 дней. Магазин открыт 10 часов в день 7 дней в неделю. Предполагается, что 2 продавца постоянно будут в отделе костюмов. Выделенная отделу площадь составляет прямоугольник 100 60 футов. Бюджет, выделенный на рекламу составляет $15000.
a. Сколько костюмов каждого типа нужно закупить для максимизации прибыли?
b . Обоснуйте, будет ли каждое из предлагаемых решений полезно для магазина:
|
|
i. Отдать в распоряжение отдела костюмов 400 кв.футов от отдела женской спортивной одежды, предполагается, что на этой площади магазин может получить прибыль $750 за последующие 90 дней;
ii. Истратить дополнительно $400 на рекламу;
iii. Нанять дополнительно продавца на 26 полных дней (все субботы и воскресенья). Это будет стоить магазину $3600 (зарплата, комиссионные).
Решение. В данной задаче переменными будет количество костюмов каждого типа, которые нужно закупить. Никакие данные в этот столбец вводить не нужно, их мы получим в результате поиска решения!
Также необходимо добавить все данные для ограничений. Для удобства расположим их прямо под таблицей.
В ячейке E10 будет ограничение времени. Из условий делаем вывод о том, что работает магазин ежедневно, каждый день 10 часов, поэтому 10 часов умножаем на 90 дней, получаем 900 часов. Но учитываем, что в отделе всегда будет работать 2 продавца, поэтому удваиваем время 900*2=1800 часов. Любая формула начинается со знака «=».
Следующее ограничение по площади. Опять совершаем расчёт: площадь = 100*60 = 6000 футов.
Ограничение по рекламе никаких дополнительных вычислений не требует, поэтому вручную вводим в ячейку F10 число 15000.
Под заданными ограничениями рассчитаем значения реальных расходов, которые получатся у нас при закупке разного количества костюмов. Для расчёта расхода рабочего времени необходимо попарно умножить переменные (ячейки I4:I7) на ячейки расхода времени по продаже 1 костюма (ячейки E4:E7) и сложить эти произведения. Сделаем это с помощью формулы СУММПРОИЗВ. Для этого нажимаем (на рисунке обведена кружочком), появляется окно «Вставка функции». Выбираем категорию «Математические» и среди них ищем СУММПРОИЗВ.
|
|
В массив 1 помещаем переменные. Массив 2 – расход времени, нажимаем ОК. Компьютер сразу введёт в ячейку готовый результат. Но сейчас этот результат будет 0. Так и должно быть, ведь столбец «переменные» ещё не заполнен. Аналогично вводятся ограничения по рекламе и по площади.
В данной задаче целевая функция будет показывать прибыль, которую получит предприятие. Т.е. нужно умножить переменные на прибыль. Для этого воспользуемся функцией СУММПРОИЗВ. Получаем:
Переходим непосредственно к поиску решения. Он находится на вкладке «Данные» - «Анализ». Нажимаем на «Поиск решения», появляется окно «Параметры поиска решения», с которыми нам предстоит работать.
В первой строке «Оптимизировать целевую функцию» выбираем цель, в нашем случае это ячейка D13. Вторая строка «До», то есть то, к чему стремится функция, выбираем к максимуму.
|
|
Изменяя ячейки переменных . В этой строке выбираем все переменные. После этих действий добавляем ограничения с помощью кнопки «Добавить».
Во-первых, все переменные должны быть не отрицательны. Время, которое мы используем, должно быть не больше, чем имеющийся у нас фонд времени, т.е. ячейка Е11 должна быль меньше или равна ячейки Е10. Вновь нажимаем «Добавить». Аналогично предыдущему добавляем ограничения по рекламе и площади и нажимаем ОК.
В методе решения выбираем РЕШЕНИЕ ЛИНЕЙНЫХ ЗАДАЧ СИМПЛЕКСНЫМ МЕТОДОМ. Нажимаем «Найти решение».
Решение найдено. Все ограничения и условия оптимальности выполнены. Нажимаем ОК и смотрим, что же нам предлагает компьютер.
Нам предлагается купить 500 костюмов из полиэстера, 2000 костюмов из шерсти, 2000 костюмов из хлопка и совсем не покупать импортные костюмы, и в таком случае мы должны будем получить прибыль в размере 171500 $.
Дата добавления: 2019-01-14; просмотров: 285; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!