1. СУЩНОСТЬ ЗАДАЧИ ОПТИМИЗАЦИИ
1.1 Немного истории
Большинство задач, которые приходится решать человеку, в процессе своей практической деятельности, являются многовариантными, то есть предполагают наличие нескольких вариантов решения. Всю свою жизнь человечество стремится отыскать наилучшее решение при имеющихся ограничениях возможностей и ресурсов. Долгое время при этом он руководствовался лишь здравым смыслом, опытом, интуицией.
На этапе индустриализации произошло резкое увеличение масштабов производства, появилась необходимость решать задачи управления, планирования, анализа альтернативных вариантов, выработки прогнозов на будущее и многие другие. Очевидно, что увеличился объем обрабатываемой информации, данных которые необходимо учитывать при решении задач такого рода. Также нужно учитывать взаимосвязь между, казалось бы, отдельными, не связанными между собой явлениями (загрязнение окружающей среды и промышленное производство; характер взаимоотношений в коллективе и производственные показатели, выполнение плана; химизация продуктов питания и уровень онкологических заболеваний у населения и др.).
Однако, с развитием компьютерной и вычислительной техники появилась возможность решать задачи, требующие большого объема арифметических вычислений. Стало возможным привлечение математического аппарата, к решению задач, решаемых ранее интуитивно и приблизительно. Стали создаваться принципиально новые способы решения задач.
Таким образом, в 30-е годы XX в., появилась новая математическая дисциплина – математическое программирование.
Математическое программирование – это раздел математики, занимающийся анализом многомерных экстремальных задач управления и планирования и разработкой теории и численных методов их решения [8].
Линейное программирование является наиболее изученным разделом математического программирования. Термин линейного программирования появился в работах Т. Купманса и Дж. Данцига в 1951 г[4].
1.2 Основные понятия
Математическое программирование – раздел математики, разрабатывающий теоретическое обоснование и способы решения многомерных экстремальных задач с ограничениями, т. е. задач на экстремум функции нескольких переменных с ограничениями на область допустимых значений неизвестных переменных.
Имеющиеся ресурсы представляются в виде системы ограничений. Функцию, экстремальное значение которой нужно найти называют целевой, показателем эффективности или критерием оптимальности. Именно эти две составляющие являются необходимыми компонентами математической модели задачи.
В большинстве случаев модель в некотором роде заменяет сам исследуемый объект, то есть оригинал. При решении задач вместо исходного объекта (оригинала, словесного описания) используется его модель, в частности математическая. Модель являлась представлением объекта в некоторой форме, отличной от формы его реального существования.
Математическая модель задачи – это отображение исследуемого объекта в виде систем неравенств и уравнений, функций и т. д.
Модель задачи математического программирования включает в себя:
? совокупность неизвестных переменных, оказывая влияние на которые, систему можно оптимизировать. Это так называемый вектор управления, план задачи или, проще говоря, вектор решения;
? функцию цели, в некоторых источниках она может иметь название целевой функции, показателя эффективности или же критерия оптимальности. С помощью данного показателя эффективности представляется возможным нахождения оптимального варианта решения задачи из нескольких возможных решений. Наилучший план решения задачи доставляет функции цели минимальное, либо максимальное значение. Это могут быть затраты на грузоперевозки, количество единиц материала, доход от продажи товаров, количество выпущенной продукции и многое другое.
Любые имеющиеся ресурсы, так или иначе ограничены, к тому же в процессе производства, потребность в этих ресурсах сохраняется. Именно из этого условия следуют вышеперечисленные компоненты задачи математического программирования.
Ресурсы могут быть не только материальными или финансовыми, но и трудовыми, техническими либо, же в качестве ресурса может выступать научный и технологический потенциал.
Математически ограничения в ресурсах выражаются с
