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

 

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

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

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

1.Оно должно быть линейным;

2.Должно отсекать найденный оптимальный не целочисленный план;

3.Не должно отсекать ни одного целочисленного плана.

Алгоритм графического решения задачи целочисленного программирования.

1.Построить систему координат x₁0х₂ и выбрать масштаб.

2.Найти область допустимых решений (ОДР) системы ограничений задачи.

3.Построить целевую функцию, являющуюся линией уровня и на ней указать направление нормали.

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

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

5.Найти координаты, точки экстремума и значение целевой функции в ней. Если полученные значения не целочисленные, то перейти к следующему шагу.

6.Выделить у этих координат область с целочисленными значениями.

7.Определить новые координаты и построить граф.

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

Пример решения задачи целочисленного программирования.