Симплекс-метод, его сущность

Содержание.

Введение……………………………………………………………………………………….с.5.

1. Теоретическая часть.

Глава 1. Простой симплекс-метод.

1.1 Обоснование и описание вычислительной процедуры. Приведение задачи линейного программирования к стандартной форме……………………………с.7

1.2 Симплексный метод решения задач……………………………………..…...с.8.

1.3 Алгоритм симплекс-метода…………………………………………………с.10.

1.4 Решение задачи оптимизации. Построение аналитической модели……...с.12.

1.5 Приведение задачи к стандартной форме. Определение начального допустимого решения…………………………….……………………………...с.14.

Глава 2. Двухэтапный метод.

2.1 Искусственное начальное решение…………………………………………с.16.

2.2 Алгоритм двухэтапного метода……………………………………………..с.19.

Глава 3. Особые случаи симплекс-метода……………………………………………...23.

3.1 Вырожденность……………………………………………………………....с.24.

3.2 Альтернативные оптимальные решения…………………………………....с.27.

3.3 Неограниченные решения…………………………………………………...с.30.

3.4 Отсутствие допустимых решений…………………………………………..с.32.

2. Практическая часть.

2.1 Постановка задачи…………..……………………………………………………..с.34.

2.2 Решение…..…………………………………………………………………………с.36.

Заключение…………………………………………………………………………………...с.39.

Литература…………………………………………………………………………………....с.40.

Введение.

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

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

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

Оптимизация – целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.

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

Постановка задачи оптимизации предполагает существование конкурирующих свойств процесса, например:

· количество продукции - расход сырья

· количество продукции - качество продукции

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

При постановке задачи оптимизации необходимо:

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

Типичный пример неправильной постановки задачи оптимизации:

«Получить максимальную производительность при минимальной себестоимости».

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

Правильная постановка задачи могла быть следующая:

а) получить максимальную производительность при заданной себестоимости;

б) получить минимальную себестоимость при заданной производительности;

В первом случае критерий оптимизации - производительность а во втором - себестоимость.

2. Наличие ресурсов оптимизации, под которыми понимают возможность выбора значений некоторых параметров оптимизируемого объекта.

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

4. Учёт ограничений.

1. Теоретическая часть.

Глава 1. Простой симплекс-метод.

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

Любая задача линейного программирования приводится к стандартной (канонической) форме основной задачи линейного программирования, которая формулируется следующим образом: найти неотрицательные значения переменных X1 , X2 , Xn , удовлетворяющих ограничениям в виде равенств:

A11X1 + A12X2 + … + A1nXn = B1;

A21X1 + A22X2 + … + A2nXn = B2;

……………………………………

Am1X1 + Am2X2 + … + AmnXn = Bm;

Xj ≥ 0, j=1,…,n

и обращающих в максимум линейную функцию этих переменных:

E = C1X1 + C2X2 + … + CnXn Þ max

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

Bj ≥ 0, j=1,…,n

Приведение к стандартной форме необходимо, так как большинство методов решения задач линейного п

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать