Общая постановка задачи линейного программирования. Графический способ решения задачи линейного программирования.

Общая постановка задачи линейного программирования. Графический способ решения задачи линейного программирования.

 

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

Главная особенность ЗЛП – экстремум целевой функции находится на границе области допустимых решений (D).

х₂

 

D Z(x)max

 

х₁

 

Z(x) Z(x)min

 

 

Математическая модель ЗЛП: max(min) Z = z(x); x D.

Формы записи

1.В виде функций:

Краткая форма

 

Развёрнутая форма:

 

2. Векторная форма

 

3. Матричная форма

Балансовый метод решения экономических задач. Схема межотраслевого баланса (МОБ).

Однопродуктовая модель производства и распределения общественного продукта на уровне всего народного хозяйства (НХ) позволяет увязать основные макроэкономические показатели, такие как валовый продукт, конечный продукт, капвложения, трудовые ресурсы, потребление и другие. Но для эффективного управления экономикой необходимо установить пропорции не только на НХ уровне, но и отраслевом. Это позволяет сделать метод МОБ. Он служит базой определения сбалансированной системы основных показателей. Он представляет кругооборот общественного продукта в целом по НХ и на межотраслевом уровне. Идея МОБ: каждый производимый в НХ продукт должен быть рассмотрен по элементам стоимости как суммы затрат различных продуктов, расходуемых на его изготовление, амортизацию основных фондов, величину зарплаты работников, величину чистого дохода. МОБ может разрабатываться в стоимостном, натуральном и натурально-стоимостном выражении. Наряду с НХ, разрабатывают региональные МОБ по экономическим регионам. Принцип МОБ используется в для построения внутриотраслевых продуктовых балансов, характеризующих связи МОБ с видами производства внутри крупных отраслей. Эти же принципы можно положить в основу баланса предприятия. В МОБ понятие отрасли отличается от общепринятого. В МОБ выделяют «чистые» отрасли – совокупность производств, выпускающих однородную продукцию. Под номенклатурой понимается перечень отраслей, которые вводятся в таблицу МОБ. Схема МОБ производства и распределения совокупного общественного продукта в стоимостном выражении:

 

Производящие отрасли	Потребляющие отрасли	Конечный продукт	Валовый продукт
		n
1	X11	X12	X1n	Y1	X1
	X21	X22	X2n	Y2	X2
n	Xn1	Xn2	Xnn	Yn	Xn
Амортизация	C1	C2	Cn
Оплата труда	V1	V2	Vn
Чистый доход	M1	M2	Mn
Валовый доход	X1	X2	Xn		ΣXi = ΣXj

3 квадрант

2 квадрант

 

 

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

1 квадрант – шахматная таблица межотраслевых связей

2 квадрант – конечная продукция всех отраслей материального производства

3 квадрант – характеризует национальный доход, но со стороны его стоимостного состава как сумма чистой продукции и амортизации

4 квадрант – находится на пересечении 2 и 3 квадрантов, он отражает конечное потребление и использование национального дохода.

Метод МОБ применяется для анализа важнейших показателей как труд, фонды, цены и др. В число важнейших входит определение прямых и полных затрат труда на единицу продукции. Обозначим затраты живого труда в производстве j-го продукта как Lj, а объем производства Xj. Тогда прямые затраты труда на единицу Xj:

Полные затраты труда можно представить как сумма прямых затрат и затрат овеществленного труда. Если обозначить полные затраты на единицу j-й продукции через Tj, то произведение aij*tj отражает затраты овеществленного труда, перенесенные на единицу j-го продукта через i-е средство производства. Тогда Тj на единицу (коэффициент полной трудоемкости):

Просуммировав затраты труда по отраслям

Это соотношение – основное балансовое равенство в теории МОБ труда. Сопоставляя потребительский эффект взаимозаменяемой продукции с полными затратами труда на их выпуск можно судить о сравнительной эффективности их производства. Для проверки выполнимости плана по труду на основе отчетного баланса:

1 – t⁰j (отчетный год)

2 -

3 – L<L^П => план не выполним и его следует корректировать.

Развитие основной модели МОБ может быть осуществлено путем включения в нее фондоемкости продукции. В этом случае модель дополняется отдельной строкой, в которой указывается в стоимостном выражении объем производственных фондов, занятых в каждой отрасли, где Фj – объемы производственных фондов j-й отрасли, f – коэффициент прямой фондоемкости (он показывает величину производственных фондов непосредственно занятых в производстве данной отрасли в расчете на единицу продукции.

Коэффициент полной фондоемкости Fj отражает объем производственных фондов, необходимых во всех отраслях для выпуска j-й продукции.

Можно проверить план:

1-

2 - , если F<Fп => план не выполним.

 

Планирование вычислительного эксперимента. Полный факторный эксперимент.

При построении экспериментальной факторной модели объект моделирования представляется «черным» ящиком, на вход подаются переменные X,Z, а на выходе регистрируются переменные Y. X- внутренние параметры, Z – внешние параметры, Y – выходные параметры. В вычислительных экспериментах объектом исследования является теоретическая или имитационная модель, на основе которой необходимо установить факторную модель. Эксперимент – система операций, воздействий и наблюдений, направленных на получение информации об объекте при исследовании. Активным называется эксперимент, в котором значения факторов задаются и поддерживаются неизменными в течение опыта в соответствии с планом эксперимента. Основные принципы планирования эксперимента: 1 цель планирования эксперимента – получение максимума информации о свойствах исследуемого объекта при минимуме опыта. Это обусловлено высокой стоимостью экспериментов и вместе с тем – построением адекватной модели 2 в вычислительном эксперименте, в отличие от физического, нет ограничений на выбор управляемых параметров и пределов их изменения. При планировании активных экспериментов применяются принципы 1 отказ от полного перебора всех возможных состояний объект 2 постепенное усложнение структуры матмодели 3 сопоставление результатов эксперимента с величиной случайных помех 4 рандомизация опытов 5 оптимальное планирование эксперимента.

При проведении активного эксперимента задается определенный план варьирования факторов. План эксперимента – совокупность данных, определяющих число, условие и порядок реализации опытов. Планирование эксперимента – выбор плана эксперимента, удовлетворяющего заданным требованиям. Точка плана – совокупность численных значений факторов, соответствующих условиям проведения опыта, т.е. точка факторного пространства, в которой эксперимент, т.е. Xi={X1,X2,…,Xn}. Общая совокупность таких векторов образует план эксперимента. Совокупность различных векторов, число которых n, образуют спектр плана. Матрица плана представляет прямоугольную таблицу, содержащую информацию о количестве и условиях проведения опытов. Строки соответствуют опытам, столбцы – факторам. Матрица спектра плана – матрица, в которую входят только различающиеся между собой строки. План называют насыщенным, если общее число точек плана равно числу неизвестных параметров регрессионной модели. Такой план позволяет получить экспериментальную факторную модель при минимальных затратах.

План полного факторного эксперимента. Спектр плана содержит все возможные комбинации значений факторов на всех уровнях изменений. Число точек спектра плана N=Uⁿ, где U- число уровней, n – количество факторов. Для составления матрицы спектра плана используется правило: в 1-й строке все факторы = -1, и в 1-м столбце знаки единиц меняются поочередно, во 2-м чередуются через 2, в 3-м – через 4, в 4-м – через 8 и т.д. по степеням двойки.

-1	-1	-1
+1	-1	-1
-1	+1	-1
+1	+1	-1
-1	-1	+1
+1	-1	+1
-1	+1	+1
+1	+1	+1

X=

	f0	f1=x1	f2=x2	f3=x3	f4=x1x2	f5=x2x3	f6=x1x3	f7=x1x2x3
		-1	-1	-1	+1	+1	+1	-1
		+1	-1	-1	-1	+1	-1	+1
		-1	+1	-1	-1	-1	+1	+1
		+1	+1	-1	+1	-1	-1	-1
		-1	-1	+1	+1	-1	-1	+1
		+1	-1	+1	-1	-1	+1	-1
		-1	+1	+1	-1	+1	-1	-1
		+1	+1	+1	+1	+1	+1	+1

Т.к. при использовании всех возможных сочетании факторов в уравнении регрессии число определенных коэффициентов Nв = числу точек спектра плана, то такой план – насыщенный.

15. Дробный факторный эксперимент (ДФЭ). Проверка пригодности спектра плана для проведения эксперемента.

Наряду с положительными качествами полного факторного эксперимента, он имеет недостаток. Увеличение количества факторов приводит к быстрому росту числа опытов и, что обусловлено степенной зависимостью (2ⁿ). Кроме того, необходимо дублирование опытов. Структура регрессионной модели выбирается на основе априорной информации о физических свойствах объекта. Сложно представить влияние на характеристики объекта сочетания факторов выше 2 или 3 порядка. Поэтому часто ограничиваются сочетаниями факторов 2-го порядка и отдельными сочетаниями 3-го порядка. В этом случае полный факторный эксперимент оказывается избыточным. Но тогда должно соблюдаться условие возможности оценки коэффициентов регрессии по результатам опытов, которые выражаются N≥Nв (N-число экспериментов, Nв – число переменных). Во многих случаях описания модели сложной системы в связи с отсутствием необходимой информации о влиянии фактора на выходные параметры строят линейную модель. Так для 3-х факторов Nв=4, а при Nв=3, спектр плана должен иметь 8 точек => 4 опыта оказываются избыточными и их можно сократить на основе принятых условностей. При построении матмодели использующих упрощенное представление регрессии применяют дробные факторные эксперименты. Наибольшее распространение получили планы дробного факторного эксперимента типа 2^n-p, p – степень дробности, n – число факторов. Планы ДФЭ принято называть репликами с указанием степени дробности. ДФЭ 2^n-1 – полуреплика, ДФЭ 2^n-2 – четвертьреплика. Число точек спектра этого плана N=2^n-p. При соблюдении такого плана должно соблюдаться условие отсутствия в матрице базисных функций совпадающих или полностью противоположных столбцов. Процедура построения спектра плана ДФЭ:

1 выбор структуры уравнения регрессии и определение степени дробности. Исходят из условия N>Nв

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

3 построение матрицы спектра плана ДФЭ. Для этого используется матрица, полученная на 2-м шаге в качестве 1-й части, во 2-ю часть должны войти столбцы матрицы для остальных факторов, число которых равно p. Столбцы матрицы, соответствующие эти факторам определяют путем умножения соответствующих столбцов ведущих факторов. Для этого используют т.н. генерирующее соотношение – алгебраическое выражение, устанавливающее связь между одним из факторов и произведением какой-либо комбинации ведущих факторов. Чтобы полученные столбцы были ортогональными, для каждого из них задается отдельное генерирующее соотношение. Выбор их произволен, но нельзя использовать те произведения ведущих факторов, которые входят в состав существующих переменных, т.к. в этом случае в матрице базисных функций окажутся совпадающие столбцы. Количество ведущих факторов, входящих в генерирующее соотношение может быть произвольным

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

Иначе последовательно выполняется следующая процедура:

1 выбираются иные генерирующие соотношения

2 изменяется набор ведущих факторов

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

 

Общая постановка задачи линейного программирования. Графический способ решения задачи линейного программирования.

 

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

Главная особенность ЗЛП – экстремум целевой функции находится на границе области допустимых решений (D).

х₂

 

D Z(x)max

 

х₁

 

Z(x) Z(x)min

 

 

Математическая модель ЗЛП: max(min) Z = z(x); x D.

Формы записи

1.В виде функций:

Краткая форма

 

Развёрнутая форма:

 

2. Векторная форма

 

3. Матричная форма