Постановка ОЗЛП и ее экономическое значение

Модель общей задачи линейного программирования в общем виде выглядит так: i - номер ресурса;j - номер выполняемой работы;

bi - количество ресурсов с номером i;

Найти мах F=c1+c2+c3+...cj+...+cn при условиях:

a11x1+a12x2+a13x3+...a1jxj+...+a1nxn<=b1

a21x1+a22x2+a23x3+...a2jxj+...+a2nxn<=b2

ai1x1+ ai2x2+ ai3x3+... aijxj+...+ ainxn <=bi

an1x1+an2x2+an3x3+...anjxj+...+annxn<=bn

x1 >=0 x2>=0 x3>=0 xj>=0 xn>=0

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

Экон.пост.зад.зав.отпринятого критерия опт-ти и цели и реш.задачи. ОЗЛП обычно имеет 2 симметр.эк.подхода,каж.из кот-ых имеет свою постановку.Они наз.двойств.зад.В обр стоит зад:если собст-к рес-в захочет сдать их в аренду,то он должен знать цены аренд плат. Аренд-ль макс доход,арен-р мин затраты.Решение любой зад.позволит оценить эф-ть рез-в и сделаь прогноз по наиболее эф-му исп-нию рес-в.Для этого исп-ся аппарат объективно обуслов.оценок рес-а Л.В.Канторовича.

 

 

30.31. Построение допустимого плана ОЗЛП.Симплекс-метод

Шаг 1. Построение канонической формы. Для каждого ограничения вводим Xj >=0 - дополнительную переменную.

Шаг 2. Строится базис допустимого плана относительно этих переменных. Для этого приравняем 0 переменные X1= X2= X3= X4=0. На основе базиса допустимого плана построим специальную форму для решения задачи симплекс-методом. Здесь в столбце ci приведены показатели целевой функции переменных, входящих в базис задачи. pi - наименования самих показателей, X5, X6, X7, В столбце Xi приведены значения показателей: X5=12, X6=8, X7 =48. Первая строка таблицы содержит значения показателей cj. Вторая строка содержит наименования переменных канонической формы. Последняя - индексная строка содержит данные коэффициентов, рассчитываемых на шаге 3: zj-cj Шаг 3. Рассчитываются симплекс- множители (zj) и показатели индексной строки zj-cj,: где zj рассчитывается по формуле:ci*aij Шаг 4. Выполняется проверка решения на оптимальность. Для задач на максимум целевой функции должно выполняться условие:zj-cj>=0 Шаг 5. Выбор ключевого столбца. Из показателей индексной строки выбирается значение с наибольшим отклонением от условия оптимальности. Соответствующая переменная на следующей итерации входит в базис задачи. Шаг 6. Выбор ключевой строки. Находится минимальное отношение показателей столбцов xi и aij при условии, что aij>=0. Шаг 7. Выполняются симплекс - преобразования:

 

 

Значение эл-та в новом базисе

Значение эл ключевой строки в новом базисе

Значение эл в текущем базисе

Значение элем ключев стр в текущем базисе

Знач эл ключ столбца в текущем базисе

Знач ключ эл в текущем базисе

 

 

Модель общей задачи линейного программирования в общем виде выглядит так: i - номер ресурса;j - номер выполняемой работы;

bi - количество ресурсов с номером i;

Найти мах F=c1+c2+c3+...cj+...+cn при условиях:

a11x1+a12x2+a13x3+...a1jxj+...+a1nxn<=b1

a21x1+a22x2+a23x3+...a2jxj+...+a2nxn<=b2

ai1x1+ ai2x2+ ai3x3+... aijxj+...+ ainxn <=bi

an1x1+an2x2+an3x3+...anjxj+...+annxn<=bn

x1 >=0 x2>=0 x3>=0 xj>=0 xn>=0

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

 

 

32. Анализ оптимального плана решения задачи состоит из нескольких этапов. Из содержания оптимального плана следует что, необходимо выпускать изделия первого (х1) и четвертого (х4) вида в количестве 97,5 и 380 единиц. Это обеспечивает массу прибыли в 5535 стоимостных единиц. Остальные изделия в оптимальный план не попали. Это значит, что значения соответствующих переменных равны: х2=х3=0.

Подставим значения неизвестных в оптимальном плане в систему неравенств модели. Имеем:770=770; 575<740; 195<700; 575<800; 760=760 X1 >0 X2 =0 X3 =0 X4 >0 Первое и последнее неравенства выполняются как равенства, т.е. ресурсы используются полностью, а второе, третье и четвертое неравенства выполняются как строгие - имеются излишние ресурсы в количестве 895 ед.. Этому же соответствует и значения дополнительных переменных х6+х7+х8=895 ед. Двойственная оценка характеризует прирост прибыли на единицу прироста соответствующего ресурса. Используя двойственные оценки видно что, ресурсы пятого вида наиболее эффективны для производства. Каждая единица прироста этого ресурса обеспечивает увеличение целевой функции на 4,75 единицы.