ИСПОЛЬЗОВАНИЕ ТАБЛИЧНОГО СИМПЛЕКС-МЕТОДА ДЛЯ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ ОПТИМИЗАЦИИ ЭКОНОМИЧЕСКИХ ЗАДАЧ
    
    ВВЕДЕНИЕ
    
    Цель данного курсового проекта - составить план производства требуемых изделий, обеспечивающий максимальную прибыль от их реализации, свести данную задачу к задаче линейного программирования, решить её симплекс - методом и составить программу для решения задачи этим методом на ЭВМ.
    
    1. КРАТКИЙ ОБЗОР АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ ДАННОГО ТИПА
    
    1.1 Математическое программирование
    
    Математическое программирование занимается изучение экстремальных задач и поиском методов их решения. Задачи математического программирования формулируются следующим образом : найти экстремум некоторой функции многих переменных f ( x1, x2, ... , xn ) при ограничениях gi ( x1, x2, ... , xn ) ? bi , где gi - функция, описывающая ограничения, ? - один из следующих знаков ? , ? , ? , а bi - действительное число, i = 1, ... , m. f называется функцией цели ( целевая функция ).
    Линейное программирование - это раздел математического программирования, в котором рассматриваются методы решения экстремальных задач с линейным функционалом и линейными ограничениями, которым должны удовлетворять искомые переменные.
    Задачу линейного программирования можно сформулировать так . Найти max
    
    при условии : a11 x1 + a12 x2 + . . . + a1n xn ? b1 ;
    a21 x1 + a22 x2 + . . . + a2n xn ? b2 ;
    . . . . . . . . . . . . . . . . . . . . . . . . . . . .
    am1 x1 + am2 x2 + . . . + amn xn ? bm ;
    x1 ? 0, x2 ? 0, . . . , xn ? 0 .
    Эти ограничения называются условиями неотрицательности. Если все ограничения заданы в виде строгих равенств, то данная форма называется канонической.
    
    В матричной форме задачу линейного программирования записывают следующим образом. Найти max cT x
    при условии
    A x ? b ;
    x ? 0 ,
    где А - матрица ограничений размером ( m?n), b(m?1) - вектор-столбец свободных членов, x(n ? 1) - вектор переменных, сТ = [c1, c2, ... , cn ] - вектор-строка коэффициентов целевой функции.
    Решение х0 называется оптимальным, если для него выполняется условие сТ х0 ? сТ х , для всех х ? R(x).
    Поскольку min f(x) эквивалентен max [ - f(x) ] , то задачу линейного программирования всегда можно свести к эквивалентной задаче максимизации.
    Для решения задач данного типа применяются методы:
    1) графический;
    2) табличный ( прямой, простой ) симплекс - метод;
    3) метод искусственного базиса;
    4) модифицированный симплекс - метод;
    5) двойственный симплекс - метод.
    
    1.2 Табличный симплекс - метод
    
    Для его применения необходимо, чтобы знаки в ограничениях были вида " меньше либо равно ", а компоненты вектора b - положительны.
    Алгоритм решения сводится к следующему :
    Приведение системы ограничений к каноническому виду путём введения дополнительных переменных для приведения неравенств к равенствам.
    Если в исходной системе ограничений присутствовали знаки " равно " или " больше либо равно ", то в указанные ограничения добавляются
    искусственные переменные, которые так же вводятся и в целевую функцию со знаками, определяемыми типом оптимума.
    Формируется симплекс-таблица.
    Рассчитываются симплекс-разности.
    Принимается решение об окончании либо продолжении счёта.
    При необходимости выполняются итерации.
    На каждой итерации определяется вектор, вводимый в базис, и вектор, выводимый из базиса. ............