Методы и способы решения задач целочисленного параметрического программирования (стр. 14 из 15)
система не имеет решения.Следовательно, для
не существует оптимального целочисленного решения. Интервалами оптимальности целочисленных планов для различных значений параметра являются: 
- планы не существуют; 
- 
, 
. 
- 
, 
.2. Пример решения задачи целочисленного программирования с параметром в свободных членах системы ограничений
Пример 4.2.1 Для каждого значения
найти неотрицательное решение, минимизирующее линейную функцию 
при ограничениях 
, 
.Решение. Перейдем от неравенств к равенствам, добавляя к левым частям неравенств дополнительные переменные:
, .Возьмем
и найдем симплекс-методом оптимальный план.Таблица 4.3.1.
| БП | СЧ |  |  |  |  |  |  |
 | 1+t | 2 | -1 | 1 | 1 | 0 | 0 |
| | 2 | -4 | 2 | -1 | 0 | 1 | 0 |
| | 5 | 3 | 0 | 1 | 0 | 0 | 1 |
| С | 0 | -1 | 1 | 3 | 0 | 0 | 0 |
Таблица 4.3.2.
| БП | СЧ |  | | | | | |
| | 1+t | 2 | -1 | 1 | 1 | 0 | 0 |
| | 3+t | -2 | 1 | 0 | 1 | 1 | 0 |
| | 4-t | 1 | 1 | 0 | -1 | 0 | 1 |
| С | -3-3t | -7 | 4 | 0 | -3 | 0 | 0 |
Таблица 4.3.3.
| БП | СЧ |  | | | | | |
| | 4+2t | 0 | 0 | 1 | 2 | 1 | 0 |
| | 3+t | -2 | 1 | 0 | 1 | 1 | 0 |
| | 1-2t | 3 | 0 | 0 | -2 | -1 | 1 |
| С | -15-7t | 1 | 0 | 0 | -7 | -4 | 0 |
Таблица 4.3.4.
| БП | СЧ |  | | | | | |
| | 4+2t | 0 | 0 | 1 | 2 | 1 | 0 |
| | (11-t)/3 | 0 | 1 | 0 | -1/3 | 1/3 | 2/3 |
| | (1-2t)/3 | 1 | 0 | 0 | -2/3 | -1/3 | 1/3 |
| С |  | 0 | 0 | 0 | -19/3 | -11/3 | -1/3 |
Решение
, 
оптимально и целочисленное при 
. Пусть 
. Тогда решение не является целочисленным. Составим дополнительное ограничение: 
, 
, 
, 
, 
.Дополнительное ограничение имеет вид:
, 
.Таблица 4.3.5.
| БП | СЧ | |  |  |  |  |  |  |
| | 4+2t | 0 | 0 | 1 | 2 | 1 | 0 | 0 |
| | (11-t)/3 | 0 | 1 | 0 | -1/3 | 1/3 | 2/3 | 0 |
| | (1-2t)/3 | 1 | 0 | 0 | -2/3 | -1/3 | 1/3 | 0 |
| | -2/3 | 0 | 0 | 0 | -2/3 | -1/3 | -2/3 | 1 |
| С | | 0 | 0 | 0 | -19/3 | -11/3 | -1/3 | 0 |
Применим двойственный симплекс-метод. Получим: