4.3.2. Задача оптимального выбора выполняемых работ

Пусть портфель заказов некоторой фирмы включает в себя работ (проектов, заданий и т.п.). Каждая j-я работа требует для своего выполнения расхода ресурсов i-го вида в объеме . Известно, что каждая работа может принести фирме доход в размере единиц. Известно, что для выполнения работ в требуемый период (месяц, год) фирма располагает ресурсами в объемах . Если выполняются все условия вида:

, (4.51)

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

Выбор выполняемых работ будет произведен с помощью вектора , компоненты которого удовлетворяют условию (4.43). Условие достаточности для отобранных работ с учетом условия (4.43) записывается так:

. (4.52)

Суммарная прибыль от реализации всех отобранных работ определяется выражением вида:

. (4.53)

Совместно с требованиями максимума прибыли при отборе работ можно использовать целевую функцию, которая описывает суммарные затраты времени на выполнение всех отобранных работ:

. (4.54)

Таким образом, выражения (4.53), (4.54), (4.52), (4.43) описывают двухкритериальную, линейную, дискретную ММ оптимального выбора работ из портфеля заказов.

Пример. Пусть фирма к началу месяца получила заказы на разработку пяти комплексов программ (КП). В этом месяце (26 рабочих дней) фирма имеет фонд з/п 100 000 рублей и 8 свободных разработчиков, которые могут быть привлечены к выполнению поступивших заказов. Технико-экономические показатели каждого КП представлены в таблице:

№ КП Показатели	1	2	3	4	5
Прибыль (млн.р.)	2	8	5	3	6
з/п (тыс. рублей)	40	70	30	20	20
Требуемая численность (человек)	4	6	2	1	3
Время разработки (р.д.)	10	12	8	4	6

Модель вида (4.53), (4.54), (4.52), (4.43) примет вид:

; (4.53')

; (4.54')

(4.52')

. (4.43')

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

Пользуясь эвристическим алгоритмом, рассмотренном в задаче о ранце, решим однокритериальную задачу (4.53'), (4.52'), (4.43'):

Возьмем на разработку самый прибыльный комплекс программ – второй: х₂ = 1. Ограничения (4.52') выполняются. Добавим 5-й КП – первое ограничение по з/п выполнилось, второе – не выполнилось (численность 6 + 3 = 9 превысила допустимое значение), следовательно 5-й КП добавлять нельзя. Возьмем вместо него 3-й: х₃ = 1 – оба ограничения выполнились, причем, что называется, под завязку: з/п 70 + 30 = 100; численность 6 + 2 = 8. Получили решение, при котором прибыль якобы максимальна:

С = 8 + 5 = 13 (млн. руб).

Однако существует решение данной задачи: х₃ = 1, х₄ = 1, х₅ = 1, при котором и прибыль больше: С_max = 14 млн. руб, и з/п меньше – 70 тыс. руб., что меньше 100 000 руб, и для выполнения работы может быть занято 6 человек, а не 8. Этот результат подтверждает квазиоптимальность эвристического подхода к решению задач ПР.

КОНТРОЛЬНЫЕ ВОПРОСЫ

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

2. Приведите математическую модель суммарной прибыли от реализации всей продукции.

3. Приведите математическую модель общих затрат времени на выпуск запланированной продукции.

4. Приведите математическую модель численности работников, участвующих в изготовлении продукции.

5. Какие особенности имеют распределительные задачи ПР?

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

7. Приведите математическую модель суммарных затрат времени на выполнение заказов предприятиями.

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

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

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

11. Приведите математическую модель общие затраты на аренду дополнительных средств доставки.

12. Сформулируйте классическую транспортную задачу.

13. Как выглядит КТЗ графически?

14. Приведите математическую модель суммарной стоимости перевозок.

15. Приведите отличия закрытой и открытой КТЗ.

16. Как решаются открытые КТЗ?

17. Докажите, что КТЗ имеет хотя бы одно ненулевое решение.

18. Докажите, что целевая функция стоимости перевозок ограничена.

19. Приведите алгоритм эвристического метода закрытой КТЗ.

20. Приведите граф решенной транспортной задачи о кирпичных заводах и стройках.

21. Сформулируйте задачу о назначениях.

22. Чем отличается задача о назначениях от КТЗ?

23. Какие 3 возможных случая Вы знаете в задаче о назначениях?

24. Приведите модель суммарной эффективности в задаче о назначениях.

25. Какие целевые функции Вы знаете в задаче о назначениях?

26. Сформулируйте задачу оптимального выбора.

27. Приведите математическую модель задачи оптимального выбора в общем виде.

28. Сформулируйте задачу о ранце.

29. Приведите математическую модель задачи о ранце.

30. Приведите алгоритм эвристического метода при решении задачи о ранце.

31. Запишите критерий минимума суммарной массы предметов в ранце.

32. Сформулируйте задачу оптимального выбора выполняемых работ.

33. При каком условии фирма может выполнить все запланированные работы и получить при этом прибыль?

34. Приведите критерий суммарной прибыли от реализации всех отобранных работ.

35. Приведите критерий суммарных затрат времени на выполнение всех отобранных работ.

36. Приведите двухкритериальную ММ оптимального выбора работ из портфеля заказов.