Решение задачи линейного программирования - задачи о ресурсах

ВВЕДЕНИЕ 

       Организация современного производства требует  не только наличия современных станков и оборудования, но и разработки новых технологических процессов и современных методов управления производством. Для решения каждой из поставленных задач разрабатываются математические модели, анализируя которые, удается найти наилучшее решение поставленной задачи. Создание математической модели – сложная и кропотливая работа.

       Цель  курсовой работы научиться от словесного описания задачи переходить к абстрактной математической модели, реализовывать математическую модель с помощью специальных прикладных программ, проводить математическое исследование математической модели и получать вектор входных воздействий, доставляющих оптимальное решение. Конечно же, речь идет о простых математических моделях, позволяющих решать элементарные задачи: задача о ресурсах, задача о смесях (о диете).

       В данной курсовой работе рассматривается решение задачи – задачи о ресурсах. Задача состоит в формировании производственной программы выпуска продукции, обеспечивающей максимальную прибыль от ее реализации. Будет дана содержательная постановка задачи, по условию которой будет построена математическая модель, где будет определен критерий задачи и ограничения.

       Для решения поставленной задачи будут использоваться симплекс-метод и графический метод. Симплекс-метод не обладает той наглядностью, которая характерна для графического метода. Графический метод позволяет выявить свойства решений задачи, которые станут основой для рассмотрения общего метода решений задач линейного программирования.

       Поиск оптимального решения задач линейного  программирования осуществляется итерационными, то есть однотипными, последовательно повторяющимися, процедурами. В ходе курсовой работы будет дан анализ полученных результатов.

 

1 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ 

       1.1.Основные понятия линейного программирования 

       Для задач математического программирования характерна особая структура, включающая в себя:

1. множество допустимых решений,
2. наличие цели (критерии оптимальности),
3. наличие условий (ограничений).

       Задачи  линейного программирования является подмножеством задач общего программирования, которые чаще называют математическим программированием.

       В математическое программирование в  составные части входят:

       1) линейное;

       2) нелинейное;

       3) динамическое;

       4) параметрическое;

       5) стохастическое;

       6) квадратическое;

       7) целочисленное.

       Отличительной особенностью задач линейного программирования является то, что цель задачи записывается с помощью линейной функции и линейных ограничений. Вычисление экстремума (min или max) линейной функции при условии, что переменные, подлежащие определению, удовлетворяют линейным ограничениям, составляет предмет линейного программирования.

       Исходя  из частных видов задачи линейного  программирования, общую задачу линейного программирования можно записать в виде: 

            (1)

       

               (2)

       

                 (3) 

       Линейная  функция f называется целевой функцией задачи. Все остальное, за исключением условий не отрицательности переменных (3) называются ограничениями.

       Любая совокупность (3), удовлетворяющая ограничением, называется допустимым решением (допустимым планом) задачи. Если задача линейного программирования имеет хотя бы одно допустимое решение, то ее ограничения называются совместными, в противном случае несовместными.

       Все допустимые решения задачи линейного  программирования или область допустимых решений максимизирующие или минимизирующие функцию f, называется оптимальным решением задачи. Если через

- обозначим оптимальное решение задачи линейного программирования, а через

любое допустимое решение, то справедливы  соотношения:

       

для задачи на максимум;

       

для задачи на минимум.

 

       1.2.Общая постановка задачи линейного программирования 

       Процесс построения оптимизационных экономико-математических моделей условно можно разделить на следующие основные этапы.

       Первый  этап - выбор объекта исследования. Объектом исследования могут быть различные производственно - экономические процессы: перевозка грузов, размещение производства, загрузка производственных мощностей, раскрой промышленных материалов и т.д.

       Второй  этап - определение цели исследования. Цель исследования формулируется на основе задач, поставленных при изучении данного объекта.

       Третий  этап - выбор критерия оптимальности. К выбору критерия следует подходить очень осторожно, так как неправильно выбранный критерий может привести к решению, не отвечающему цели поставленной задачи.

       Четвертый этап - выявление основных ограничений. При построении модели необходимо выявить основные ограничения задачи и включить их в модель. Реальные задачи обычно содержат большое количество ограничений. Часть из них вытекает из условия задачи, другие можно выявить лишь после решения, которое по каким-либо причинам не устраивает.

       1.2.1 Задача об использовании ресурсов

       Задача  об использовании ресурсов относится  к задачам линейного программирования и может решаться на различных предприятиях, где выпускается различное количество видов продукции с использованием различного количества видов продукции с использованием различного количества видов ресурсов.

       Особенность данной задачи состоит в том, что  существует множество вариантов выпуска продукции, необходимо выбрать такой вариант выпуска продукции, который приносит максимальный доход. Этот вариант выпуска продукции будет оптимальным.

       Учитывая  это обстоятельство, сформулируем в общем виде данную задачу.

       Предположим, что предприятие выпускает n видов продукции с использованием m видов ограничений ресурсов. Известны следующие величины:

        - запас ресурса i-го вида;

        - количество ресурса i-го вида, идущее на изготовление единицы продукции j-го вида:

        - доход от реализации единицы  продукции j-го вида.

       Требуется составить такой план выпуска  продукции, чтобы при ее реализации получить максимальный доход.

       Обозначим через 

количество  продукции j-го вида. Тогда задачу об использовании ресурсов в общем виде можно описать с помощью такой модели: 

 

       1.3 Методы решения  задач линейного программирования 

       1.3.1 Алгоритм симплекс метода

1. Строим и заполняем исходную симплексную таблицу.

       В столбце «Базис» записываются базисные переменные, в столбце «C» - коэффициенты при базисных переменных в целевой функции , в столбце «B» -свободные члены ограничений , то есть значения базисных переменных. В столбцах (небазисные переменные) отражаются коэффициенты при небазисных переменных в ограничениях , над переменными - коэффициенты при этих переменных в целевой функции . Строка в столбце «B» содержит значение целевой функции, которое рассчитывается по формуле:

          (4)

а столбцы  этой же строки – значения относительных оценок , рассчитываемых по формуле:

     

          (5)

       Числа и , записываемые соответственно над столбцами «C» и «B», неизменно присутствуют в каждой симплексной таблице и носят вспомогательный характер, чтобы при расчете оценок по таблице не забывать о вычислении .

       При определении значения фактически нужно найти сумму произведений элементов столбца «B», что равносильно подстановке базисного плана в целевую функцию, а при определении значения относительной оценки - сумму произведений элементов того столбца «C», включая , на соответствующие элементы того столбца , для которого она рассчитывается.

2. Проверим полученный базисный план на оптимальность по условию оптимальности.

       Если и среди базисных переменных нет искусственных, то план является оптимальным.

       Если и среди базисных переменных есть искусственные, то задача неразрешима, так как ее система ограничений несовместна.

       Если  , то полученный базисный план не является оптимальным и необходимо переходить к другому базисному плану.

       Если  в оптимальном плане  , то это говорит о том, что задача имеет бесконечное число планов.

3. Для перехода к новому базисному плану в первую очередь из числа небазисных переменными с отрицательными оценками выбирается переменная, которая вводится в базис. Введем в новый базис переменную , которая соответствует наибольшая по абсолютной величине отрицательная оценка :

     

          (6)

       Столбец, отвечающий переменной , назовем главным. Элементы главного столбца обозначаются через . Выбранная переменная будет вводиться в базис.

       Если  окажется несколько одинаковых наибольших по абсолютной величине отрицательных оценок, то выбирается любая из соответствующих им переменных.

4. Выбираем переменную, которая выводиться из базиса. Ее индекс   находится из соотношения:

     

          (7)

по всем , для которых .

       Строку  таблицы, в которой получено наименьшее отношение элемента столбца «В» к соответствующему положительному элементу главного столбца, назовем главной. Элементы главной строки обозначаются через . Выбранная переменная будет выводиться из базиса.

       Если  окажется несколько одинаковых наименьших значений отношений, то выбирается любая  из соответствующих им переменных.

       Элемент, стоящий на пересечение главной строки и главного столбца, назовем главным.

       В случае отсутствия значений задача неразрешима, так как ее целевая функция не ограничена на множестве планов задачи.