Экономическая интерпретация ЗЛП, пример постановки задачи и ЭММ.  

Постановка: на некоторый временной период, например месяц, осуществляется формирование производственной программы выпуска двух изделий Р1 и Р2. Для их производства используется два основных вида ресурсов S1 и S2. Экономические оценки ожидаемых месячных объемов этих ресурсов составляют В1 и В2. На предприятии имеются утвержденные нормы расходов производственных ресурсов Аij, i =1,2; j= 1,2. Имеется возможность сбыта любых объемов производственной продукции по приемлемым продажным ценам С1 и С2. Необходимо выбрать такой вариант месячной производственной программы, который позволяет максимизировать выручку от продаж. Численное значение величин приведем в таблице:

ЭММ задачи: введем обозначения: обозначим через Х1 – объем продукции первого вида Р1, через Х2 – второго вида Р2. С учетом этих обозначений , математически задача записывается:

Max f (x) = f(x1, x2)=C1x1+C2x2                                                   

 max f(X1,X2)= 2X1+3X2

A1,1X1 + A1,2X2≤B1                                  

или

 1X1+3X2≤300                                                                         

A2,1X1+A2,2X2≤B2                                                                               1X1+1X2≤150

X1,2≥0    X1,2≥0

Эта модель 1а, 2а, 3а, 4а, 5а, т.е. задача линейного программирования. Реализация этой модели может быть осуществлена симплекс-методом.

1) Х* = 75, Х2*=75, т.е. следует производить 75 единиц продукции первого вида и 75 единиц – второго вида. Ожидаемая выручка составит f(X*)=f(X1*,X2*)=2*75+3*75=375 у. Е.

Определение объемов валовой и конечной продукции по модели Леонтьева.  

Задав в модели величины валовой продукции каждой отрасли (Xi), можно определить объемы конечной продукции каждой отрасли (Yi): Y=(E-A)X

Задав величины конечной продукции всех отраслей (Yi) можно определить величины валовой продукции каждой отрасли (Xi): X=(E-A)ˉ¹ Y

Матрица коэффициентов полных материальных затрат, способы ее определения.  

Матричная форма модели Леонтьева (E-A)X=Y. По ней можно определить объемы валовой продукции отраслей X1,X2,…,Xn по заданным объемам конечной продукции: X=(E-A)ˉ¹ Y X=BY B=(E-A)ˉ¹. Элементы bij обратной матрицы B=(E-A)ˉ¹ называются коэффициентами полных (материальных) затрат. Это затраты i-той отрасли на каждый рубль конечной продукции отрасли j. Матрицу В называют матрицей коэффициентов полных затрат.

40. Расчет параметров кривой роста методом наименьших квадратов [1 стр.195-198].  

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

Задача дискретной оптимизации, пример (постановка задачи и ее ЭММ).  

Целочисленное программирование изучает задачи, в которых на искомые переменные накладываются условия целочисленности, а ОДР конечна.

Задача о ранце.

Постановка: Организация арендует баржу грузоподъемностью 83т на которой предполагает перевозить груз, состоящий из предметов 4 типов. Веса и стоимости предметов равны соответственно 24т,22т,16т,10т и 96у.е.,85у.е.,50у.е.,20у.е. Требуется погрузить на баржу груз максимальной стоимости. ЭММ: Введем обозначения. Пусть Xj, j=1,4 число предметов j-того типа, которое следует погрузить на баржу. С учетом этих обозначений ЭММ задача о подборе для баржи допустимого груза максимальной ценности записывается:

Max f(x1,x2,x3,x4)=96x1+85x2+50x3+20x4

24x1+22x2+16x3+10x4 ≤ 83

xj, j=1,2,3,4 – неотрицательное целое число.

Это модель типа 1а2б3а4а5а – т.е. модель целочисленного (дискретного) линейного программирования. Реализация этой модели средствами EXCEL позволяет получить решение: 1. X1*=3 x2*=0 x3*=0 x4*=1 2.maxf(x)=308y.e.

Коэффициенты прямых и полных материальных затрат, связь между ними, методы расчета.   

max f(x)=∑CjXj.  При ограничениях: ∑АijXj=Bi, i= от 1 до m, Xi≥ 0, Bi≥0, i= от 1 до m, j= от1 до n. Приведение ЗЛП к каноническому виду осуществляется введением в левую часть соответствующего ограничения вида k-й дополнительной переменной Xn+k ≥ 0 со знаком (– )в случае ограничения типа ≥ и знаком (+) в случае ограничения типа ≤. Если на некоторую переменную Xr не накладывается условие неотрицательности, то делают замену переменных: Xr=Xr' – Xr", Xr'≥0 и Xr"≥0.

43. Каноническая форма записи ЗЛП. Способы приведения ЗЛП к каноническому виду.

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

В процессе решения системы уравнений на некотором этапе получилась расширенная матрица вида:

( 10…0А'1r+1…А'1n | B'1)

А'= ( 01…0A'2r+1…A'2n | B'2 )

(………………………|……)

(00….1A'rr+1…A'r n | B'r )

Система совместна и имеет бесчисленное множество решений. Общее решение системы записывают:

Х1= В'1-А'1r+1*Xr+1 ------A'1n*Xn

X2=B'2- A'2r+1*Xr+1-------A'2n*Xn

----------------------------------------------

Xr= B'r - A'rr+1*Xr+1--------A'r n*Xn

Придавая каждой из стоящих в правых частях равенств переменных Xr+1, Xr+2,……, Xn; произвольные значения, получаем частные решения системы. Неизвестные Х1, Х2,…., Хr; называют базисными или основными, они соответствуют линейно-независимым векторам А1, …, Аr. Любые r – переменных называют базисными, если определитель матрицы коэффициентов при них отличен от нуля, а остальные (n-r) переменных называют свободными или не основными. Базисным решением системы уравнений называют частное решение, в котором не основные переменные имеют нулевые значения. Каждому разбиению на основные и не основные переменные соответствует одно базисное решение, а количество способов разбиения не превышает величины Сⁿⁿn=n! /m!*(n-m)!

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

45. Классическая задача оптимизации, метод получения решения [3 стр.13-14].