Математические методы

План, который обращает в равенство хотя бы n независимых ограничений задачи, называется опорным планом. Опорный план соответствует некоторой вершине многогранника планов.

Опорный план содержит не свыше m положительных компонент (m - число независимых ограничений задачи). Опорный план, содержащий менее m положительных компонент, называют вырожденным.

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

Система m векторов Aj при положительных компонентах опорного плана называется базисом этого плана. Симплекс- метод - это метод упорядоченного перебора опорных планов. Упорядоченность в данном случае обеспечивается последовательным перебором опорных планов с монотонным изменением значения целевой функции в сторону возрастания (убывания).

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

Предположим, что исходная задача приведена к канонической форме (1.1)-(1.3) при В 0 и первые m векторов начального базиса образуют единичную матрицу (их можно принять за базис).

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

В первом столбце таблицы (С баз) записывают коэффициенты целевой функции (С1, С2 …Сm) при базисных переменных (напомним, что в базис входят только векторы, образующую единичную подматрицу, как в нашем случае А1 / Аm). Во втором столбце (Базис плана) должны находиться базисные векторы данного опорного плана, а в третьем столбце (План Х) - правая часть ограничений задачи (базисные компоненты плана). Таким образом, перемножая элементы первого столбца таблицы со столбцом - "План Х", и суммируя эти произведения, мы получаем значение целевой функции (ячейка - L(X)=С1*В1 + С2*В2+…+ +Сm*Bm).

Первая строка симплексной таблицы содержит коэффициенты линейной функции нашей задачи и остается неизменной на протяжении всего решения (С1, С2, …, Сn).

В центральной части таблицы записывают коэффициенты при неизвестных в ограничениях исходной задачи (Z11,…, Z1n,…, Zm1,…, Zmn). При этом следует заметить, что коэффициенты при базисных переменных в ограничениях задачи составляют единичную подматрицу. 
Строку Zk рассчитывают по формуле 

 
  
 

Известно, что при переходе к новому опорному плану X(Θ), в котором k-я компонента равна Θ>0 (станет базисной), значение целевой функции изменится и будет равно 
 

Выводы относительно данного опорного плана делают на основании содержимого последней строки таблицы по следующим критериям.  
Критерий 1 (критерий оптимальности). Если все Δk >= 0 , то выбранный план для задачи максимизации является оптимальным (для задачи на минимум признак оптимальности - неположительность всех Δk ).

Критерий 2 . Если обнаруживается некоторое Δk < 0 (для задачи минимизации Δk>0) и хотя бы одно из значений Zjk >0, то переход к новому опорному плану увеличит (уменьшит) значение целевой функции. При этом в базис будет вводиться новый вектор, выбор которого определяется по критерию максимального по модулю произведения Θ*Δk. Ес-ли к тому же учесть, что число положительных (базисных) компонент опорного плана должно оставаться равным m, то одну из m базисных компонент исходного плана обращаем в нуль выбором 

 
где Xjo- компоненты опорного плана; 
Zjk- коэффициенты при k-й переменной в ограничениях задачи.

Критерий 3 . Если обнаруживается некоторое Δk < 0, но все Zjk<=0, то линейная форма задачи не ограничена по максимуму (неограничен-ность по минимуму устанавливается аналогично при Δk>0 и всех Zjk <=0).

Переход к очередной симплексной таблице сводится к тому, чтобы выразить Xk из уравнения, соответствующего минимуму для Θ, и исключить из остальных уравнений (в итоге получаем единичный вектор при новой базисной компоненте и тем самым сохраняется единичная подматрица при базисных векторах):

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

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

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

2.3.1 Каноническая форма  решения задач 

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

 Правило приведения задачи линейного программирования к каноническому виду состоит в следующем:

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

если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1;

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

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

2.4 Алгоритм метода оптимизации

Оптимизация - целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.

Поиски оптимальных решений привели к созданию специальных математических методов и уже в 18 веке были заложены математические основы оптимизации (вариационное исчисление, численные методы и др.). Однако до второй половины 20 века методы оптимизации во многих областях науки и техники применялись очень редко, поскольку практическое использование математических методов оптимизации требовало огромной вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев - невозможно.

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

• количество продукции - расход сырья
• количество продукции - качество продукции

Обычно оптимизируемая величина связана с экономичностью работы рассматриваемого объекта (аппарат, цех, завод). Оптимизируемый вариант работы объекта должен оцениваться какой-то количественной мерой -критерием оптимальности.

Критерием оптимальности называется количественная оценка оптимизируемого качества объекта.

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

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

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

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

Задачами линейного программирования называются задачи, в которых линейны как целевая функция, так и ограничения в виде равенств и неравенств.

Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:

рационального использования сырья и материалов; задачи оптимизации раскроя;

оптимизации производственной программы предприятий;

оптимального размещения и концентрации производства;

составления оптимального плана перевозок, работы транспорта;

управления производственными запасами;

и многие другие, принадлежащие сфере оптимального планирования. 
3 РЕШЕНИЕ ЗАДАЧИ

Строим симплексную таблицу используя каноническую форму задачи

Таблица 1. Шаг I

1. Проверка критерия  оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение  новой базисной переменной.

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

3. Определение  новой свободной переменной.

Вычислим значения Di по строкам как частное от деления: bi / ai1

и из них выберем наименьшее:

min (2400 : 40 , 2400 : 20 , 2400 : 10 ) = 60

	Сi	Xi	Bj	4	3	0	0	0
				х1	х2	х3	х4	х5
I	0	Х3	2400	40	20	1	0	0	60
	0	Х4	2400	20	30	0	1	0	120
	0	Х5	2400	10	30	0	0	1	240
		f	0	-4	-3	0	0	0

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (40) и находится на пересечении ведущего столбца и ведущей строки.

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x3 в план 1 войдет переменная x1.

Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x3 плана 0 на разрешающий элемент РЭ=40

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x1 плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x1 и столбец x1.

Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.

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

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (40), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Получаем симплекс таблицу:

Базис	B	x1	x2	x3	x4	x5
x1	60	1	1/2	1/40	0	0
x4	1200	0	20	-1/2	1	0
x5	1800	0	25	-1/4	0	1
F(X1)	240	0	-1	1/10	0	0

 

Таблица 2. Шаг II

1. Проверка критерия  оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение  новой базисной переменной.

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