Этот класс задач связан с выбором конкретных вариантов органи-зации системы с учетом ресурсных ограничений. Как правило, в зада-чах логического выбора используются изменяемые ячейки, которые могут хранить одно из двух значений: 1 или 0, - иначе «выбирать ва-риант организации» или «не выбирать». В математическом програм-мировании такие задачи называются задачами булевского програм-мирования. Использование булевских переменных позволяет сформулировать различные логические ограничения выбора.
Например, выбор одного из 2-х вариантов организации исследуе-мой системы (1,2) может определяться двумя булевскими переменны-ми (Х1, Х2).
Условие выбора только одного из двух вариантов эквивалентно логическому ограничению: Х1+Х2=1. Такое ограничение моделирует условие взаимоисключения.
Условие выбора хотя бы одного из двух вариантов эквивалентно логическому ограничению Х1+Х2>=1.
Если вариант 2 может быть принят только при принятии варианта 1 (взаимообусловленность) следует использовать ограничение Х1>=Х2. Если же вариант 2 должен быть принят при принятии вари-анта 1, вводится ограничение Х2>=Х1.
В качестве примера рассмотрим задачу о выборе варианта капита-ловложений.
Распределение капиталовложений
Проект Распределение капиталовложений Прибыль
Год 1 Год 2 Год 3
1 5 1 8 20
2 4 7 10 40
3 3 9 2 20
4 7 4 10 15
5 8 6 1 30
Максималь-ный объем капиталовло-жений 25 25 25
Рассматриваются пять проектов, которые могут быть осуществле-ны в течение последующих трех лет. Ожидаемые величины прибыли от реализации каждого из проектов и распределение необходимых капиталовложений по годам (в тыс.$.) приведены в таблице. Предпо-лагается, что каждый утвержденный проект будет реализован за трех-летний период. Требуется выбрать совокупность проектов, которой соответствует максимум суммарной прибыли.
Добавим к таблице исходных данных столбец изменяемых ячеек. Обозначим содержимое этих ячеек как Xi, где i=1, 2,..., 5 определяет номер проекта, а Xi определяет решение: вкладывать (Xi=1) или нет (Xi=0) средства в i-ый проект. Такую переменную, принимающую только два возможных значения (1 или 0), называют булевской.
Ограничения:
1) по объему капиталовложений
в первый год: 5* X1 + 4*X2 +3*X3 + 7*X4 + 8*X5 <= 25;
во второй год: 1* X1 + 7*X2 +9*X3 + 4*X4 + 6*X5 <= 25;
в третий год: 8* X1 + 10*X2 +2*X3 + 10*X4 + 1*X5 <= 25;
2) “естественные” ограничения:
X1X5 = двоичные (булевские)
Целевая функция:
Z= 20*X1 + 40*X2 + 20*X3 + 15*X4 + 30*X5;
Максимизировать Z.
Электронная таблица в этом варианте может выглядеть следую-щим образом.
A B C D E F
1 Проект Распределение капиталовложений (тыс.$) Прибыль (тыс.$) Выбор про-екта (1–да, 0–нет)
// PascalABC.NET 3.0, сборка 1128 procedure Convert(V:array of integer); begin for var i:=0 to V.Length-1 do if V[i]>9 then V[i]:=9 else if V[i]<5 then V[i]:=5 end;
procedure Develop(c:char; k:integer); begin WritelnFormat('*** Массив {0} ***',c); var a:=ArrRandom(k,-5,15); Write('исходный : '); a.PrintLn(','); Convert(a); Write('результат: '); a.PrintLn(','); end;
begin var m:=ReadInteger('Количество элементов в массиве A:'); var n:=ReadInteger('Количество элементов в массиве B:'); Develop('A',m); Develop('B',n) end.
Тестовое решение: Количество элементов в массиве A: 15 Количество элементов в массиве B: 10 *** Массив A *** исходный : 6,5,-5,9,1,0,-3,9,13,12,-4,8,11,14,-5 результат: 6,5,5,9,5,5,5,9,9,9,5,8,9,9,5 *** Массив B *** исходный : 5,12,12,4,7,9,7,-3,-1,-2 результат: 5,9,9,5,7,9,7,5,5,5
0,0(0 оценок)
Полный доступ
Позволит учиться лучше и быстрее. Неограниченный доступ к базе и ответам от экспертов и ai-bota
Оформи подписку
