Предмет экономико-математического моделирования

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

                        

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

                                 .

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

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

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

И, наконец, рассмотрим экономическую  постановку и математическую модель открытой транспортной задачи для случая (1.1.8), когда суммарный спрос меньше суммарного предложения.

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

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

 

1.2.4. Распределение  по должностям

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

Построение экономико-математической модели.

На предприятии имеется  т работников:

                                          ,

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

                                          .

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

Обозначим через  назначение го работника на ю работу. Так как количество работников равно количеству работ, то может принимать только два значения: 1, если й работник назначен на выполнение й работы и 0, если не назначен. При назначении  го работника на ю работу производительность равна . Следовательно, необходимо найти матрицу распределения по должностям, которая обеспечивает максимальное значение линейной функции      

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

Умножая линейную функцию  на «–1», приводим задачу к транспортной, в которой объем запасов каждого поставщика и объем потребностей каждого потребителя равны единице.

 

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

1.3.1. Графоаналитический метод

 

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

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

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

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

Множество планов основной задачи линейного программирования является выпуклым (если оно не пусто). Непустое множество планов называется многогранником решений, а всякая угловая точка многогранника решений – вершиной.

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

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

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

 при условиях                      ,

                                             

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

                                   .

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

Решение задачи линейного  программирования графоаналитическим методом включает следующие этапы.

1. На плоскости строят прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств.
2. Находят полуплоскости, определяемые каждым из ограничений задачи.
3. Строят многоугольник решений.
4. Строят вектор-градиент целевой функции , который указывает направление возрастания целевой функции. Координатами вектора являются коэффициенты целевой функции при переменных   и .
5. Строят линию уровня целевой функции, которая перпендикулярна вектору и пересекает многоугольник решений, а затем передвигают ее в направлении вектора до крайней угловой точки многоугольника решений, т.е. когда линия уровня примет положение опорной прямой. В результате находят точку, в которой целевая функция принимает максимальное значение, либо множество точек с одинаковым максимальным значением целевой функции, если линия уровня целевой функции сливается с одной из сторон многоугольника решений, либо устанавливают неограниченность сверху функции на множестве планов.
6. Определяют координаты точки максимума функции и вычисляют значение целевой функции в этой точке.
7. Минимальное значение целевой функции находится путем передвижения линии уровня целевой функции в направлении, противоположном вектору .

Пример 1.

Найдите экстремум линейной функции

                                   

при условиях-ограничениях:

                                      

Решение. Построим на плоскости многоугольник решений. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки неравенств заменим на знаки точных равенств.

                                        

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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