Методы и способы решения задач целочисленного параметрического программирования (стр. 7 из 15)

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

Пример 3.3.1. Для всех значений параметра найти максимальное значение функции

Решение. Пусть

. Находим симплекс-методом решение задачи.

Таблица 3.3.1.

БП	СЧ
		1	-1	1	0
		-1	2	0	1
С				0	0

Таблица 3.3.2.

БП	СЧ
		1/2	0	1	1/2
		-1/2	1	0	1/2
С			0	0

План

оптимален при условии

а среди компонент вектора

нет отрицательных чисел:

Следовательно, при

, ,

Если

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

Таблица 3.3.3.

БП	СЧ
		0	1	1	1
		1	-2	0	-1
С		0		0

Вектор

оптимален при условии

то есть при

.

Если

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

Мы рассмотрели интервал

. Пусть , тогда переходим к новому оптимальному плану:

Таблица 3.3.4.

БП	СЧ
		0	1	1	1
		1	0	2	1
С		0	0

Таким образом, при

, , .

4. Целочисленное параметрическое программирование

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

4.1 Пример решения задачи целочисленного программирования с параметром в целевой функции

Пример 4.1.1. Для каждого значения

найти неотрицательное решение, минимизирующее линейную функцию при ограничениях