Департамент кинематографии Министерства культуры РФ
Федеральное Государственное образовательное учреждение высшего профессионального образования Санкт-Петербургский Государственный Университет Кино и Телевидения.
Институт экономики и управления
Кафедра управления экономическими и социальными процессами
КУРСОВАЯ РАБОТА
по дисциплине
«Экономико-математические методы и модели»
на тему:
Одноиндексные задачи линейного программирования
Выполнила:
студентка ФПК 17 гр.
Карышева А.А.
Проверил:
к.э.н. доцент Булочников П.А.
Санкт-Петербург
2009
Содержание
Стр.
Введение………………………………………………………………….…..…….3
Теоретическая часть……………………….. ………………….………………….4
Практическая часть………………………………………….………………..…..14
Вывод…….………………………………………………………………….….….22
Список литературы……….………………………………………………...….….23
Введение
Современная экономика как наука о рациональном ведении хозяйства должна давать ответы на следующие основные вопросы: что производить? где производить? какова цена продукции? как соизмерить настоящие и будущие издержки?
Высокоразвитое хозяйство требует точных экономических рекомендаций, и наиболее эффективным инструментом для их разработки являются экономико-математические модели, описывающие процессы производства и реализации продукции и услуг на разных уровнях.
Существует множество моделей и методов, которые целесообразно использовать на уровне отдельных предприятий и фирм при оптимальном распределении ресурсов, управлении складскими запасами, оценке рентабельности товара, при организации эффективного статистического контроля за качеством продукции.
Особое внимание в своей работе я уделяю линейному программированию. Оно применимо для построения математических моделей тех процессов, в основу которых может быть положена гипотеза линейного представления реального мира: экономических задач, задач управления и планирования, оптимального размещения оборудования и пр.
Задачами линейного программирования называются задачи, в которых линейны как целевая функция, так и ограничения в виде равенств и неравенств. Кратко задачу линейного программирования можно сформулировать следующим образом: найти вектор значений переменных, доставляющих экстремум линейной целевой функции при нескольких ограничениях в виде линейных равенств или неравенств.
Цель данной курсовой работы: приобретение навыков построения математических моделей одноиндексных задач и решение их симплексным методом.
Теоретическая часть
Если в какой-либо системе (экономической, организационной, военной и
т.д.) имеющихся в наличии ресурсов не хватает для эффективного выполнения
каждой из намеченных работ, то возникают так называемые
распределительные задачи
. Цель решения распределительной задачи –
отыскание оптимального распределения ресурсов по работам. Под
оптимальностью распределения может пониматься, например, минимизация
общих затрат, связанных с выполнением работ, или максимизация получаемого в результате общего дохода.
Для решения таких задач используются методы математического
программирования. Математическое программирование
– это раздел
математики, занимающийся разработкой методов отыскания экстремальных
значений функции, на аргументы которой наложены ограничения. Слово
"программирование" заимствовано из зарубежной литературы, где оно
используется в смысле "планирование".
В зависимости от своей постановки, любая из задач оптимизации может решаться различными методами, и наоборот – любой метод может применяться для решения многих задач. Методы оптимизации могут быть скалярными (оптимизация проводится по одному критерию), векторными (оптимизация проводится по многим критериям), поисковыми (включают методы регулярного и методы случайного поиска), аналитическими (методы дифференциального исчисления, методы вариационного исчисления и др.), вычислительными (основаны на математическом программировании, которое может быть линейным, нелинейным, дискретным, динамическим, стохастическим, эвристическим и т.д.), теоретико-вероятностными, теоретико-игровыми и др. Подвергаться оптимизации могут задачи как с ограничениями, так и без них.
Наиболее простыми и лучше всего изученными среди задач математического программирования являются задачи линейного программирования.
Характерные черты задач ЛП следующие:
1) показатель эффективности L представляет собой линейную функцию,
заданную на элементах решения x1 , x2, xn;
2) ограничительные условия, налагаемые на возможные решения, имеют
вид линейных равенств или неравенств.
В общей форме записи модель задачи ЛП имеет вид:
целевая функция (ЦФ)
L=c1x1+c2x2+...+cnxn→max(min) ;
при ограничениях
а11х1+а12х2+…+а1nxn≤(≥,=)b1,
а21х1+а22х2+…+а2nxn≤(≥,=)b2,
……………………………
аm1х1+аm2х2+…+аmnxn≤(≥,=)bm,
x1, x2,…, xк ≥ (к ≤ n).
Любая задача линейного программирования приводится к стандартной (канонической) форме основной задачи линейного программирования.При этом также требуется, чтобы правые части равенств были неотрицательны.
Приведение к стандартной форме необходимо, таккакбольшинство методов решения задач линейного программирования разработано именно для
стандартной формы. Для приведения к стандартной форме задачи линейного программирования может потребоваться выполнить следующие действия:
- перейти от минимизации целевой функции к ее максимизации;
- изменить знаки правых частей ограничений;
- перейти от ограничений-неравенств к равенствам;
- избавиться от переменных, не имеющих ограничений на знак.
Допустимое решение
– это совокупность чисел X = (x1, x2,…, xn),
удовлетворяющих ограничениям задачи.
Оптимальное решение
– это план X* = (x*1, x*2,…, x*n), при котором ЦФ принимает свое максимальное (минимальное) значение.
В настоящее время оптимизация находит применение в науке, технике и в любой другой области человеческой деятельности.
Оптимизация
- целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.
Поиски оптимальных решений привели к созданию специальных математических методов и уже в 18 веке были заложены математические основы оптимизации (вариационное исчисление, численные методы и др). Однако до второй половины 20 века методы оптимизации во многих областях науки и техники применялись очень редко, поскольку практическое использование математических методов оптимизации требовало огромной вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев - невозможно.
Постановка задачи оптимизации предполагает существование конкурирующих свойств процесса, например:
· количество продукции - расход сырья
· количество продукции - качество продукции
Выбор компромиcного варианта для указанных свойств и представляет собой процедуру решения оптимизационной задачи.
При постановке задачи оптимизации необходимо:
1
. Наличие объекта оптимизации и цели оптимизации. При этом формулировка каждой задачи оптимизации должна требовать экстремального значения лишь одной величины, т.е. одновременно системе не должно приписываться два и более критериев оптимизации, т.к. практически всегда экстремум одного критерия не соответствует экстремуму другого. Приведем примеры.
Типичный пример неправильной постановки задачи оптимизации:
«Получить максимальную производительность при минимальной себестоимости».
Ошибка заключается в том, что ставится задача поиска оптимальности 2-х величин, противоречащих друг другу по своей сути.
Правильная постановка задачи могла быть следующая:
а)
получить максимальную производительность при заданной себестоимости;
б)
получить минимальную себестоимость при заданной производительности;
В первом случае критерий оптимизации - производительность
а во втором - себестоимость.
2
. Наличие ресурсов оптимизации, под которыми понимают возможность выбора значений некоторых параметров оптимизируемого объекта.
3
. Возможность количественной оценки оптимизируемой величины, поскольку только в этом случае можно сравнивать эффекты от выбора тех или иных управляющих воздействий.
4.
Учет ограничений.
Обычно оптимизируемая величина связана с экономичностью работы рассматриваемого объекта (аппарат, цех, завод). Оптимизируемый вариант работы объекта должен оцениваться какой-то количественной мерой - критерием оптимальности.
Критерием оптимальности
называется количественная оценка оптимизируемого качества объекта.
На основании выбранного критерия оптимальности составляется целевая функция, представляющая собой зависимость критерия оптимальности от параметров, влияющих на ее значение. Вид критерия оптимальности или целевой функции определяется конкретной задачей оптимизации.
Таким образом, задача оптимизации сводится к нахождению экстремума целевой функции.
Для построения математической модели необходимо ответить на
следующие три вопроса.
1. Что является искомыми величинами, то есть переменными этой
задачи?
2. В чем состоит цель, для достижения которой из всех допустимых
значений переменных нужно выбрать те, которые будут соответствовать
наилучшему, то есть оптимальному, решению?
3. Какие ограничения должны быть наложены на переменные, чтобы
выполнялись условия, описанные в задаче?
Линейное программирование
- один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программ) для ЭВМ» не имеет, так как дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических,
инженерных, экономических и др. задач. Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова «programming» - составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и т.д. в нашей литературе стали общепринятыми. Итак, линейное программирование возникло после Второй Мировой Войны и стал быстро развиваться, привлекая внимание математиков, экономистов и инженеров благодаря возможности широкого практического применения, а так же математической «стройности». Можно сказать, что линейное программирование применимо для построения математических моделей тех процессов, в основу которых может быть положена гипотеза линейного представления реального мира: экономических задач, задач управления и планирования, оптимального размещения оборудования и пр.
Задачами линейного программирования называются задачи, в которых линейны как целевая функция, так и ограничения в виде равенств и неравенств. Кратко задачу линейного программирования можно сформулировать следующим образом: найти вектор значений переменных, доставляющих экстремум линейной целевой функции при m ограничениях в виде линейных равенств или неравенств.
Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:
· рационального использования сырья и материалов; задачи оптимизации раскроя;
· оптимизации производственной программы предприятий;
· оптимального размещения и концентрации производства;
· составления оптимального плана перевозок, работы транспорта;
· управления производственными запасами;
· и многие другие, принадлежащие сфере оптимального планирования.
Так, по оценкам американских экспертов, около 75% от общего числа применяемых оптимизационных методов приходится на линейное программирование. Около четверти машинного времени, затраченного в последние годы на проведение научных исследований, было отведено решению задач линейного программирования и их многочисленных модификаций.
Первые постановки задач линейного программирования были сформулированы известным советским математиком Л.В.Канторовичем, которому за эти работы была присуждена Нобелевская премия по экономике.
Значительное развитие теория и алгоритмический аппарат линейного программирования получили с изобретением и распространением ЭВМ и формулировкой американским математиком Дж. Данцингом симплекс-метода.
В настоящее время линейное программирование является одним из наиболее употребительных аппаратов математической теории оптимального принятия решения. Для решения задач линейного программирования разработано сложное программное обеспечение, дающее возможность эффективно и надежно решать практические задачи больших объемов. Эти программы и системы снабжены развитыми системами подготовки исходных данных, средствами их анализа и представления полученных результатов.
В развитие и совершенствование этих систем вложен труд и талант многих матеметиков, аккумулирован опыт решения тысяч задач. Владение аппаратом линейного программирования необходимо каждому специалисту в области математического программирования. Линейное программирование тесно связано с другими методами математического программирования (например, нелинейного программирования, где целевая функция нелинейна).
Задачи с нелинейной целевой функцией и линейными ограничениями называют задачами нелинейного программирования с линейными ограничениями. Оптимизационные задачи такого рода можно классифицировать на основе структурных особенностей нелинейных целевых функций. Если целевая функция L - квадратичная функция, то мы имеем дело с задачей квадратичного программирования; если L – это отношение линейных функций, то соответствующая задача носит название задачи дробно-линейного программирования, и т.д. Деление оптимизационных задач на эти классы представляет значительный интерес, поскольку специфические особенности тех или иных задач играют важную роль при разработке методов их решения.
Современные методы линейного программирования достаточно надежно решают задачи общего вида с несколькими тысячами ограничений и десятками тысяч переменных. Для решения сверхбольших задач используются уже, как правило, специализированные методы.
В данной лабораторной работе рассматривается одноиндексная задача
ЛП, представляющая собой общую распределительную задачу
, которая
характеризуется различными единицами измерения работ и ресурсов.
Экстремум целевой функции всегда достигается в угловых точках области допустимых решений. Симплекс-метод
, называемый также методом последовательного улучшения плана, реализует перебор угловых точек области допустимых решений в направлении улучшения значения целевой функции. Основная идея этого метода следующая. Прежде всего, находится какое-либо допустимое начальное (опорное) решение, т.е. какая-либо угловая точка области допустимых решений. Процедура метода позволяет ответить на вопрос, является ли это решение оптимальным. Если "да", то задача решена. Если "нет", то выполняется переход к смежной угловой точке области допустимых решений, где значение целевой функции улучшается, т.е. к нехудшему допустимому решению. Если некоторая угловая точка имеет несколько смежных, то вычислительная процедура метода обеспечивает переход к той из них, для которой улучшение целевой функции будет
наибольшим. Процесс перебора угловых точек области допустимых решений повторяется, пока не будет найдена точка, которой соответствует экстремум целевой функции Е.
При построении начального базиса в заданной задаче использовался метод искусственного базиса, поэтому найденное решение не является допустимым. В этом случае для решения задачи необходимо использовать двухэтапный симплекс-метод.
Задача с помощью этого метода решается в два этапа: сначала отыскивается начальное допустимое решение, не содержащее искусственных переменных, а затем на основе найденного решения ищется оптимальное решение исходной задачи. Основные шаги, реализации метода следующие.
1. Задача линейного программирования сводится к стандартной форме.
2. Строится искусственный базис.
3. Составляется искусственная целевая функция: сумма всех искусственных переменных.
4. Реализуется первый этап двухэтапного метода: с помощью обычных процедур симплекс-метода выполняется минимизация искусственной целевой функции. Если ее минимальное значение равно 0, то соответствующее решение является допустимым решением исходной задачи. Очевидно, что при нулевом значении искусственной целевой функции все искусственные переменные также нулевые (так как искусственная целевая функция - их сумма, и все они неотрицательны). Если минимальное значение искусственной целевой функции оказывается отличным от нуля, это означает, что задача не имеет допустимых решений.
5. Реализуется второй этап двухэтапного метода: найденное на шаге 4 допустимое решение используется в качестве начального решения исходной задачи для поиска ее оптимального решения.
Для того чтобы решить задачу ЛП в табличном редакторе Microsoft Excel, необходимо выполнить следующие действия:
1. Ввести условие задачи:
a) создать экранную форму для ввода условия задачи
:
• переменных,
• целевой функции (ЦФ),
• ограничений,
• граничных условий;
b) ввести исходные данные в экранную форму
:
• коэффициенты ЦФ,
• коэффициенты при переменных в ограничениях,
• правые части ограничений;
c) ввести зависимости из математической модели в экранную форму
:
• формулу для расчета ЦФ,
• формулы для расчета значений левых частей ограничений;
d) задать ЦФ
(в окне "Поиск решения"
):
• целевую ячейку,
• направление оптимизации ЦФ;
e) ввести ограничения и граничные условия
(в окне "Поиск решения"
):
• ячейки со значениями переменных,
• граничные условия для допустимых значений переменных,
• соотношения между правыми и левыми частями ограничений.
2. Решить задачу:
a) установить параметры решения задачи
(в окне "Поиск
);
b) запустить задачу на решение
(в окне "Поиск решения"
)
;
c) выбрать формат вывода решения
(в окне "Результаты поиска решения"
).
Практическая часть
Мебельный комбинат выпускает книжные полки А из натурального
Дерева со с теклом, полки B 1 из полированной ДСП (древесно-стружечной
плиты) без стекла и полки B2 из полированной ДСП со с теклом. Габариты
полок А, B1 и В2 следующие: длина 1260 (d) мм, ширина 270 (w) мм, высота 320 (h) мм. Размер листа ДСП 2*3 м.
При изготовлении полок А выполняются следующие работы: столярные,
покрытие лаком, сушка, резка стекла, упаковка. Все операции, производимые в
ходе столярных работ и упаковки, выполняются вручную. Полки B1 и В2
поставляются в торговую сеть в разобранном виде. За исключением операции
упаковки, все остальные операции (производство комплектующих полки, резка
стекла) при изготовлении полок B1 и В2, выполняются на специализированных
автоматах.
Трудоемкость столярных работ по выпуску одной полки А составляет 2,4
(Тр1
) ч. Производительность автомата, покрывающего полки А лаком – 4
(Пр1
) полок в час, автомата, режущего стекло – 200 (Пp2
) стекол в час.
Сменный фонд времени автомата для покрытия лаком – 7,1 (ФВ1
) ч, автомата для резки стекла – 7,5 (ФВ2
) ч. Сушка полок, покрытых лаком, происходит в
течение суток в специальных сушилках, вмещающих 35 (V1
) полок. На
упаковку полки А требуется 8 (Тр2
) минуты. В производстве полок заняты 11
(Р1
) столяров и 6 (Р2
) упаковщиков.
Производительность автомата, производящего комплектующие полок B1
и В2, равна 11 (Пр3
) полки в час, а его сменный фонд времени равен 7,7 (ФВ3
) ч, трудоемкость упаковочных работ составляет 11 (Тр3
) мин для полки В1 и 14 (Тр4
) мин для полки В2.
От поставщиков комбинат получает в месяц 395 (Z1
) листов полированной ДСП, 205 (Z2
) листов ДВП (древесно-волокнистой плиты), а
также 220 (Z3
) листов стекла. Из каждого листа ДВП можно выкроить 8 (К1
)
задних стенок полок B1 и В2, а из каждого листа стекла – 15 (К2
) стекол для
полок А и В2.
Склад готовой продукции может разместить не более 390 (V2
) полок и комплектов полок, причем ежедневно в торговую сеть вывозится в среднем 38 (N
) полок и комплектов. На начало текущего месяца на складе осталось 60 (Ост
) полок, произведенных ранее. Себестоимость полки А равна 165 (C1
) руб., полки В без стекла – 129 (C2
) руб., со стеклом – 142 (С3
) руб.
Маркетинговые исследования показали, что доля продаж полок обоих
видов со стеклом составляет не менее 23% (Д
) в общем объеме продаж, а
емкость рынка полок производимого типа составляет около 1400 (V3
) штук в
месяц. Мебельный комбинат заключил договор на поставку заказчику 80 (З
)
полок типа В1 в текущем месяце.
Требуется составить план производства полок на текущий месяц. Известны цены реализации полок: полка А – 203 (Ц1
) руб., полка В без стекла – 194 (Ц2
) руб., полка В со стеклом – 167 (Ц3
) руб.
Построение модели
I этап построения модели
заключается в определении (описании,
задании, идентификации) переменных. В данной задаче искомыми
неизвестными величинами является количество полок каждого вида, которые
будут произведены в текущем месяце. Таким образом, xА – количество полок А (шт./мес.); xB1 – количество полок В1 (шт./мес.); xB2 – количество полок В2
(шт./мес.).
II этап построения модели
заключается в построении целевой функции,
Представляющей цель решения задачи. В данном случае цель – это
максимизация прибыли, получаемой от продажи полок всех видов в течение
месяца. Поскольку в этой задаче прибыль может быть определена как разность
между ценой (Ц1, Ц2, Ц3) и себестоимостью (С1, С2, С3), то ЦФ имеет вид
L (X ) = (203 - 165 )x
A
+ (194 - 129 )x
B1
+ (167 - 142) x
B2
→max
III этап построения модели
заключается в задании ограничений,
моделирующих условия задачи. Все ограничения рассматриваемой задачи
можно разделить на несколько типов.
Ограничения по фонду времени (с использованием трудоемкости работ)
Левая часть ограничений по фонду времени представляет собой время,
затрачиваемое на производство полок в течение месяца в количестве xА, xB1,
xB2 штук. Правая часть ограничения – это фонд рабочего времени исполнителя
работы (рабочего или автомата) за смену. Неравенство (2.2) описывает
ограничение по фонду времени на выполнение столярных работ. Коэффициент
2,4 ч/шт. (Тр1) – это время, затрачиваемое на столярные работы
при
производстве одной полки типа А (трудоемкость); 11 чел. (Р1) – это количество
столяров, участвующих в производстве; 8 ч(чел.*см.) – количество часов
работы одного человека в течение смены; 1 см./дн. – количество смен в одном
рабочем дне; 22 дн./мес . – количество рабочих дней в месяце:
2,4xA ≤ 11 *8*1* 22
(2.2)
Примечание 2.2.
Важным моментом проверки правильности составления
ограничений является проверка совпадения единиц измерения левой и правой
частей ограничения. В ограничении (2.2) левая и правая части измеряются в
часах, потраченных на выпуск продукции в течение месяца.
Аналогично записывается ограничение (2.3) по фонду времени на
упаковочные работы
, в котором 6 чел. (Р2) – это количество упаковщиков:
8/60 xA + 11/60 xB1 + 14/60 xB2 ≤ 6 *8*1* 22
(2.3)
Ограничения по фонду времени (с использованием производительности работ)
Неравенство (2.4) описывает ограничение по фонду времени на покрытие
Лаком полок типа А. Отличие ограничений, учитывающих данные о
Производительности
работ, от ограничений, учитывающих данные о
трудоемкости
работ, состоит в том, что производительность необходимо
преобразовать в трудоемкость. Трудоемкость является величиной, обратной
производительности. Коэффициент 1/4 (1/ Пр1) при xA в (2.4) – это количество часов, приходящихся на покрытие лаком одной полки типа А. При записи
правой части ограничения учитываем, что автомат, выполняющий покрытие лаком, работает не полную смену (8 ч), а в течение сменного фонда времени 7,1 ч (ФВ1). Это связано с необходимостью подготовки автомата к работе и обслуживанием его после окончания работы.
1/4
xA
≤ 7,1 * 1* 22
(2.4)
Неравенство (2.5) описывает ограничение по фонду времени на резку
стекла для полок типа А и В2:
2/200
xA
+ 2/200
xB2 ≤ 7,5 * 1* 22
(2.5)
Неравенство (2.6) описывает ограничение по фонду времени на производство комплектующих полок типа В1 и В2:
1/11 xB1 + 1/11 xB2 ≤ 7,7* 1* 22
(2.6)
Ограничения по запасу расходуемых в производстве материалов
(по запасу используемых для производства полок деталей)
Неравенство (2.7) описывает ограничение по запасу листов ДСП, поставляемых на комбинат ежемесячно. При этом следует учесть, что из листа
ДСП надо выкраивать комплекты (верхнюю и нижнюю стороны полок, 2 боковые стороны) для производства полок. Поэтому при задании ограничения имеет смысл ориентироваться не на количество листов ДСП, а на количество комплектов для полок [правая часть (2.7)], которые можно получить из имеющегося запаса ДСП. Но поскольку листы ДСП можно раскраивать различными способами и получать при этом различное количество деталей и комплектов, то обозначим месячный запас комплектов в правой части (2.7) как
Yкомпл и рассмотрим способ его численного определения позже. В левой части ограничения (2.7) задается количество комплектов (по одному на полку),
необходимых на производство полок в течение месяца в объеме xB1 , xB2 :
1xB1 + 1xB2 ≤ Yкомпл
(2.7)
Аналогично ограничению по ДСП неравенство (2.8.) – это ограничение по запасу задних стенок из ДВП для полок В1 и В2, а неравенство (2.9) –ограничение по запасу стекол для полок А и В2. В отличие от ДСП листы ДВП
и листы стекла кроятся стандартным способом, и из каждого листа ДВП получается 8 (К1) задних стенок полок, а из каждого листа стекла получается
15 (К2) стекол. Ежемесячный запас листов ДВП и стекла составляет соответственно 205 (Z2) и 220 (Z3). При составлении левых частей ограничений (2.8) и (2.9) следует учесть, что на каждую полку В1 и В2 приходится по одной задней стенке, а на каждую полку А и В2 – по 2 стекла:
1x B1 + 1x B2 ≤ 205 * 8
(2.8)
2x А + 2x B2 ≤ 220 * 15
(2.9)
Ограничения по емкости вспомогательных помещений и рынка
Неравенство (2.10) является ограничением по количеству полок А, которые может вместить сушилка. В правой части (2.10) представлено количество полок, которые могут быть просушены в течение месяца (в день может быть просушено 35 (V1) полок):
xA ≤ 35 * 22
(2.10)
Неравенство (2.11) описывает ограничение по количеству полок всех видов, которые может вместить склад готовой продукции. При этом правая часть (2.11) учитывает, что общая емкость склада уменьшена на 60 (Ост) полок, которые остались невывезенными с прошлого месяца. Кроме того, в течение месяца каждый день будет освобождаться по 38 (N) мест для полок:
x A + x B1 + x B2 ≤ 390 – 60 + 38 * 22
(2.11)
Неравенство (2.12) описывает ограничение по примерной емкости рынка,
равной 1400 (V3) полкам всех видов:
x A + x B1 + x B2 ≤ 1400
(2.12)
Ограничения по гарантированному заказу
Неравенство (2.13) показывает, что необходимо произвести как минимум 80 (З) заказанных полок В1, а возможно, и большее количество, но уже для свободной продажи:
xB1 ≥ 80
(2.13)
Ограничения по соотношению объемов продаж различных товаров
Неравенство (2.14) показывает, что доля полок А и В2 в общем объеме
полок, производимых для свободной продажи, должна составлять не менее 23% (Д). К такому выводу приводят результаты маркетинговых исследований. Поскольку из всех полок В1 в свободную продажу поступит лишь (x B1 − 50), то это учитывается при составлении ограничения (2.14), которое после алгебраических преобразований принимает вид (2.15).
xA + xB2 ≥ 0,23 [xA + (xB1 − 80) + xB2 ]
(2.14)
0,77xA − 0,23xB1 + 0,77xB2 ≥ − 18,4
(2.15)
Определение количества комплектов для полок В1 и В2
Рассмотрим подробно вопрос определения максимально возможного количества комплектов для полок В1 и В2, которое можно произвести из ежемесячного запаса ДСП. В зависимости от размеров листов ДСП ( 2000*3000 мм) и габаритов полок (1260*270*320 мм) детали полок В1 и В2 можно выкроить различными способами. Рассмотрим три возможных варианта такого раскроя, представленные на рис. 2.3 (затемненные участки – это неиспользованная площадь ДСП).
11 верхних и нижних стенок, 12 верхних и нижних стенок, 13 верхних и нижних стенок,
22 боковые стенки 17 боковых стенок 12 боковых стенок
Рис. 2.3. Возможные варианты раскроя листов ДСП
Согласно 1-му варианту из одного листа ДСП для полок В1 и В2 можно выкроить 11 деталей верхней или нижней стенок, а также 22 детали боковых стенок. По 2-му варианту раскроя получаем 12 деталей верхней или нижней стенок и 17 деталей боковых стенок. По 3-му варианту раскроя получаем 13 деталей верхней или нижней стенок и 12 деталей боковых стенок. Обозначим количество листов ДСП, раскроенных в течение месяца: по 1-му варианту через y1 (лист./мес.); по 2-му варианту – y2 (лист./мес.); по 3-му варианту – y3 (лист./мес.). При производстве полок нам выгодно стремиться к такому раскрою листов ДСП, при котором из полученных деталей можно укомплектовать максимальное количество полок. Количество комплектов, получаемых из раскроенных деталей, мы ранее обозначили черезYкомпл . Таким образом, наша цель описывается целевой функцией:
L(Y) = Yкомпл →max
Количество всех раскроенных листов ДСП не должно превышать 395 (Z1), то есть ежемесячный запас их на складе:
y1 + y2 + y3 ≤ 395
При этом, поскольку в каждый комплект входит одна верхняя и одна нижняя стенки, количество нижних и верхних стенок, получаемых при раскрое всех листов ДСП [левая часть (2.16)], должно быть не меньше чем 2Yкомпл :
11y1 +12y2 +13y3 ≥ 2Yкомпл
(2.16)
Аналогичный смысл имеет ограничение (2.17), которое задает нижнюю границу количества боковых стенок полок:
22y1 + 17y2 +12y3 ≥ 2Yкомпл
(2.17)
После преобразования описанных неравенств получим модель задачи (2.18), позволяющую раскроить максимальное количество комплектов:
L(Y) = Yкомпл →max;
y1 + y2 + y3 ≤ 395
11y1 +12y2 +13y3 - 2Yкомпл ≥ 0
(2.18)
22y1 + 17y2 +12y3 - 2Yкомпл ≥ 0
y
1
, y
2
, y
3,
Yкомпл ≥ 0
Таким образом, при решении задачи (2.18) симплекс-методом в MS Excel переменная Yкомпл непосредственно
определяет значение ЦФ, а переменные y1, y2 и y3 влияют на изменение значения ЦФ косвенно,
через ограничения. Решив задачу (2.18), мы получим значение правой части ограничения (2.7) Y= 1989 компл, после чего сможем решить исходную задачу, модель которой имеет вид:
L (X ) = 38x
A
+ 65x
B1
+ 25x
B2
→max;
2,4xA ≤ 1936;
0,133 xA + 0,183 xB1 + 0,233 xB2 ≤ 1056;
0,25
xA
≤ 156,2;
0,01
xA
+ 0,01
xB2 ≤ 165;
0,09 xB1 + 0,09 xB2 ≤ 169,4;
xB1 + xB2 ≤ 1989
xB1 + xB2 ≤ 1640
; (2.19)
2xА + 2xB2 ≤ 3300;
xA ≤ 770
;
xA + xB1 + xB2 ≤ 1166;
xA + xB1 + xB2 ≤ 1400;
xB1 ≥ 80;
0,77xA − 0,23xB1 + 0,77xB2 + 18,4 ≥ 0;
xA , xB1, xB2 ≥ 0.
Решив задачу (2.19), получаю:
xA =336 шт./мес., xB1 = 418 шт./мес., xB2 = 254 шт./мес.,
(2.20)
L(X)= 46 288 руб./мес.,
то есть в текущем месяце необходимо произвести 336 полок А, 418 полок В2,
и 254 полки В1. После реализации всех произведенных полок комбинат получит прибыль в размере 46 288 рублей.
Вывод
В настоящее время линейное программирование является одним из наиболее употребительных аппаратов математической теории оптимального принятия решения. Для решения задач линейного программирования разработано сложное программное обеспечение, дающее возможность эффективно и надежно решать практические задачи больших объемов. Эти программы и системы снабжены развитыми системами подготовки исходных данных, средствами их анализа и представления полученных результатов.
В развитие и совершенствование этих систем вложен труд и талант многих матеметиков, аккумулирован опыт решения тысяч задач. Владение аппаратом линейного программирования необходимо каждому специалисту в области математического программирования. Линейное программирование тесно связано с другими методами математического программирования (например, нелинейного программирования, где целевая функция нелинейна).
Современные методы линейного программирования достаточно надежно решают задачи общего вида с несколькими тысячами ограничений и десятками тысяч переменных. Для решения сверхбольших задач используются уже, как правило, специализированные методы.
В данной лабораторной работе рассматривается одноиндексная задача
ЛП, представляющая собой общую распределительную задачу, которая
характеризуется различными единицами измерения работ и ресурсов.
Цель решения данной распределительной задачи – отыскание оптимального распределения ресурсов по работам. Под оптимальностью распределения понимается максимизация получаемого в результате общего дохода.
Выполняя курсовую работу, я закрепила теоретический материал по курсу экономико-математического моделирования, а также приобрела навыки построения математических моделей одноиндексных задач и решения их симплексным методом.
Список литературы
1. Алесинская Т.В., Сербин В.Д., Катаев А.В. Учебно-методическое
пособие по курсу "Экономико-математические методы и модели. Линейное программирование". Таганрог: Изд-во ТРТУ, 2001.
2. Брыкин Л.В., Камартина Н.М. Учебное пособие по курсу "Экономико-математические методы и модели. Линейное программирование" СПИКиТ, кафедра мат.мод., 1997.
3. Дегтярев Ю.И. Исследование операций. - М.: Высшая школа, 1986.
4. Курицкий Б. Решение оптимизационных задач средствами Excel. М.:
BHV, 1997.
5. Смородинский С.С., Батин Н.В. Методы и алгоритмы для решения оптимизационных задач линейного программирования. Ч.1. – Мн.: БГУИР, 1995.
6. Смородинский С.С., Батин Н.В. Методы и алгоритмы для решения оптимизационных задач линейного программирования. Ч.2. – Мн.: БГУИР, 1996.
7. Эддоус М., Стенсфилд Р. Методы принятия решений. М.: Аудит, ЮНИТИ, 1997.