Построение линейно-регрессионной модели экономического процесса (стр. 5 )

Одним из методов решения задач линейного программирования является метод последовательного уточнения оценок (симплекс метод).

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

(1)

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

. (2)

Разрешим эту систему относительно переменных :

. (3)

Векторы условий, соответствующие , образуют базис. Переменные - базисными переменными. Остальные переменные задачи – небазисные. Целевую функцию можно выразить через небазисные переменные:

(4)

Если приравнять небазисные переменные нулю, то соответствующие базисные переменные примут значения . Вектор с такими компонентами представляет собой угловую точку многогранника решений (допустимую) при условии, что (опорный план). Теперь необходимо перейти к другой угловой точке с меньшим значением целевой функции. Для этого следует выбрать некоторую небазисную переменную и некоторую базисную так, чтобы после того, как мы “поменяем их местами”, значение целевой функции уменьшилось. Такой направленный перебор, в конце концов приведет нас к решению задачи.

Пример

Математическая постановка задачи имеет вид (а)

(а) (б)

Выберем в качестве базисных следующие переменные и разрешим систему относительно этих переменных. Система примет вид (б).

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

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

.

Соответствующий опорный план и .

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

.

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

Рассмотрим формализованный алгоритм симплекс метода, который состоит из двух основных этапов: построение опорного плана и построение оптимального плана. Проиллюстрируем алгоритм на рассмотренном ранее примере:

.

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

			1
=	1	-2	1
=	-2	1	2
=	3	1	3
=	-1	1	0

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

Выбор разрешающего элемента:

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

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

– разрешающий (направляющий) элемент, строка – разрешающая.

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

Модифицированное жорданово исключение:

1.  На месте разрешающего элемента ставится «1».

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

3.  Остальные элементы разрешающей строки делятся на разрешающий элемент.

4.  Все остальные элементы симплексной таблицы вычисляются по следующей формуле:

.

			1		Разрешающий элемент, который соответствует замене базисной переменной на небазисную переменную .
	1	-2	1
	-2	1	2
	3	1	3
	-1	1	0

			1		Разрешающий элемент, который соответствует замене базисной переменной на небазисную переменную .
	-3	2	5
	-2	1	2
	5	-1	1
	1	-1	-2

			1		Все коэффициенты в строке целевой функции отрицательны, т. е. мы нашли оптимальное решение.
	3/5	7/5	28/5
	2/5	3/5	12/5
	1/5	-1/5	1/5
	-1/5	-4/5	-11/5

Задачи для контроля и самопроверки

а) Общие приложения симплекс метода к экономическим исследованиям

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

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

Вариант №1

	Тов.1	Тов.2	Тов.3	Тов.4	Тов.5	Тов.6	Лимит на транспорт рекламу сбыт
Транспорт	1	2	4	5	6	9	4,34
Реклама	12	10	8	6	4	3	3,7
Сбыт	4	7	6	5	5	7	4,49
Надбавка	28,2	33,3	27,8	23,3	22,7	27,7

Вариант №2

	Тов.1	Тов.2	Тов.3	Тов.4	Тов.5	Тов.6	Лимит на транспорт рекламу сбыт
Транспорт	1	2	4	5	6	9	3
Реклама	14	12	10	8	6	5	5,28
Сбыт	5	3	7	6	6	3	3,72
Надбавка	27,4	20,5	27,3	27,9	27	23,3

Вариант №3

	Тов.1	Тов.2	Тов.3	Тов.4	Тов.5	Тов.6	Лимит на транспорт рекламу сбыт
Транспорт	1	2	4	5	6	9	6,44
Реклама	16	14	12	10	8	7	10,72
Сбыт	6	4	3	7	7	4	4,75
Надбавка	35,8	31,4	30,5	32,7	29,5	29,6

Вариант №4

	Тов.1	Тов.2	Тов.3	Тов.4	Тов.5	Тов.6	Лимит на транспорт рекламу сбыт
Транспорт	1	2	4	5	6	9	5,44
Реклама	18	16	14	12	10	9	19,76
Сбыт	7	5	4	3	3	5	5,92
Надбавка	34,4	31,5	29,4	24,2	24,7	28,1

Вариант №5