Целочисленное программирование

Размещено на http://www.allbest.ru/

Введение

Проектирование - разработка проекта.

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

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

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

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

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

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

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

Радиоэлектронный функциональный узел - РЭС, представляющее собой функционально законченную сборочную единицу, выполненную на несущей конструкции, реализующую определенную эксплуатационную функцию и не имеющее самостоятельного применения (например, блок коммутации, блок питания и т.п.).

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

По конструктивной сложности РЭС имеют также ряд уровней: шкаф, блок, модуль, ячейка и др.

Изделие - комплекс, комплект, сборочная единица, деталь.

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

Алгоритм - строго определенная последовательность операций, приводящая к определенному результату.

Множество - совокупность элементов некоторой природы (людей, систем, точек, понятий и т.п.).

Информация - совокупность сведений о процессах и явлениях в некотором объекте (субъекте). Для передачи или хранения информации используется тот или иной язык. Язык характеризуется знаками (символами) и правилами их применения.

Сообщение - совокупность знаков (символов), содержащих некоторую информацию.

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

Радиосигнал - электромагнитное поле, модулированное переносимым этим сигналом сообщением.

Вооружение - средства, предназначенные для поражения живой силы, техники, сооружений и других объектов противника.

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

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

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

1. Понятие о целочисленном программировании

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

В некоторых случаях допускается округление результатов. Например, если в оптимальном плане предусмотрено, что следует произвести 499683,3 автомашины, то экономически обосновано округление результата до 499683 или даже до 500000.

Существуют однако задачи, в которых подобное округление может создать большую ошибку. Например, если в оптимальном плане предусмотрено, что следует построить 0,67 заводов, то формальное округление до 0 или 1 недопустимо.

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

Если задача целочисленного программирования задана в канонической форме, она формулируется следующим образом:

найти максимум функции цели (линейной формы)

при системе ограничений



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

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

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

- оптимизацию схемно-конструктивных решений (по критерию надежности и стойкости) методами и средствами математического и физического моделирования;

2. Метод Гомори решения задач целочисленного программирования

целочисленное программирование метод

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

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

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

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

где в фигурных скобках - дробные части соответственно свободного члена и коэффициентов при неизвестных.

Например, из симплексной таблицы получаем такое уравнение:

.

Дробную часть свободного члена получаем, вычитая из самого числа его целую часть следующим образом:

.

Аналогично получаем дробные части коэффициентов при неизвестных:

(при x3),

(при x4).

А общее правило нахождения дробных частей таково: целой частью вещественного числа a называется самое большое целое число [a], не превыщающее a; дробной частью вещественного числа a называется разность {a} = a - [a] самого числа a и его целой части [a].

Далее следует преобразовать полученное неравенство в уравнение путём введения дополнительной неизвестной :

.

В нашем примере по приведённой выше формуле получается следующее уравнение: .

Пример 1. Решить методом Гомори следующую задачу целочисленного программирования. Найти максимум целевой функции

при системе ограничений

Решение. Решаем задачу симплекс-методом.

Дополнительные неизвестные x3 и x4 примем за базисные. Выразим базисные неизвестные и функцию цели через неосновные переменные:

Из коэффициентов составим симплексную таблицу:

Таблица 1
Базисные неизвестные	Свободные члены	Свободные неизвестные	Вспомогательные коэффициенты
		X1	X2
X3	6	2	1
X4	5	1	4
С	0	-3	-2

Составляем следующие таблицы до получения оптимального плана:

Таблица 2
Базисные неизвестные	Свободные члены	Свободные неизвестные	Вспомогательные коэффициенты
		X3	X2
X1	3	1/2	1/2
X4	2	-1/2	7/2	-1
С	9	3/2	-1/2	3

Таблица 3
Базисные неизвестные	Свободные члены	Свободные неизвестные	Вспомогательные коэффициенты
		X3	X4
X1	19/7	4/7	-1/7	-1/2
X2	4/7	-1/7	2/7
С	65/7	10/7	1/7	1/2

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

Первое уравнение на основании таблицы запишется так:

.

Определив дробные части коэффициентов при неизвестных и свободных членов, получаем следующее дополнительное условие:

или, введя добавочную переменную ,

.

Получаем новую строку в симплексной таблице, полученной из таблицы 3 и добавления коэффициентов из только что полученного уравнения:

Таблица 4
Базисные неизвестные	Свободные члены	Свободные неизвестные	Вспомогательные коэффициенты
		X3	X4
X1	19/7	4/7	-1/7	-1/2
X2	4/7	-1/7	2/7
X5	-5/7	-4/7	-6/7
С	65/7	10/7	1/7	1/2

Совершаем шаг симплекс-метода и получаем таблицу:

Таблица 5
Базисные неизвестные	Свободные члены	Свободные неизвестные	Вспомогательные коэффициенты
		X3	X4
X1	17/6	2/3	-1/6	1/7
X2	1/3	-1/3	1/3	-2/7
X4	5/6	2/3	-7/6
С	55/6	4/3	1/6	-1/7

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

Составляем следующую таблицу:

Таблица 6
Базисные неизвестные	Свободные члены	Свободные неизвестные	Вспомогательные коэффициенты
		X3	X4
X1	17/6	2/3	-1/6	1/7
X2	1/3	-1/3	1/3	-2/7
X4	5/6	2/3	-7/6
X6	-5/6	-2/3	-5/6
С	55/6	4/3	1/6	-1/7

Оптимальный план получаем из следующей, завершающей таблицы:

Таблица 7
Базисные неизвестные	Свободные члены	Свободные неизвестные	Вспомогательные коэффициенты
		X3	X6
X1	3	4/5	-1/5	1/6
X2	0	-3/5	2/5	-1/3
X4	2	8/5	-7/5	7/6
X5	1	4/5	-6/5
С	9	6/5	1/5	-1/6

Так как найденный оптимальный план удовлетворяет условию целочисленности, задача целочисленного программирования решена. Координаты x5 и x6 можно не учитывать, так как начальные условия задачи содержит лишь четыре неизвестные. Поэтому окончательный оптимальный план запишется так: , а максимум функции цели равен 9.

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

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

Задание границ, в которых должны находиться значения неизвестных в задаче целочисленного программирования, можно записать так:

.

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

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

Сначала решается, допустим, симплекс-методом задача линейного программирования, соответствующая задаче целочисленного программирования. Пусть найден оптимальный план в этой задаче и значением какой-либо его координаты является дробное число. Тогда потребуется составить две новые задачи линейного программирования. Как это сделать?

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

.

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

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

· оптимальный план не является целочисленным,

· оптимальный план является целочисленным,

· задача не имеет решений.

Лишь в первом случае возможно "ответвление" новых задач способом, показанным выше. Во втором и третьем случае "ветвление" прекращается.

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

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

· если задача задана в нормальной форме, то перед её решением нижняя граница имеет значение нуль (то есть );

· если на некоторой итерации (назовём её p-й) найденный план не является целочисленным и максимальное значение целевой функции больше ранее установленной нижней границы, то на следующей итерации нижняя граница максимального значения целевой функции остаётся прежней (как на предыдущей итерации, то есть );

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

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

Согласно алгоритму решения задачи целочисленного программирования методом ветвей и границ, на каждой p-й итерации требуется сделать 4 шага.

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

· Шаг 2. Решается выбранная из списка задача линейного программирования. Если задача не имеет решения или для полученного на этом шаге оптимального плана значение функции цели , то следует принять и выполнить шаг 1. В противном случае выполнять шаг 3.

· Шаг 3. Если найденный оптимальный план является целочисленным, то следует принять, что и выполнить шаг 1. В противном случае выполнить шаг 4.

· Шаг 4. Выбрать любую дробную координату оптимального плана . Определить целую часть координаты, составить две новые задачи линейного программирования и включить их в список решаемых задач. Новые задачи отличаются от задачи, выбранной на шаге 1 только границами допустимых значений выбранной координаты. Принять, что и выполнить шаг 1.

Пример 2. Решить методом ветвей и границ следующую задачу целочисленного программирования. Найти максимум целевой функции

при системе ограничений

Решение. Допустим, что заданы или определены следующие границы оптимальных значений неизвестных:

.

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

В списке решаемых задач - 1-я задача:

Итерация 1.

Шаг 1. С помощью симплекс метода получено решение 1-й задачи:

.

Так как найденный план не является целочисленным, следует шаг 4.

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

Итак, следует решить 2-ю задачу:

и 3-ю задачу:

Нижняя граница максимального значения целевой функции .

Итерация 2.

Шаг 1. Из списка решаемых задач выбираем 2-ю задачу.

Шаг 2. Констатируем, что 2-я задача не имеет решения, так как её система ограничений несовместна. Тогда и следует следующая итерация.

Итерация 3.

Шаг 1. В списке имеется только одна - 3-я задача.

Шаг 2. Применяя симплекс-метод, получаем решение 3-й задачи:

.

Так как это решение не является целочисленным, следует шаг 4.

Шаг4. Выбираем дробную координату . Тогда и . Применяя границы значений неизвестных из 3-й задачи, получаем две новых задачи.

4-я задача:

5-я задача:

Нижняя граница максимального значения функции цели .

Итерация 4.

Шаг 1. Из списка решаемых задач, в котором имеются 4-я и 5-я задачи, выбираем 4-ю задачу.

Шаг 2. Применяя симплекс-метод, получаем решение 4-й задачи:

.

Так как полученное решение не является целочисленным, следует шаг 4.

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

6-я задача:

7-я задача:

Итак, в списке решаемых задач имеются 5-я, 6-я и 7-я задачи, а нижняя граница максимального значения функции цели .

Итерация 5.

Шаг 1. Из списка выбираем 5-ю задачу.

Шаг 2. Применяя симплекс-метод, получаем решение 5-й задачи:

.

Так как найденный план не является целочисленным, следует шаг 4.

Шаг 4. Выбираем дробную координату и получаем и . Применяя границы значений неизвестной 5-й задачи, получаем две новые задачи.

8-я задача:

9-я задача:

В списке решаемых задач имеются 6-я, 7-я, 8-я и 9-я задачи, а нижняя граница максимального значения функции цели .

Итерация 6.

Шаг 1. Из списка решаемых задач выбираем 6-ю задачу.

Шаг 2. Констатируем, что 6-я задача не имеет решения. Поэтому нижняя граница максимального значения функции цели и следует следующая итерация.

Итерация 7.

Шаг 1. Из списка решаемых задач выбираем 7-ю задачу.

Шаг 2. Применяя симплекс-метод, получаем решение 7-й задачи:

.

Шаг 3. Так как полученное решение является целочисленным, то нижняя граница максимального значения функции цели и далее следует итерация 8.

Итерация 8.

Шаг 1. Из списка решаемых задач выбираем 8-ю задачу.

Шаг 2. Применяя симплекс-метод, получаем решение 8-й задачи:

.

Нижняя граница максимального значения функции цели , далее - следующая итерация.

Итерация 9.

Шаг 1. В списке решаемых задач имеется лишь 9-я задача.

Шаг 2. Применяем симплекс-метод и получаем решение 9-й задачи:

.

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

Итерация 10.

Шаг 1. В списке решаемых задач нет ни одной задачи. Таким образом, решение данной задачи целочисленного программирования следующее:

.

Размещено на Allbest.ru

...