Понятие метода линейного программирования

Минский филиал государственного образовательного учреждения высшего  профессионального образования  «Московский государственный университет  экономики, статистики и информатики (МЭСИ)»

Минский филиал МЭСИ

 

 

КАФЕДРА БУХГАЛТЕРСКОГО УЧЕТА И ФИНАНСОВ

 

Контрольная работа

по дисциплине “ Статистика ”

Вариант 3

 

 

Выполнила:

Студентка 2 курса

группы  №  ЗОМЕ 11-1         Парахневич М.П.

 

 

 

Руководитель:

преподаватель                                                          Машканова Л.В.

 

Минск 2012

 

Введение

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

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

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

 

Понятие метода линейного  программирования

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

Линейное программирование представляет собой наиболее часто  используемый метод оптимизации. К  числу задач линейного программирования можно отнести задачи:

• рационального использования сырья и материалов;
• задачи оптимального раскроя;
• оптимизации производственной программы предприятий;
• оптимального размещения и концентрации производства;
• составления оптимального плана перевозок, работы транспорта;
• управления производственными запасами;
• и многие другие, принадлежащие сфере оптимального планирования.

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

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

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

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

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

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

 

Особенности и задачи линейного  программирования

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

Линейное программирование представляет собой наиболее часто  используемый метод оптимизации. К  числу задач линейного программирования можно отнести задачи:

• рационального использования сырья и материалов;
• задачи оптимального раскроя;
• оптимизации производственной программы предприятий;
• оптимального размещения и концентрации производства;
• составления оптимального плана перевозок, работы транспорта (транспортные задачи);
• управления производственными запасами;
• и многие другие, принадлежащие сфере оптимального планирования.

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

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

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

Формы задач линейного  программирования:

1. стандартная;

1.1 первая стандартная  форма;

1.2 вторая стандартная  форма;

2. каноническая.

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

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

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

Задачи линейного программирования решаются несколькими методами:

1. графический метод;

2. симплексный метод;

3. двойственность в ЛП;

4.двойственный симплексный  метод.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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