Оглавление

 

ВВЕДЕНИЕ

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

       Большинство объектов, изучаемых экономической  наукой, может быть  охарактеризовано  кибернетическим  понятием  сложная  система.

       Наиболее  распространено понимание системы  как совокупности элементов, находящихся во взаимодействии и образующих некоторую целостность,  единство.  Важным  качеством любой системы является эмерджентность - наличие таких  свойств,  которые  не присущи ни  одному из элементов,  входящих в систему.  Поэтому при изучении систем недостаточно пользоваться методом их расчленения на  элементы  с последующим изучением этих элементов в отдельности. Одна из трудностей экономических исследований - в том, что  почти  не существует экономических объектов, которые можно  было  бы  рассматривать  как  отдельные  (внесистемные) элементы.

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

       Сложность экономики иногда рассматривалась  как  обоснование невозможности ее моделирования,  изучения средствами математики. Но такая точка зрения в принципе неверна. Моделировать можно объект любой природы и любой сложности.  И как раз сложные объекты представляют наибольший интерес для моделирования; именно здесь  моделирование  может  дать  результаты,  которые нельзя получить другими способами исследования.

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

 

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 Модифицированный симплекс - метод

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

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

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

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

 

2.СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ

         Для производства двух видов  изделий А и В используется  три типа технологического оборудования. На производство единицы изделия А идёт времени, часов : оборудованием 1-го типа - а₁ , оборудованием 2-го типа - а₂ , оборудованием 3-го типа - а₃ . На производство единицы изделия В идёт времени, часов : оборудованием 1-го типа - b₁ , оборудованием 2-го типа - b₂ ,_, оборудованием 3-го типа - b₃ .

       На  изготовление всех изделий администрация предприятия может предоставить оборудование 1-го типа не более, чем на t₁ , оборудование 2-го типа не более, чем на t₂ , оборудование 3-го типа не более, чем на t₃ часов.

       Прибыль от реализации единицы готового изделия  А составляет a рублей, а изделия В - b рублей.

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

       а₁ = 1 b₁ = 5 t₁ = 10 a = 2

       а₂ = 3 b₂ = 2 t₂ = 12 b = 3

       а₃ = 2 b₃ = 4 t₃ = 10

 

3.РАЗРАБОТКА И ОПИСАНИЕ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ

3.1 Построение математической  модели задачи