Организация оплаты труда

                                Введение.                               

Многие задачи, с которыми приходится иметь дело в повседнев­ной  практике,

являются многовариантными. Среди множества возможных вариантов  в условиях

рыночных отношений приходится отыскивать наилучшие в некотором  смысле при

ограничениях, налагаемых на природные, экономические и технологические

возможности. В связи с  этим возникла необходимость применять  для анализа и

синтеза экономических ситуаций и систем математические методы и  современную

вычислительную технику? Такие методы объединяются под общим  названием —

математическое программирование.

     Математическое  программирование — область математики, разрабатывающая

теорию и численные  методы решения многомерных экстремальных  задач с

ограничениями, т. е. задач  на экстремум функции многих пере­менных  с

ограничениями на область  изменения этих переменных.

Функцию, экстремальное значение которой нужно найти в условиях экономических

возможностей, называют целевой, показателем эффективности или 

критерием оптимальности. Экономические  возможности формализуются в  виде

системы ограничений. Все  это составляет математическую модель.

Математическая модель задачи — это отражение оригинала  в виде функций,

уравнений, неравенств, цифр и т. д. Модель задачи математического

программирования включает:

1)     совокупность  неизвестных величин, действуя  на которые, систему

можно совершенствовать. Их называют планом задачи (вектором управления,

решением, управлением, стратегией, поведением и др.);

2)     целевую функцию  (функцию цели, показатель эф­фективности, критерий

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

наилучший вариант -из множества  возможных. Наилучший ва­риант доставляет

целевой функции экстремальное  значение. Это может быть прибыль, объем

выпуска или реализации, затраты  производства, издержки обращения, уровень

обслуживания или дефицитности, число комплектов, отходы и т. д.;

Эти условия следуют из ограниченности ресурсов, которыми располагает  общество в

любой момент времени, из необходимости  удовлетворения насущных потребностей, из

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

только материальные, финансовые и трудовые ресурсы. Таковыми могут  быть

возможности технического, технологического и вообще научного потенциала.

Нередко потребности превышают  возможности их удовлетворения. Математически

ограничения выражаются в  виде уравнений и неравенств. Их совокупность образует

область допустимых решений (область экономических возможно­стей). План,

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

Допустимый план, доставляющий функции цели экстремальное значение, называется

оптимальным. Оптимальное  решение, вообще говоря, не обяза­тельно

единственно, возможны случаи, когда оно не существует, имеется  конечное или

бесчисленное множество  оптимальных решений.

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

программированием.   Методы и модели линейного программирования широко

применяются при оптимизации  процессов во всех отраслях народного  хозяйства: при

разработке производственной программы предприятия, распределении  ее по

исполнителям, при размещении заказов между исполнителями  и по временным

интервалам, при определении  наилучшего ассортимента выпускаемой  продукции, в

задачах перспективного, текущего и оперативного планирования и управления;

при планировании грузопотоков, определении плана товарооборота  и его

распределении; в задачах  развития и размещения производительных сил, баз и

складов систем обращения  материальных ресурсов и т. д. Особенно широкое

применение методы и модели линейного программирования получили при решении

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

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

Начало линейному программированию было положено в 1939 г. советским

математиком-экономистом  Л. В. Канторовичем в работе «Математические  методы

организации и планирования производства». Появление этой работы открыло новый

этап в применении математики в экономике. Спустя десять лет американский

математик Дж. Данциг разработал эффективный метод решения данного  класса задач

— симплекс-метод. Общая идея симплексного метода (метода последовательного

улучшения плана) для решения  ЗЛП состоит в следующем:

1)     умение находить  начальный опорный план;

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

3)     умение переходить  к нехудшему опорному плану.

     §1.Задача линейного  программирования  и свойства  ее решений.

     1.1 Понятие линейного  программирования. Линейное про­граммирование—раздел

математического программирования, применяемый при разработке методов  отыскания

экстремума линейных функций  нескольких переменных при линейных дополнительных

ограничениях, налагаемых на переменные. По типу решаемых задач  его методы

разделяются на универсальные  и специальные. С помощью универсальных  методов

могут решаться любые задачи линейного программирования (ЗЛП).

Специальные методы учитывают  особенности модели задачи, ее целевой  функции и

системы ограничений.

Особенностью задач линейного  программирования является то, что  экстремума

целевая функция достигает  на границе области допустимых решений. Классические

же методы дифференциального  исчисления связаны с на­хождением экстремумов

функции во внутренней точке  области допустимых значений. Отсюда —

необходимость разработки новых  методов.

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

Общей задачей линейного  программирования называют задачу

       (1)

при ограничениях

       (2)

       (3)

            (4)

          (5)

     - произвольные    (6)

где - заданные

действительные числа; (1) – целевая функция; (1) – (6) –ограничения;

      - план задачи.

     1.2 Свойства  решений.

Пусть ЗПЛ представлена в  следующей записи:

               (7)

          (8)

                          (9)

Чтобы задача (7) – (8) имела  решение, системе её ограничений (8) должна быть

совместной. Это возможно, если  r этой системы не больше числа  неизвестных n.

Случай r>n вообще невозможен. При r= n система имеет единственное решение,

которое будет при 

оптимальным. В этом случае проблема выбора оптимального решения  теряет смысл.

Выясним структуру координат  угловой точки многогранных решений. Пусть r<n.

В этом случае система векторов

содержит базис — максимальную линейно независимую подсистему векторов, через

которую любой вектор системы  может быть выражен как ее линей­ная  комбинация.

Базисов, вообще говоря, может  быть несколько, но не более 

. Каждый из них состоит  точно из r векторов. Переменные ЗЛП,  соответствующие

r векторам базиса, называют, как известно, базисными и обо­значают  БП.

Остальные n – r переменных будут  свободными, их обозначают СП. Не

ограничивая общности, будем  считать, что базис составляют первые m векторов

. Этому базису соответствуют  базисные переменные 

, а свободными будут  переменные 

.

Если свободные переменные приравнять нулю, а базисные переменные при этом

примут неотрицательные  значения, то полученное частное решение  системы (8)

называют опорным решением (планом).

     Теорема. Если  система векторов 

содержит m линейно независимых  векторов

, то допустимый план   

(10) является крайней точкой  многогранника планов.

     Теорема. Если  ЗЛП имеет решение, то целевая  функция достигает

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

Если же целевая функция  достигает экстремального значения бо­лее чем в одной

крайней точке, то она достигает  того же значения в любой точке, являющейся их

выпуклой линейной комбинацией.

                    §2.Графический способ решения  ЗЛП.                   

Геометрическая интерпретация  экономических задач дает возможность  наглядно

представить, их структуру, выявить  особенности и открывает пути исследования

более сложных свойств. ЗЛП  с двумя переменными всегда можно  решить

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

в пространствах, размерность  которых больше трех, графическое  решение,

вообще говоря, невозможно. Случай двух переменных не имеет особого

практического значения, однако его рассмотрение проясняет свойства ОЗЛП,

приводит к идее ее решения, делает геометрически наглядными способы  решения

и пути их практической реализации.

Пусть дана задача

                (11)

              (12)

                              (13)

Дадим геометрическую интерпретацию  элементов этой задачи. Каждое из ограничений

(12), (13) задает на плоскости 

некоторую полуплоскость. Полуплоскость  — выпуклое множество. Но пересечение

любого числа выпуклых множеств является выпуклым множест­вом. Отсюда следует,

что область допустимых решений  задачи (11) — (13)  есть выпуклое множество.

Перейдем к геометрической интерпретации целевой функции. Пусть область

допустимых решений ЗЛП  — непустое множество, например многоугольник 

.

    

Выберем произвольное значение целевой функции 

. Получим 

. Это уравнение прямой  линии. В точках прямой NМ целевая  функция

сохраняет одно и то же постоянное значение

. Считая в равенстве  (11) 

параметром, получим уравнение  семейства параллельных прямых, называемых линиями

уровня целевой функции (линиями постоянного значения).

Найдём частные производные  целевой функции по  и 

                (14)

                (15)

Частная производная (14)  ((15)) функции показывает скорость ее возрастания

вдоль данной оси. Следовательно, 

и — скорости

возрастания 

соответственно вдоль  осей 

и . Вектор 

называется градиентом функции. Он показывает направление наискорейшего

возрастания целевой функции:

    

Вектор —  указывает

направление наискорейшего  убывания целевой функции. Его называют

антиградиентом.

Вектор перпендикулярен  к прямым  семейства 

Из геометрической интерпретации  элементов ЗЛП вытекает следующий  порядок ее

графического решения.

1.                  С учетом системы ограничений  строим область допустимых

решений

2.                  Строим вектор 

наискорейшего возрастания  целевой функции — вектор градиентного направления.

3.                  Проводим произвольную линию  уровня 

4.                  При решении задачи на максимум  перемещаем линию уровня 

в направлении вектора 

так, чтобы она касалась области допустимых решений в  ее крайнем положении

(крайней точке). В случае  решения задачи на минимум  линию уровня 

перемещают в антиградиентном  направлении

5.                  Определяем оптимальный план 

и экстремальное значение целевой функции 

.

                          §3.Симплексный метод.                         

Общая идея симплексного метода (метода последовательного улучшения  плана)

для решения ЗЛП состоит

1)     умение находить  начальный опорный план;

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

3)     умение переходить  к нехудшему опорному плану.

Пусть ЗЛП представлена системой ограничений в каноническом виде:

     .

Говорят, что ограничение  ЗЛП имеет предпочтительный вид, если при

неотрицательной правой части 

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

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

Пусть система ограничений  имеет вид

    

Сведем задачу к каноническому  виду. Для этого прибавим к левым  частям неравенств

дополнительные переменные    

. Получим систему, эквивалентную  исходной:

     ,

которая имеет предпочтительный вид

     .

В целевую функцию дополнительные переменные вводятся с коэффициентами, равными

нулю 

.

Пусть далее система ограничений  имеет вид

    

Сведём её к эквивалентной  вычитанием дополнительных переменных    

из левых частей неравенств системы. Получим систему

    

Однако теперь система  ограничений не имеет предпочтительного  вида, так как

дополнительные переменные 

входят в левую часть (при 

) с коэффициентами, равными  –1. Поэтому, вообще говоря, базисный  план 

не является допустимым. В  этом случае вводится так называемый искусственный

базис. К левым частям ограничений-равенств, не имеющих предпочтительного вида,

добавляют искусственные  переменные

. В целевую функцию  переменные 

, вводят с коэффициентом  М в случае решения задачи  на минимум и с коэффициентом

-М для задачи на максимум, где М - большое положительное  число. Полученная

задача называется М-задачей, соответствующей исходной. Она всегда имеет

предпочтительный вид.