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

Федеральное агентство по образованию РФ

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

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

Барнаульский строительный колледж

Курсовая работа.

По дисциплине: «Математические методы»

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

Выполнил: Нунгесер М.В.

Специальность: ПОВТ

Группа: 0881

Преподаватель: Клепикова Н.Н.

Барнаул 2010

Содержание:

Возможно вы искали - Реферат: Упражнения по базам данных MS ACCESS методичка

Введение

Линейное программирование

Симплекс метод

Постановка задачи

Разработка алгоритма

Похожий материал - Дипломная работа: Машинная память

Решение задачи

Программная реализация на языке Delphi

Приложение

Заключение

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


Введение

Очень интересно - Реферат: Носители информации. Общая характеристика, классификация, принципы, кодирования и считывания инф

В последние годы в прикладной математике большое внимание уделяется новому классу задач оптимизации, заключающихся в нахождении в заданной области точек наибольшего или наименьшего значения некоторой функции, зависящей от большого числа переменных. Это так называемые задачи математического программирования, возникающие в самых разнообразных областях человеческой деятельности и прежде всего в экономических исследованиях, в практике планирования и организации производства. Изучение этого круга задач и методов их решения привело к созданию новой научной дисциплины, получившей позднее название линейного программирования. В конце 40-х годов американским математиком Дж. Данцигом был разработан эффективный метод решения данного класса задач – симплекс-метод. К задачам, решаемых этим методом в рамках математического программирования относятся такие типичные экономические задачи как «Определение наилучшего состава смеси», «Задача об оптимальном плане выпуска продукции», «Оптимизация межотраслевых потоков», « Задача о выборе производственной программы», «Транспортная задача», «Задача размещения», «Модель Неймана расширяющейся экономики» и другие. Решение таких задач дает большие выгоды как народному хозяйству в целом, так и отдельным его отраслям.

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


Линейное программирование

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

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

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

Математическая формулировка задачи линейного программирования

Вам будет интересно - Контрольная работа: по Принятие оптимальных решений в экономике и менеджменте с применением

Нужно определить максимум линейной целевой функции (линейной формы)

при условиях

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

Такую задачу называют «основной» или «стандартной» в линейном программировании. Наиболее известным и широко применяемым на практике для решения общей задачи линейного программирования (ЛП) является симплекс метод.

Симплекс метод

Похожий материал - Реферат: Компьютерная безопасность и взлом компьютерных систем

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

Применение симплекс-метода для задачи линейного программирования предполагает предварительное приведение ее формальной постановки к канонической форме с n неотрицательными переменными: (X1 , ..., Xn ) , где требуется минимизация линейной целевой функции при m линейных ограничениях типа равенств. Среди переменных задачи выбирается начальный базис из m переменных, для определенности (X1 , ..., Xm ) , которые должны иметь неотрицательные значения, когда остальные (n-m) свободные переменные равны 0. Целевая функция и ограничения равенства преобразуются к диагональной форме относительно базисных переменных, переменных, где каждая базисная переменная входит только в одно уравнение с коэффициентом 1.

Данная формальная модель задачи линейного программирования обычно задается в форме, так называемой симплекс-таблицы , удобной для выполнения операций симплекс-метода:

Симплекс-таблица

1 X1 X2 ... Xm Xm+1 ... Xn
X0 A0,0 0 0 ... 0 A0,m+1 ... A0,n
X1 A1,0 1 0 ... 0 A1,m+1 ... A1,n
X2 A2,0 0 1 ... 0 A2,m+1 ... A2,n
... ... ... ... ... ... ... ... ...
Xm Am,0 0 0 ... 1 Am,m+1 ... Am,n

К-во Просмотров: 257