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

Задачи линейного программирования

 

 

Общие сведения

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

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

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

Во многих случаях реализация процесса управления требует затраты каких-либо ресурсов: затрат времени, расхода материалов, топлива, электроэнергии. Следовательно, при выборе способа управления следует говорить не только о том, достигается ли поставленная цель, но и том, какие ресурсы придется затратить для достижения этой цели. В этом случае задача управления состоит в том, чтобы из множества решений, обеспечивающих достижение цели, выбрать одно, которое требует наименьшей затраты ресурсов.

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

Математическое выражение, дающее количественную оценку степени выполнения наложенных на способ управления требований, называется, критерием качества управления.

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

Различные виды задач оптимального управления отличаются друг от друга способом и последовательностью выполнения этих операций.

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

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

Поэтому методы математического программирования эффективны лишь при использовании ЭВМ.

Задача линейного программирования является простейшим случаем задачи математического программирования. Метод решения таких задач разработал советский математик Канторович, за что он получил Нобелевскую премию.

Задача линейного программирования состоит в следующем.

Дана система m линейно независимых уравнений с n неизвестными x₁, x₂,…, x_n, называемая системой ограничений задачи линейного программирования:

 

a11x1+…a1nxn=b1 ……………………………….. am1x1+…amnxn=bm

(1)

 

где, не уменьшая общности, можно считать b _i ≥ 0, i =1… m.

Характерной особенностью данной задачи является то, что число уравнений меньше числа неизвестных, т.е. m < n. Требуется найти неотрицательные значения переменных (x _i ≥ 0, i =1… n), которые удовлетворяют уравнениям (1) и обращают в минимум (максимум) критерий оптимальности, который в данном случае называют целевой функцией:

q=c₁x₁ +….+ c_nx_n. (2)

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

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

(задача с искусственным базисом, обыкновенные дроби)

 

Задача.

Найти значения переменных x₁,...,x₂, при которых функция:

Q =

x1

+

x2

принимает минимальное значение, при условии следующих ограничений:

		x1	+		x2	≥				(1)
		x1	+		x2	≥				(2)
		x1				≥				(3)
					x2	≥				(4)

x₁, x₂ ≥ 0

Шаг:1

Избавимся от неравенств в ограничениях, введя в ограничения 1, 2, 3, 4 неотрицательные балансовые переменные s₁, s₂, s₃, s₄.

x1

+

x2

–

s1

=

(1)

x1

+

x2

–

s2

=

(2)

x1

–

s3

=

(3)

x2

–

s4

=

(4)

x₁, x₂, s₁, s₂, s₃, s₄ ≥ 0

Шаг:2

Ищем в системе ограничений базисные переменные. Базисные переменные в исходной задаче отсутствуют, это значит, что исходная задача не содержит в себе допустимого базисного решения. Для его нахождения вначале составим и решим вспомогательную задачу. Введем по одной искусственной неотрицательной переменной r_i в каждое уравнение системы ограничений. Получим следующую систему ограничений,

x1

+

x2

–

s1

+

r1

=

(1)

x1

+

x2

–

s2

+

r2

=

(2)

x1

–

s3

+

r3

=

(3)

x2

–

s4

+

r4

=

(4)

x₁, x₂, s₁, s₂, s₃, s₄, r₁, r₂, r₃, r₄ ≥ 0

с базисными переменными r₁,r₂,r₃,r₄.

Целью решения вспомогательной задачи является получение допустимого базисного решения не содержащего искусственных переменных (r₁,r₂,r₃,r₄). Для этого сформируем вспомогательную целевую функцию:

G =r₁+r₂+r₃+r₄

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

Для решения вспомогательной задачи симплекс- методом выразим функцию G через свободные переменные, для этого:

- вычтем из функции G уравнение 1

- вычтем из функции G уравнение 2

- вычтем из функции G уравнение 3

- вычтем из функции G уравнение 4

Функция G примет вид:

G =

–

x1

–

x2

+

s1

+

s2

+

s3

+

s4

+

Теперь мы можем сформировать начальную симплекс-таблицу.
Шаг:3

Начальная симплекс-таблица

БП

x1

x2

s1

s2

s3

s4

r1

r2

r3

r4

Решение

Отношение

r1

–1

/   =

r2

–1

/   =

r3

–1

–

r4

–1

/   =

Q

–

G

–9

–36

–108

–

 

 

Итерация 1

БП	x1	x2	s1	s2	s3	s4	r2	r3	r4	Решение	Отношение
x2			–1								/ =
r2				–1							/   =
r3					–1						/   =
r4	–3					–1					–
Q										–50	–
G	–3		–2							–48	–

 

 

Итерация 2

БП	x1	x2	s1	s2	s3	s4	r2	r4	Решение	Отношение
x2			–1							–
r2				–1						/ =
x1					–1					–
r4					–1	–1				/ =
Q									–584	–
G			–2						–34	–

 

Итерация 3

БП	x1	x2	s1	s2	s3	s4	r4	Решение	Отношение
x2				–1					–
s1				–2					–
x1					–1				–
r4					–4	–1			/   =
Q								–704	–
G				–3				–2	–

 

 

Итерация 3-a

БП	x1	x2	s1	s2	s3	s4	Решение	Отношение
x2						–1		–
s1					–2	–2		–
x1					–1			–
s2					–4	–1		–
Q							–238	–
G								–

Получено оптимальное решение вспомогательной задачи (найден минимум функции G т.к. в строке целевой функции нет отрицательных коэффициентов). Все искусственные переменные вышли из базиса и поэтому мы можем приступить к решению исходной задачи, приняв полученное базисное решение в качестве опорного. Строка "G" нам больше не нужна, принятие решения о направляющем столбце, во всех последующих итерациях, будем принимать по строке "Q"

 

Итерация 4

БП	x1	x2	s1	s2	s3	s4	Решение	Отношение
x2						–1		–
s1					–2	–2		–
x1					–1			–
s2					–4	–1		–
Q							–238	–

Достигнуто оптимальное решение, т.к. в строке целевой функции нет отрицательных коэффициентов.

Ответ: Оптимальное значение функции

Q(x)=

достигается в точке с координатами:

x1=
x2=
s1=
s2=
s3=
s4=