При наличии в задаче линейного программирования двух переменных, а в системе ограничения – неравенств, она может быть решена графическим методом без требований целочисленных переменных.
Если оптимальное решение этой задачи является целочисленным, то оно и является оптимальным для исходной задачи.
Если же полученное оптимальное решение не целочисленное, то строится дополнительное линейное ограничение. Оно обладает следующими свойствами:
1) Оно должно быть линейным;
2) Должно отсекать найденный оптимальный не целочисленный план;
3) Не должно отсекать ни одного целочисленного плана.
Алгоритм графического решения задачи целочисленного программирования.
1. Построить систему координат x10х2 и выбрать масштаб.
2. Найти область допустимых решений (ОДР) системы ограничений задачи.
3. Построить целевую функцию, являющуюся линией уровня и на ней указать направление нормали.
4. Переместить линию целевой функции по направлению нормали через ОДР, чтобы она из секущей стала касательной к ОДР и проходила через наиболее удаленную от начала координат точку. Эта точка будет являться точкой экстремума, т.е. решением задачи.
|
|
Если окажется, что линия целевой функции параллельна одной из сторон ОДР, то в этом случае экстремум достигается во всех точках соответствующей стороны, а задача линейного программирования будет иметь бесчисленное множество решений.
5. Найти координаты, точки экстремума и значение целевой функции в ней. Если полученные значения не целочисленные, то перейти к следующему шагу.
6. Выделить у этих координат область с целочисленными значениями.
7. Определить новые координаты и построить граф.
8. Найти точки с целыми значениями искомых переменных, подставить в уравнение целевой функции и найти её значение. Максимальное из полученных значений целевой функции и будет решением задачи.