Методы и способы решения задач целочисленного параметрического программирования (стр. 8 из 15)
. Решение. I способ. Перейдем от неравенств к равенствам, добавляя к левым частям неравенств дополнительные переменные:
Возьмем
(число 0 выбрано произвольно) и найдем симплекс-методом оптимальный план.Таблица 4.1.1.
| БП | СЧ |  |  |  |  |  |  |
 | 1 | 2 | -1 | 1 | 1 | 0 | 0 |
 | 2 | -4 | 2 | -1 | 0 | 1 | 0 |
 | 5 | 3 | 0 | 1 | 0 | 0 | 1 |
| С | 0 |  +1 | 1 | 3+4  | 0 | 0 | 0 |
Таблица 4.1.2.
| БП | СЧ |  |  |  |  | |  |
| | 1 | 2 | -1 | 1 | 1 | 0 | 0 |
| | 3 | -2 | 1 | 0 | 1 | 1 | 0 |
| | 4 | 1 | 1 | 0 | -1 | 0 | 1 |
| С | -3  |  |  | 0 | -3 | 0 | 0 |
Таблица 4.1.3.
| БП | СЧ |  | | |  | |  |
| | 4 | 0 | 0 | 1 | 2 | 1 | 0 |
| | 3 | -2 | 1 | 0 | 1 | 1 | 0 |
| | 1 | 3 | 0 | 0 | -2 | -1 | 1 |
| С | -15  |  | 0 | 0 |  |  | 0 |
Таблица 4.1.4.
| БП | СЧ |  | |  | |  | |
 | 4 | 0 | 0 | 1 | 2 | 1 | 0 |
| | 11/3 | 0 | 1 | 0 | -1/3 | 1/3 | 2/3 |
| | 1/3 | 1 | 0 | 0 | -2/3 | -1/3 | 1/3 |
| С |  | 0 | 0 | 0 |  |  |  |
Определим значения параметра t, при которых план, соответствующий таблице 4.1.4 останется оптимальным:
.Следовательно, при
задача имеет оптимальное решение: 
, 
. Оно не является целочисленным: 
- дробные. Составим дополнительное ограничение для переменной . Имеем: 
, 
, 
, 
, 
. 
, 
.Таблица 4.1.5.
| БП | СЧ | | | | | | |  |
| | 4 | 0 | 0 | 1 | 2 | 1 | 0 | 0 |
| | 11/3 | 0 | 1 | 0 | -1/3 | 1/3 | 2/3 | 0 |
| | 1/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 |  |  |  | 0 |
Применим двойственный симплекс-метод. Получим:
Таблица 4.1.6.
| БП | СЧ | |  |  | |  |  |  |
| | 4 | 0 | 0 | 1 | 2 | 1 | 0 | 0 |
| | 3 | 0 | 1 | 0 | -1 | 0 | 0 | 1 |
| | 0 | 1 | 0 | 0 | -1 | -1/2 | 0 | 1/2 |
 | 1 | 0 | 0 | 0 | 1 | 1/2 | 1 | -3/2 |
| С |  | 0 | 0 | 0 |  |  | 0 |  |
Получили целочисленное решение. Рассмотрим, при всех ли
