14) Линейное программирование. Математическая формулировка задачи оптимального размещения элементов на печатной плате

Основной (стандартной) задачей линейного программирования называется задача нахождения минимума линейной целевой функции (линейной формы) вида:

при условиях

,

.

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

,

Основную задачу можно свести к канонической путём введения дополнительных переменных.

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

Легко заметить, что задачу нахождения максимума можно заменить задачей нахождения минимума, взяв коэффициенты С с обратным знаком.

15) Математическая формулировка и особенности симплекс метода (геометрическая интерпретация).

  Подготовительный этап Рассмотрим примеры основных вариантов решения задачи линейного прогрммирования в графической интерпретации: 1) Графическое решение есть (единственное) Y=12x₁+15x₂→max 4x₁+3x₂ ≤12 2x₁+5x₂ ≤10 x₁≥0, x₂≥0 Любые допустимые решения задачи находятся внутри 0, A, В, С - эти вершины, называемые экстремальными, крайними точками множества. При этом точки А, В, С являются допустимыми экстремальными точками а точка D - недопустимым экстремальным решением. 1) 12x₁+15x₂0 x₁=-(5/4)x₂ 2) 12x₁+15x₂1 x₁=y/12-(5/4)x₂ 3) 12x₁+15x₂15 *) x₂=0,5 x₁=0,625 *)x₂=0 x₁=1,25 4) 12x₁+15x₂30 *) x₂=1 x₁=1,25 *)x₂=0 x₁=2,5 Решение точка B x₂=8/7 x₁=15/7 Y=300/7 При использовании симплекс метода найдя первую экстремальную точку на следующем шаге будем всегда попадать в смежную экстремальную точку, фактически при решений задачи при помощи СМ последовательность решений получатся двигаясь вдоль границ пространства решений, причем данные ребра определяются как линии, соединяющие 2 смежные экстремальные точки. 2) Задача не имеет решений сиситема ограничений противоречива Y=x₁+x₂→max -x₁+x₂ ≤-1 x₁-x₂ ≤-1 x₁≥0, x₂≥0 Для данной задачи решение не существует поскольку област допустимых значений отсутствует.

Таким образом Геометрическая интерпретация метода состоит в последовательном движении по вершинам симплекса.

16) Математическая формулировка и особенности табличного симплекс метода.

Приводим задачу к каноническому виду:

F=a_0,1x₁+a_0,2x₂+...a_0,nx_n +b₀ → max

a_1,1x₁+a_1,2x₂+...a_1,nx_n+x_n+1=b₁

.......................................

a_m,1x₁+a_m,2x₂+...a_m,nx_n+x_n+m=b_m

В случае если в исходной задаче необходимо найти минимум - знаки коэффициентов целевой функции F меняются на противоположные a_0,n=-a_0,n.

Шаг 0. Составляем симплексную таблицу, соответствующую исходной задаче

	x1	x2	...	xn-1	xn	b
F	-a0,1	-a0,2	...	-a0,n-1	-a0,n	-b0
xn+1	a1,1	a1,2	...	a1,n-1	a1,n	b1
xn+2	a2,1	a2,2	...	a2,n-1	a2,n	b2
...	...	...	...	...	...	...
xn+m	am,1	am,2	...	am,n-1	am,n	bm

Шаг 1. Проверка на допустимость.

Проверяем на положительность элементы столбца b (свободные члены), если среди них нет отрицательных то найдено допустимое решение. Если в столбце свободных членов имеются отрицательные элементы то выбираем среди них максимальный по модулю - он задает ведущую строку k. В этой строке так же находим максимальный по модулю отрицательный элемент a_k,l - он задает ведущий столбец - l и является ведущим элементом. Переменная, соответствующая ведущей строке исключается из базиса, переменная соответствующая ведущему столбцу включается в базис.

Если же среди свободных членов есть отрицательные элементы - а в соответствующей строке - нет решений нет.

Шаг 2. Проверка на оптимальность.

Выбираем среди отрицательных элементов строки F максимальный по модулю 4

a_0,l=min{a_0,i }

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

b_k/a_k,l =min {b_i/a_i,l } при a_i,l>0, b_i>0

k - cтрока, для которой это отношение минимально - ведущая. Элемент a_k,l - ведущий (разрешающий). Переменная, соответствующая ведущей строке (x_k) исключается из базиса, переменная соответствующая ведущему столбцу (x_l) включается в базис.

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

Если в строке F и в столбце свободных членов все элементы положительные, то найдено оптимальное решение.

Правила преобразований симплексной таблицы.

 При составлении новой симплекс-таблицы в ней происходят следующие изменения: 

• Вместо базисной переменной x_k записываем x_l; вместо небазисной переменной x_l записываем x_k.  

• ведущий элемент заменяется на обратную величину a_k,l'= 1/a_k,l

• все элементы ведущего столбца (кроме a_k,l) умножаются на -1/a_k,l

• все элементы ведущей строки (кроме a_k,l) умножаются на 1/a_k,l

• оставшиеся элементы симплекс-таблицы преобразуются по формуле a_i,j'= a_i,j- a_i,lx a_k,j/ a_k,l