Решение задач линейного программирования симплексным методом

Размещено на http://www.allbest.ru/

14

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

федеральное государственное автономное образовательное учреждение

высшего профессионального образования

«Национальный исследовательский ядерный университет «МИФИ»

Димитровградский инженерно-технологический институт - филиал НИЯУ МИФИ

КУРСОВАЯ РАБОТА

на тему: «Решение задач линейного программирования симплексным методом»

Выполнил студент 332 группы

Бородкин Александр Павлович

Содержание

Введение

1. Методы и модели линейного программирования

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

3. Алгебраический симплекс метод

4. Составление первого опорного плана

5. Проверка плана на оптимальность

6. Определение ведущих столбца и строки

7. Построение нового опорного плана

8. Применение симплексного метода в экономике

Заключение

Список используемой литературы

Введение

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

Математические знания и навыки нужны практически во всех профессиях, прежде всего, конечно, в тех, что связаны с естественными науками, техникой, и экономикой. Математика является языком естествознания, техники и экономики и поэтому профессии естествоиспытателя, техника и экономиста требуют серьёзного овладения многими профессиональными сведениями, основанными на математике.

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

Первая школа, где была выработана концепция математического образования, была создана чуть более 1200 лет назад (в 795 г.). Это произошло при Карле Великом. Он повелел открыть в городе Аахене школу и пригласил для её организации монаха из Британии по фамилии Алкуин. Алкуин выполнил поручение и написал первую в Средневековой Европе учебную книгу по математике, озаглавленную “Задачи для изощрения ума”

“Изощрение ума” - важная цель математического образования.

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

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

1. Методы и модели линейного программирования

В настоящее время множество задач планирования и управления в отраслях народного хозяйства, а также большой объем частных прикладных задач - решаются методами математического программирования. Наиболее развитыми в области решения оптимизационных задач являются методы линейного программирования. Эти методы позволяют описать с достаточной точностью широкий круг задач коммерческой деятельности, таких, как: планирование товарооборота; размещение розничной торговой сети города; планирование товароснабжения города, района; прикрепление торговых предприятий к поставщикам; организация рациональных перевозок товаров (транспортная задача); распределение работников торговли по должностям (задача о назначении); организация рациональных закупок продуктов питания (задача о диете); распределение ресурсов; планирование капиталовложений; оптимизация межотраслевых связей; замена торгового оборудования; определение оптимального ассортимента товаров в условиях ограниченной площади; установление рационального режима работы.

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

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

Если в задаче математического программирования имеется переменная времени, а критерий эффективности выражается через уравнения, описывающие течение операций во времени, то такая задача является задачей динамического программирования.

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

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

В целом экономико-математическая формулировка и модель общей задачи линейного программирования (ОЗЛП) имеют следующий вид:

найти максимальное (минимальное) значение линейной целевой функции

F() = Cj . Xj>max(min) (1)

при условиях - ограничениях:

где аij, bi, cj - заданные постоянные величины.

Стандартной задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения целевой функции (1) при выполнении условий (2) - нетривиальных и (4) - тривиальных.

Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимaльнoгo значения целевой функции (1) при выполнении условий (3) и (4).

Для перехода от стандартной формы записи задачи линейного программирования к канонической необходимо ограничение - неравенство исходной задачи линейного программирования, имеющее вид «», преобразовать в ограничение - равенство с добавлением к левой части дополнительной неотрицательной пepeменной. Ограничение - неравенство вида «» преобразуется в ограничение - равенство вычитанием из левой части дополнительной неотрицательной переменной.

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

В базисном решении все (п-т) свободные переменные равны нулю.

Допустимое базисное решение (опорный план) содержит только неотрицательные переменные, среди которых свободные равны нулю.

Допустимое базисное решение является невырожденным, если все базисные переменные строго положительны, и вырожденным - в противном случае.

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

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

План , при котором целевая функция задачи принимает экстремальное значение, называется оптимальным.

В случае, когда требуется найти минимум функции , можно перейти к нахождению максимума функции , так как min F(Х) = -F1(Х), тогда полученное решение целевой функции следует записать с обратным знаком.

3. Алгебраический симплекс метод

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

Впервые симплексный метод был предложен американским ученым Дж. Данцингом в 1949 г. идеи метода были разработаны российским математиком Л.В. Канторовичем.

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

Допустимое множество базисных решений системы линейных уравнений образует в объеме многогранное тело, например тетраэдр, вершины которого - угловые точки.

Каждой угловой точке многогранника решений соответствует опорный план (допустимое базисное решение).

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

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

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

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

Коммерческое предприятие реализует n товарных групп, располагая m ограниченными материально-денежными ресурсами . Известны расходы ресурсов каждого i-вида на реализацию единицы товара по каждой группе, представленной в виде матрицы A=(aij), и прибыль cj, получаемая предприятием от реализации единицы товара j-группы. Необходимо определить объем и структуру товарооборота , при которых прибыль коммерческого предприятия была бы максимальной. Математическую модель задачи запишем следующим образом. Определить вектор , который удовлетворяет ограничениям вида

и обеспечивает максимальное значение целевой функции

Алгоритм симплексного метода заключает следующие этапы:

4. Составление первого опорного плана

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

Опорным решением называется базисное неотрицательное решение.

Опорный план, который заносим в симплексную таблицу состоит из коэффициентов системы ограничений и свободных членов. Последняя строка таблицы называется индексной и заполняется коэффициентом функции цели, взятыми с противоположным знакам.

5. Проверка плана на оптимальность

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

6. Определение ведущих столбца и строки

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

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

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

7. Построение нового опорного плана

Переход к новому плану осуществляется в результате пересчета симплексной таблицы методом Жордона-Гаусса. Сначала заменим переменные в базисе, то есть вместо в базис войдет переменная , соответствующая ведущему столбцу (замена).

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

НЭ= СТЭ-АВ/РЭ

Где СТЭ - элемент старого плана;

РЭ - разрешающий элемент;

А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Далее возвращаемся ко второму этапу алгоритма - проверке плана на оптимальность.

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

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

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

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

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

8. Применение симплексного метода в экономике

симплекс линейный программирование алгебраический

Рассмотрим применение симплексного метода на конкретном примере.

Компания выпускает изделия двух типов А и В. При этом она использует сырьё четырех видов. Расход сырья каждого вида на изготовление единицы продукции и запасы сырья заданы в таблице:

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

Решение.

Построение математической модели:

Цель: max дохода;

Параметры: все числовые данные в таблице;

Управляющие переменные: х1, х2 - изделия вида 1,2,3.4.

Ограничения:

Целевая функция:

Zmax=300x1+200x2

Для построения первого опорного плана приводим задачу к каноническому виду (систему неравенств приводим к системе уравнений):

Целевая функция:

Zmax=300X1+200X2+X3+X4+X5+X6

Заполняем таблицу, решая задачу по приведенному выше алгоритму:

Ответ: Zmax=1775 Х оптимал. =(9/4;11/2;0;7/4;1/2;0)\

Проверка: 300*9/4+200*11/2=1775

Заключение

В результате работы над данным курсовым проектом были исследованы:

методы и модели линейного программирования;

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

построение экономико-математической модели задачи;

алгебраический симплекс метод и алгоритм решения задач линейного программирования данным методом;

применение симплексного метода в экономике

В процессе исследования последнего пункта (Применение симплексного метода в экономике) была рассмотрена и решена конкретная экономическая задача оптимизации (Максимизация дохода от производства).

Список используемой литературы

1. Партыка Т.Л., Попов И.И. - “Математические методы”;

2. Фомин Г.П. - “Математические методы и модели в коммерческой деятельности

Размещено на Allbest.ru