Учись Учиться

 

Переборный метод решения задачи линейного программирования

Теоретические основы переборного метода

Переборный метод решения основан на следующей основной теореме:

Поэтому для поиска максимума или минимума целевой функции следует:

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

Основной вопрос: как осуществить поиск вершин?

Для ответа на этот вопрос рассмотрим геометрическую интерпретацию ЗЛП.

Рассмотрим ЗЛП, имеющую ограничения в виде неравенств

a_1,1x₁+a_1,2x₂+…+a_1,nx_n ≥ b₁,

a_2,1x₁+a_2,2x₂+…+a_2,nx_n ≥ b₂,

. . . . . . . . . . . . . . . . . . . . . . .,

a_m,1x₁+a_m,2x₂+…+a_m,nx_n ≥b_m,

Дадим геометрическую интерпретацию для задач размерности 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. 1) из системы ограничений взять N ограничений (где N – количество неизвестных);

1. 2) записать их со знаком равно, составить систему линейных уравненийаписать их со знаком равно, составить систему линейных уравнений ()нужно из системы ограничений взять ;

1. 3) решить систему;

1. 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=2^M

Замечание: в программе проверку условия A≥B осуществлять в виде (A>B) или │A-B│<1.0e-10 (подумать, для чего?)