Табличный симплекс-метод

ИСПОЛЬЗОВАНИЕ ТАБЛИЧНОГО СИМПЛЕКС-МЕТОДА ДЛЯ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ ОПТИМИЗАЦИИ ЭКОНОМИЧЕСКИХ ЗАДАЧ

ВВЕДЕНИЕ

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

1. КРАТКИЙ ОБЗОР АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ ДАННОГО ТИПА

1.1 Математическое программирование

Математическое программирование занимается изучение экстремальных задач и поиском методов их решения. Задачи математического программирования формулируются следующим образом : найти экстремум некоторой функции многих переменных f ( x₁ , x₂ , ... , x_n ) при ограничениях g_i ( x₁ , x₂ , ... , x_n ) * b_i , где g_i - функция, описывающая ограничения, * - один из следующих знаков £ , = , ³ , а b_i - действительное число, i = 1, ... , m. f называется функцией цели ( целевая функция ).

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

Задачу линейного программирования можно сформулировать так . Найти max

при условии : a₁₁ x₁ + a₁₂ x₂ + . . . + a_1n x_n £ b₁ ;

a₂₁ x₁ + a₂₂ x₂ + . . . + a_2n x_n £ b₂ ;

_{. . . . . . . . . . . . . . . . . . . . . . . . . . . .}

a_m1 x₁ + a_m2 x₂ + . . . + a_mn x_n £ b_m ;

x₁ ³ 0, x₂ ³ 0, _{. . .} , x_n ³ 0 _.

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

В матричной форме задачу линейного программирования записывают следующим образом. Найти max c^T x

при условии

A x £ b ;

x ³ 0 ,

где А - матрица ограничений размером ( m´n), b^{(m ´ 1)} - вектор-столбец свободных членов, x^{(n ´ 1)} - вектор переменных, с^Т = [c₁ , c₂ , ... , c_n ] - вектор-строка коэффициентов целевой функции.

Решение х₀ называется оптимальным, если для него выполняется условие с^Т х₀ ³ с^Т х, для всех х Î R(x).

Поскольку min f(x) эквивалентен max [ - f(x) ] , то задачу линейного программирования всегда можно свести к эквивалентной задаче максимизации.

Для решения задач данного типа применяются методы:

1) графический;

2) табличный ( прямой, простой ) симплекс - метод;

3) метод искусственного базиса;

4) модифицированный симплекс - метод;

5) двойственный симплекс - метод.

1.2 Табличный симплекс - метод

Для его применения необходимо, чтобы знаки в ограничениях были вида “ меньше либо равно ”, а компоненты вектора b - положительны.

Алгоритм решения сводится к следующему :

Приведение системы ограничений к каноническому виду путём введения дополнительных переменных для приведения неравенств к равенствам.

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

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

Формируется симплекс-таблица.

Рассчитываются симплекс-разности.

Принимается решение об окончании либо продолжении счёта.

При необходимости выполняются итерации.

На каждой итерации определяется вектор, вводимый в базис, и вектор, выводимый из базиса. Таблица пересчитывается по методу Жордана-Гаусса или каким-нибудь другим способом.

1.3 Метод искусственного базиса

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

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

1.4 Модифицированный симплекс - метод

В основу данной разновидности симплекс-метода положены такие особенности линейной алгебры , которые позволяют в

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

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

Скачать