Переборный метод решения задачи линейного программирования
Теоретические основы переборного метода
Переборный метод решения основан на следующей основной теореме:
Если целевая функция имеет максимум (минимум), то он достигается в крайней точке (вершине) области допустимых решений.
Поэтому для поиска максимума или минимума целевой функции следует:
- перебрать все вершины многоугольника;
- для каждой вершины найти значение целевой функции;
- выбрать вершину, в которой достигается оптимальное значение.
Основной вопрос: как осуществить поиск вершин?
Для ответа на этот вопрос рассмотрим геометрическую интерпретацию ЗЛП.
Рассмотрим ЗЛП, имеющую ограничения в виде неравенств
a1,1x1+a1,2x2+…+a1,nxn ≥ b1,
a2,1x1+a2,2x2+…+a2,nxn ≥ b2,
. . . . . . . . . . . . . . . . . . . . . . .,
am,1x1+am,2x2+…+am,nxn ≥bm,
Дадим геометрическую интерпретацию для задач размерности 2, 3. Сделаем выводы для произвольной задачи.
Размерность задачи (N) |
||
N = 2 |
N = 3 |
N > 3 |
Ограничение, взятое со знаком равно |
||
a1,1x1+a1,2x2 = b1, прямая |
a1,1x1+a1,2x2+a1,3x3 = b1 плоскость |
a1,1x1+a1,2x2+…+a1,nxn = b1 гиперпространство |
Ограничение |
||
a1,1x1+a1,2x2 ≥ b1, полуплоскость |
a1,1x1+a1,2x2+a1,3x3 ≥ b1 полупространство |
a1,1x1+a1,2x2+…+a1,nxn ≥ b1 полугиперпространство |
Область допустимых решений |
||
Многоугольник |
Многогранник |
Гипермногогранник |
Вершина образуется в результате пересечения… |
||
двух прямых |
трех плоскостей |
N гиперплоскостей |
Вывод: для того, чтобы получить вершину области допустимых решений, нужно:
- 1) из системы ограничений взять N ограничений (где N – количество неизвестных);
- 2) записать их со знаком равно, составить систему линейных уравнений ;
- 3) решить систему;
- 4) проверить, является ли полученная точка вершиной (!!!). Для этого нужно подставить ее во все ограничения системы. Если она удовлетворяет всем ограничениям – это вершина.
Чтобы получить все вершины, нужно выполнить пункт 1 всеми возможными способами. Если M – число ограничений, N – число неизвестных, то число способов равно
Пример
Решить ЗЛП переборным методом:
Решение:
M = 5 – число ограничений, N = 3 – число неизвестных.
Для нахождения вершин будем выбирать по 3 ограничения. Это можно сделать способами.
Каждый вариант будем кодировать последовательностью из 1 и 0 (1 – ограничение взяли, 0 – ограничение не взяли). Длина последовательности равна 5, количество единиц – 3.
Задание 3 (домашнее)
Написать программу, реализующую переборный метод решения ЗЛП.
Входной файл:
N (количество переменных)
M (общее количество ограничений)
<коэффициенты ограничений, знак ограничений >= >
Вывести:
координаты всех вершин многогранника допустимых решений;
значение целевой функции для каждой вершины;
максимум целевой функции и вершину, в которой он достигается.
Алгоритм (возможный вариант):
Для перебора вершин будем составлять всевозможные двоичные слова длины М и выбирать те, в которых ровно N единиц
I:=0;
Повторять
Перевести I в двоичную систему (записать в массив)
Если количество единиц в нем равно N, то
Составить систему, выбрав в нее ограничения, соответствующие единицам
Решить ее методом Гаусса с выбором главного элемента
Если решение есть, то
Проверить, удовлетворяет ли оно всем ограничениям
Если да, то это решение – вершина, найти для нее значение цел. ф-ии
Увеличить I
Выйти, когда I=2M
Замечание: в программе проверку условия A≥B осуществлять в виде (A>B) или │A-B│<1.0e-10 (подумать, для чего?)