Задачи логического выбора

Этот класс задач связан с выбором конкретных вариантов органи­зации системы с учетом ресурсных ограничений. Как правило, в зада­чах логического выбора используются изменяемые ячейки, которые могут хранить одно из двух значений: 1 или 0, иначе «выбирать вариант организации» или «не выбирать». В математическом программирова­нии такие задачи называются задачами булевского программирования.

Использование булевских переменных позволяет сформулировать различные логические ограничения выбора.

Например, выбор одного из двух вариантов организации исследу­емой системы (1,2) может определяться двумя булевскими перемен­ными (XI, Х2).

Условие выбора только одного из двух вариантов эквивалентно ло- гическому ограничению: XI + Х2 = 1. Такое ограничение моделирует условие взаимоисключения.

Условие выбора хотя бы одного из двух вариантов эквивалентно] логическому ограничению XI + Х2 >= 1.

Если вариант 2 может быть принят только при принятии вари­анта 1 (взаимообусловленность), следует использовать ограничение Xi >= Х2. Если же вариант 2 должен быть принят при принятии ва-рианта 1, вводится ограничение Х2 >= XI.

В качестве примера рассмотрим задачу о выборе варианта капита-ловложений.

Распределение капиталовложений

Продолжение таблицы

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

Математическая формулировка задачи

Добавим к таблице исходных данных столбец изменяемых ячеек. Обозначим содержимое этих ячеек как Xi, где i = 1,2,..., 5 определя­ет номер проекта, a Xi определяет решение: вкладывать (Xi =1) или нет (Xi = 0) средства в i-ый проект. Такую переменную, принимаю­щую только два возможных значения (1 или 0), называют булевской.

Ограничения:

1) по объему капиталовложений

в первый год: 5* XI + 4*Х2 +3*ХЗ + 7*Х4 + 8*Х5 <= 25; во второй год: 1* XI + 7*Х2 +9*ХЗ + 4*Х4 + 6*Х5 <= 25; в третий год: 8* XI + 10*Х2 +2*ХЗ + 10*Х4 + 1*Х5 <= 25;

2) «естественные» ограничения:
Х1- Х5 = двоичные (булевские).

Целевая функция:

Z= 20*Х1 + 40*Х2 + 20*ХЗ + 15*Х4 + 30*Х5. Максимизировать Z.

Электронная таблица в этом варианте может выглядеть следую­щим образом.

Задачи для исследования систем управления

61

Формула =S(F3:F7)*(B3:B7) записывается в системе EXCEL как СУММПРОИЗВ (F3:F7;B3:B7). Она определяет сумму произведений столбца F3:F7 на столбец ВЗ:В7:

СУММПРОИЗВ (F3:F7;B3:B7) = F3*B3 + F4*B4 + F5*B5 + F6*B6 + + F7*B7.

F3:F7 — изменяемые булевские ячейки, F8 — целевая ячейка.

Ограничения: B8:D8 <= B9:D9.

Контрольные вопросы

1. Как связана математическая формулировка оптимизационной задачи со
структурой ЭТ, на которой будет проводиться поиск решения задачи?

2. Приведите примеры элементов сходства и различия между математической
формулировкой задачи и структурой ЭТ.

3. Укажите основные особенности задач определения оптимального ассорти­
мента продукции.

4. Укажите основные особенности задач о смеси.

5. Могут ли изменяемые ячейки одной задачи иметь разные размерности?

6. Укажите основные особенности систем с дисбалансом. Приведите приме­
ры таких систем.

7. Укажите основные особенности «транспортных задач». Всегда ли они свя­
заны с транспортом?

8. Что такое «скользящий график» и в чем заключается его оптимизация?
Приведите примеры.

9. Укажите основные особенности задач оптимизации инвестиций. В чем за­
ключаются основные трудности поиска решения этих задач?

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

11. К какому виду математического программирования относятся задачи логи­
ческого выбора?

12. Приведите примеры изменяемых ячеек различных уровней. Как бы Вы
определили понятие уровня изменяемой ячейки?

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

Задачи для исследования систем управления

1. Задачи определения объемов производства товаров и услуг

При подборе задач были использованы источники [1, 2, 3, 7].

1.1. Оптимизация производства карамели

Кондитерская фабрика для производства трех видов карамели А, В и С использует три вида основного сырья: сахарный песок, патоку и фруктовое пюре. Нормы расхода сырья каждого вида на производ­ство одной тонны карамели приведены в таблице. В ней же указано общее количество сырья каждого вида, которое может быть использо­вано фабрикой, а также приведена прибыль от реализации 1 т караме­ли соответствующего вида.

Найти оптимальное сочетание объемов производства карамели (по видам), обеспечивающее максимальную прибыль от ее реализа­ции. Исследовать, как изменятся эти объемы при изменении запасов сырья на фабрике.

62

Часть 1. Поиск решений на электронных таблицах

Задачи для исследования систем управления

63

1.2. Оптимизация объемов производства изделий

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

Затраты на производство одного изделия каждого типа определя­ются как величины, прямо пропорциональные времени использова­ния станков (в машино-часах). Стоимость машино-часа составляет долл. 10 для станка 1 и $15 для станка 2. Допустимое время использо­вания станков для обработки изделий всех типов ограничено следую­щими значениями: 500 машино-часов для станка 1 и 380 машино-ча-сов для станка 2. Цены изделий типов 1, 2, 3, и 4 равны соответствен­но $65, $70, $55 и $45.

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