Реализация метода Искусственного Базиса

свободными, их обозначают СП. Не ограничивая общности, будем  считать, что базис составляют первые m векторов . Этому базису соответствуют базисные переменные , а свободными будут переменные .

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

Теорема.

Если система векторов содержит m линейно независимых векторов , то допустимый план       

является крайней точкой многогранника планов.

Теорема.

Если ЗЛП имеет решение, то целевая функция достигает экстремального

значения, хотя бы в одной из крайних точек многогранника решений.

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

 

 

 

 

1.2 Форма задачи линейного  программирования и свойства  ее решений.

В зависимости  от вида ограничений различают следующие  формы задач:

• Каноническая
• Симметричная
• Общая

 

Задача в  канонической форме – задача ЛП, в которой все ограничения есть равенства (p = q = 0) и все переменные неотрицательные (r = n).

Общий метод решения  задачи ЛП разработан именно для задачи в каноническом виде.

Матричный вид задачи в канонической форме:

( ) = ( * ) →

=

=   – вектор коэффициентов критерия

= -  вектор переменных

 

 

= – матрица условий (технологических коэффициентов)

= ( )

=  – вектор условий

=    – вектор ограничений

 

( ) = ( * )

+ + …+ =

,

 

Для неё разработан метод  решения, который называется симплексным.

Задача в  симметричной форме – задача ЛП, в которой все ограничения есть неравенства (p = q = m) и все переменные неотрицательные (r = n).

Матричный вид задачи в симметричной форме:

 

 

 

Симметричная форма допускает  графическое решение (иллюстрацию).

Задача в общей (смешанной) форме – задача ЛП, в которой присутствуют все виды ограничений и не все переменные неотрицательные.

Приведение задачи линейного программирования от одной  
эквивалентной формы к другой.

 

Сведение задачи минимизации  к задаче максимизации:

Преобразование сводится к смене  знака критерия (Рисунок 1).

( ) ~ ( ( ))

 

( ) = ( ( ))

 

Рисунок 1

 

Переход от ограничений-неравенств к уравнению:

 

+ =

Переменные  - дополнительные или балансовые, так как обеспечивают баланс правой и левой частей.

 

 

 

 

- =

 

Переход от переменных произвольного  знака к неотрицательным переменным:

= -

Переход от переменных, ограниченных снизу, к неотрицательным:

= +

Переход от уравнений  к неравенствам:

Если имеется уравнение:

то оно заменяется на два неравенства:

 

Пусть есть несколько  ограничений:

 

А также:

Пусть ранг (количество линейно-независимых  уравнений) системы ограничений  равен  , тогда переменных можно выразить через остальные:

 

Под решением систем уравнений понимается зависимость одних переменных через  другие. Эта зависимость (27) называется общим решением, независимые переменные – свободными (их можно произвольно менять), а – базисными переменными.

Задавая произвольные значения свободным переменным, получаем частные решения, но не все они удовлетворяют условиям неотрицательности:

Тогда для свободных переменных получаем ограничения в виде неравенств:

 

 

Если ( ) = 2, то задача допускает иллюстрацию в пространстве двух переменных.

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

 

Примеры решения задач

Каноническая форма

 

 

 

 

Симметричная форма

 

1.3 Переход к канонической форме

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

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

 

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

Определение.

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

Утверждение. 

Любая общая задача ЛП может быть приведена к канонической форме.  
Приведение общей задачи ЛП к канонической форме достигается путем введения новых (их называют дополнительными) переменных. Система ограничений этой задачи состоит из четырех неравенств. Введя дополнительные переменные y₁≥  0, y₂ ≥  0, y₃ ≥  0, y₄ ≥  0, можно перейти к системе ограничений:

 

 

Эти дополнительные переменные y _i имеют абсолютно ясный экономический смысл, а именно означают величину неиспользованного времени работы (простоя машины i-го вида).  
Например, если бы машины первого вида работали все 18 ч, то x + y = 18,

следовательно, y₁ = 0. Но мы допускаем возможность неполного использования времени работы первой машины x + y<18. В этом случаеy₁ приобретает положительное значение и может рассматриваться как неиспользованный лимит времени. Например, зная решение этой задачи из пункта 3.3.2, x =  12, y  =  6, мы можем из системы ограничений (3.9) сделать вывод, что y₁  =  y₂  =  y₃  =  0, а y₄  =  12 – 6  =  6. Т. е. машины первого, второго, третьего вида используют свое рабочее время полностью. А вот четвертая машина загружена лишь наполовину, 6 часов, и при заданном оптимальном плане простаивает. Возможно, после таких выводов руководителю предприятия захочется загрузить ее другой работой,            сдать в аренду на это время и т.д.  
Итак, введением дополнительных переменных мы можем любое ограничение типа неравенства привести к уравнению.

Рассмотрим задачу о  смеси. Система ограничений имеет  вид:

Неравенства были обращены в сторону «больше», поэтому вводя  дополнительные переменные y₁, y₂, y₃ ≥ 0, их необходимо вычесть из левой части, чтобы уравнять ее с правой. Получим систему ограничений в канонической форме:

Переменные y_i также будут иметь экономический смысл. Если вы вспомните практическое содержание задачи, то переменная y₁ будет означать количество излишнего вещества А в смеси, y₂ –количество излишков вещества В в смеси, y₃ – излишки С в смеси.  
Задача нахождения максимального значения целевой функции может быть сведена к нахождению минимума для функции –F ввиду очевидности утверждения maxF = –min (–F ). Посмотрите на рисунок 3.9: если в какой-то точке x= x₀ функция y= F(x) достигает своего максимума, то функция y= –F(x), симметричная ей относительно оси OX, в этой же точке x₀ достигнет минимума, причем F_max = – (–F_min) при x =  x₀.

Вывод. Для представления задачи ЛП в канонической форме необходимо:

• неравенства, входящие в систему ограничений задачи, преобразовать в уравнения с помощью введения дополнительных переменных;
• если целевая функция F →max (максимизируется), она заменяется на функцию –F→ min (которая минимизируется).

 

Рисунок 2

1.4 Табличный симплекс-метод

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

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_2,1x₁+a_2,2x₂+...a_2,nx_n +x_n+2 =b₂

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

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

Исходная таблица для  задачи имеет следующий вид(Таблица 1):

                                                                                                     Таблица 1

	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

x₁, x₂, x_n - исходные переменные, x_n+1, x_n+2, x_n+m - дополнительные переменные. Все дополнительные переменные мы приняли как базисные, а

исходные переменные как небазисные(дополнительные записаны в первый столбец симплекс-таблицы а исходные в первую строку).

При каждой итерации элементы симплекс-таблицы  пересчитывают по определенным правилам.

Алгоритм  симплекс-метода.

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

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₁