Введение 
 

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

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

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

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

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

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

     В последние годы в прикладной математике большое внимание уделяется новому классу задач оптимизации, заключающихся  в нахождении в заданной области  точек наибольшего или наименьшего  значения некоторой функции, зависящей  от большого числа переменных. Это  так называемые задачи математического  программирования, возникающие в  самых разнообразных областях человеческой деятельности и прежде всего в  экономических исследованиях, в  практике планирования и организации  производства. Изучение этого круга  задач и методов их решения  привело к созданию новой научной  дисциплины, получившей позднее название линейного программирования. В конце 40-х годов американским математиком  Дж. Данцигом был разработан эффективный метод решения данного класса задач – симплекс-метод. К задачам, решаемых этим методом в рамках математического программирования относятся такие типичные экономические задачи как «Определение наилучшего состава смеси», «Задача об оптимальном плане выпуска продукции», «Оптимизация межотраслевых потоков», « Задача о выборе производственной программы», «Транспортная задача», «Задача размещения», «Модель Неймана расширяющейся экономики» и другие. Решение таких задач дает большие выгоды как народному хозяйству в целом, так и отдельным его отраслям.

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

 

1 Задача линейного программирования: нахождение оптимального плана 

         1.1 Теоретико-методическое описание метода линейного программирования

 

     В настоящее время линейное программирование является одним из наиболее употребительных  аппаратов математической теории оптимального принятия решений. Линейное программирование — математическая дисциплина, посвященная теории и методам решения задач об экстремумах линейных функций на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств. Линейное программирование является частным случаем выпуклого программирования, которое в свою очередь является частным случаем математического программирования. Одновременно оно — основа нескольких методов решения задач целочисленного и нелинейного программирования. Одним из обобщений линейного программирования является дробно-линейное программирование. Многие свойства задач линейного программирования можно интерпретировать также как свойства многогранников и таким образом геометрически формулировать и доказывать их. Для решения задач линейного программирования разработано сложное программное обеспечение, дающее возможность эффективно и надежно решать практические задачи больших объемов. Владение аппаратом линейного программирования необходимо каждому специалисту в области прикладной математики.

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

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

     В общем виде модель записывается следующим  образом:

1. целевая функция представлена в формуле (1):

     f()= c₁x₁ + c₂x₂ + … + c_nx_n → max(min);                 (1)

2. система ограничений выражена в формуле (2):

                                                    (2)

3. требование неотрицательности представлено в формуле (3):

     x_j ≥ 0,                       (3)

     При этом a_ij, b_i, c_j ( ,   ) – заданные постоянные величины.

     Задача  состоит в нахождении оптимального значения функции (1) при соблюдении ограничений (2) и (3).

     Систему ограничений (2) называют функциональными  ограничениями задачи, а ограничения (3) – прямыми.

     Решения, удовлетворяющие системе ограничений (2) условий задачи и требованиям  неотрицательности (3), называются допустимыми, а решения, удовлетворяющие одновременно и требованиям минимизации (максимализации) целевой функции, – оптимальными.

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

     К числу задач линейного программирования можно отнести задачи:

     1) рационального использования сырья и материалов;

     2) задачи оптимального раскроя;

     3) оптимизации производственной программы предприятий;

     4) оптимального размещения и концентрации производства;

     5) составления оптимального плана перевозок, работы транспорта (транспортные задачи);

     6) управления производственными запасами;

     7) и многие другие, принадлежащие сфере оптимального планирования.

     Линейное  программирование является одной из основных частей того раздела современной  математики, который получил название математического программирования.

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

     Графический метод довольно прост и нагляден. Он основан на геометрическом представлении  допустимых решений задачи. Каждое из неравенств задачи ЛП определяет на координатной плоскости некоторую  полуплоскость, а система неравенств в целом - пересечение соответствующих  плоскостей. Множество точек пересечения  данных полуплоскостей называется областью допустимых решений. ОДР всегда представляет собой выпуклую фигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлен выпуклым многоугольником, неограниченным выпуклой многоугольной областью, отрезком, лучом и т.д. В случае несовместности системы ограничений задачи ОДР является пустым множеством.

     При поиске оптимального решения задач  линейного программирования возможны следующие ситуации: существует единственное решение задачи, существует бесконечное  множество решений; ЦФ не ограничена; область допустимых решений- единственная точка; задача не имеет решений.

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

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

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

     Алгоритм  решения задачи ЛП табличным симплексом-методом состоит из следующих этапов:

     1) рассчитывают и заполняют начальную симплекс-таблицу с допустимым единичным базисом, включая индексную строку.

     2) находят разрешающий столбец;

     3) находят разрешающую строку;

     4) рассчитывают методом Жордано-Гаусса все параметры матрицы;

     5) анализируют полученные данные в индексной строке.

     Таблицы симплекс-метода необходимо строить  до тех пор, пока не будет получен  оптимальный план. План будет считаться  оптимальным, если в последней индексной  строке симплекс-таблицы будут только нули и положительные числа.

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

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

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