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

ВВЕДЕНИЕ

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

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 - положительны.

--> ЧИТАТЬ ПОЛНОСТЬЮ <--