Метод ветвей и границ.

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

 

ПОСТАНОВКА ЗАДАЧИ

Издательское предприятие должно выполнить в течении недели (число дней m = 5) работу по набору текста с помощью работников n категорий (высокая, средняя, ниже средней, низкая). Требуются определить оптимальную численность работников по категориям, при которой обеспечивается выполнение работы с минимальным расходом фонда зарплаты при заданных ограничениях. Исходные данные приведены в таблице 1 и 2.

Таблица 1

Наименование показателей

Обозначение

Исходные данные

Минимальный общий объём выполнения работ в неделю, у.е.

Р

120

Максимальная допустимая численность работников всех категорий, чел.

kmax

5

 

Таблица 2

Наименование показателей

Обозначение

Данные по категориям работающих

1

2

3

4

Коэффициенты целевой функции (дневная тарифная ставка по категориям, у.е.)

c

7,5

5,5

4,0

3,5

Объём работ, выполняемый одним работником в неделю, у.е.

p

40

25

20

17,5

Максимальная численность по категориям, чел.

d

2

2

2

3

Задача должна решаться методом целочисленного линейного программирования в Mathcad 2000/2001.

 

 

ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ
РЕШЕНИЯ
ЗАДАЧИ

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

Решение задачи целочисленного программирования выполняется в два этапа.

На первом этапе выполняется задача линейного программирования без учета целочисленности.

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

Сначала решается, задача без учета условия целочисленности.

Целевая функция определяется по формуле:

,

где    Q – общий фонд зарплаты на выполнение работы;

x1, x2, …, xn – численность работников по категориям;

n – число категорий работников;

c1, c2,…, cn – дневная тарифная ставка одного работника по категориям;

m – число рабочих дней в неделю, m = 5.

Целевую функцию можно записать в векторной форме:

 

При решении задачи должны выполняться следующие ограничения. Ограничение сверху

                                                   x d                                                           (1)

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

В ограничении

                                                                                                      (2)

учтено, что общая численность работников не должна превышать kmax.

В ограничении снизу

                                                   р × х≥Р                                                        (3)

отражается, что все работники вместе должны выполнить заданный объем работ Р.

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

                                                     x≥0                                                           (4)

Математическая модель решения задачи без учета условия целочисленности включает следующие выражения:

                                                      ,                                            (5)                                               

xd

р × х≥Р,

x ≥ 0.

Модель целочисленного программирования должна включать выражения (5), а также дополнительные ограничения, с помощью которых нецелочисленные переменные х заменяются целочисленными значениями. Конкретные выражения модели с целочисленными переменными рассмотрены в следующем подразделе.

 

 

 

 

 

 

 

РЕШЕНИЕ ЗАДАЧИ ОПТИМИЗАЦИИ В MATHCAD

Исходные данные для примера даны в табл. 1 и 2.

Для решения задачи используется пакет Mathcad с функцией Minimize. Данная функция определяет вектор решения задачи:

х := Minimize (Q, x),

где Q — выражение целевой функции, определяющей минимальный фонд зарплаты, х – вектор переменных.

Сначала задача решается без учета условия целочисленности. Это решение приведено в Приложении 1. В первой строке введены нулевые начальные значения вектора х и целевая функция Q(x). После слова Given и перед функцией Minimize указаны ограничения. В результате получена нецелочисленная оптимальная численность по категориям:

х = [2 ; 0; 2; 1,143]

с фондом зарплаты Q = 135 у. е.

Из данного решения находится целочисленное решение методом ветвей и границ.

Сначала в полученном решении анализируется дробная величина х4 =
= 1,143. Для нее можно задать два целочисленных значения: х4 = 1 и х4 = 2. Начинается построение дерева решений (Приложение 2). На дереве решений откладывается начальный нулевой узел. Затем он соединяется первым узлом х4, и из этого узла проводятся две ветви, соответствующие ограничениям: х= 1 и х4 = 2.

Для ветви с ограничением х4 = 1 решается задача линейного программирования, данная в Приложении 1, с учетом этого ограничения .

В результате получено решение этой задачи. Переменная х1 стала целочисленная, но переменная х2 стала дробной х2 = 0,9.

Далее продолжается построение первой ветви. Из узла х2 проводится ветвь для х2 = 1 и с этим ограничением решается задача линейного программирования. Получается решение хТ = (2   1   0,875   1).

Для продолжения ветви создается узел х3 и ветвь х3 = 1. Снова выполняется задача линейного программирования со всеми тремя ограничениями: x4 = 1, х2 = 1, х3 = 1. С этими ограничениями задача имеет решение   хТ =
= (1,938   1   1   1).

Для продолжения ветви создается узел х1 и ветвь х1 = 2. Снова выполняется задача линейного программирования со всеми тремя ограничениями: x4 = 1, х2 = 1, х3 = 1, х1 = 2. С этими ограничениями задача имеет решение хТ = = (2   1   1   1).

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

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

Из результативных выбирается наилучшее и оно принимается как оптимальное целочисленное решение всей задачи с минимальной величиной Q(x). В нашем случае мы имеем два оптимальных целочисленных решения

Q(х) = 140,

xT = (2   1    1    1),

xT = (1   1    2    2).

Ветвь, содержащая оптимальное решение, показана на дереве решений. Оптимальное целочисленное решение задачи определения численности работников приводится в Приложении 1.

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

Скачать решение задачи:


Имя файла: 2.rar
Размер файла: 24.99 Kb

Если закачивание файла не начнется через 10 сек, кликните по этой ссылке