Метод перебора базисных решений

Лабораторная работа №6

Решение канонической задачи линейного программирования методом перебора

Цель работы и задачи работы

Закрепить теоретические сведения о методах решения канонической задачи линейного программирования. Освоить приемы их применения в среде MathCAD.

Теоретические сведения, необходимые для выполнения лабораторной работы

Каноническая и стандартная формы задачи линейного программирования

Задачей линейного программирования (ЗЛП) называются задачи, в векторно-матричном виде записываемые следующим образом:

(1)

Конструкция в выражении (1) означает, что на ее месте может стоять один из знаков , или =.

n – размерность вектора переменных задачи (число переменных x_i), m – число уравнений и/или неравенств ограничений.

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

Среди различных вариантов постановки ЗЛП выделяют две формы, отличающиеся способом задания ограничений:

1) каноническая (КЗЛП);

2) стандартная (СЗЛР).

В канонической форме все ограничения заданы в виде равенств, причем число равенств меньше размерности вектора переменных задачи.

В стандартной форме все ограничения заданы в виде неравенств, причем число неравенств больше размерности вектора переменных системы (m ³ n+1).

Указанные формы постановки ЗЛП приведены в таблице 2.1.

Таблица 2.1

Формы постановки ЗЛП

Каноническая	Стандартная

 

Любая форма постановки ЗЛП может быть сведена к указанным двум с помощью следующих преобразований:

1. если в условии задачи ЛП требуется определить максимум функции f(x), то это эквивалентно нахождению минимума -f(x).

2. В ограничениях типа неревенств возможна замена знака неравенства на противоположный, т.е. неравенство

эквивалентно неравенству

3. Ограничения в виде неравенства можно заменить ограничением в виде равенства. Пусть ограничение имеет вид:

 

a₁x₁ +a₂x₂ +...+a_nx_n £ b

 

Вводим дополнительную переменную x_n+1 ³ 0, тогда

 

a₁x₁ + a₂x₂ +...+ a_nx_n + x_n+1 = b

 

Если знак неравенства противоположный, т,е,

 

a₁x₁ +a₂x₂ +...+a_nx_n ³ b, то

a₁x₁ + a₂x₂ +...+ a_nx_n - x_n+1 = b

 

При этом, естественно, увеличивается размерность вектора x.

4. От ограничений в виде равенств можно перейти к ограничениям в виде неравенств следующим образом. Систему из m уравнений с n переменными (m<n) решить относительно m переменных, т.е. выразить эти переменные через остальные (n-m) переменных. Тогда с учетом того, что все они неотрицательны, получим m неравенств.

 

Методы решения КЗЛП

Определим основные термины, используемые при решении КЗЛП.

Точка, удовлетворяющая ограничениям задачи называется допустимым решением или планом.

Допустимое решение, при котором целевая функция f(x) приобретает минимальное значение называется оптимальнымрешением (оптимальнымпланом),

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

Оставшиеся (n-m) переменных называются свободными переменными.

Решение системы из m уравнений с m базисными переменными при условии равенства нулю свободных (n-m) переменных называется базиснымрешением.

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

В теории ЗЛП доказано, что решением ЗЛП является одно из базисных решений, поэтому для решения ЗЛП необходимо перебрать базисные решения задачи по какому-либо алгоритму.

Метод перебора базисных решений

В методе перебора определяются все базисные решения задачи. Для этого необходимо рассмотреть всевозможные случаи сочетания базисных (m штук) переменных. Количество перебираемых вариантов определяется по формуле:

(2)

Для определения базисного решения необходимо выбрать базисные переменные (m переменных), приравняв к нулю свободные, и решить полученную систему уравнений ограничений.

Перебрав все сочетания базисных переменных и, соответственно, определив все базисные решения, среди них выбираются допустимые базисные решения (с неотрицательными переменными).

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

Пример.

Решим методом перебора следующую КЗЛП:

В данной задаче размерность вектора переменных n=4, число уравнений m=2.

Методом перебора необходимо перебрать базисных решений.

Сочетания базисных переменных: x₁x₂, x₁x₃, x₁x₄, x₂x₃, x₂x₄, x₃x₄.

 

В таблице 2.2 представлены сочетания базисных переменных, системы уравнений и базисные решения

Таблица 2.2

К решению примера

№	Сочетание	Система уравнений	Базисное решение	Значение целевой функции
	x1x2			-
	x1x3			0.5
	x1x4			-
	x2x3			0.25
	x2x4			-
	x3x4

Жирным шрифтом выделены допустимые базисные решения.

Среди допустимых базисных решений минимальное значение целевая функция имеет для сочетания 6.

Таким образом, Оптимальное решение:

На рисунке 2.1 приведен фрагмент документа MathCAD, в котором решена рассмотренная задача. Как видно из рисунка методом перебора получено правильное решение.

Рисунок 2.1 ­– Решение примера в MathCAD