значений переменных нужно выбрать те, которые будут соответствовать
наилучшему, то есть оптимальному, решению?
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 м.
При изготовлении полок А выполняются следующие работы: столярные,