Слайд 1МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА
РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное образовательное
учреждение высшего
профессионального образования
«ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПО ЗЕМЛЕУСТРОЙСТВУ»
Факультет Заочный
Специальность 120300 «Землеустройство»
Кафедра Землеустройства
Дисциплина «Экономико-математические
методы и моделирование»
Лекция 3. Симплексный метод линейного программирования
Лектор: доцент кафедры землеустройства,
к.э.н. Сорокина Ольга Анатольевна
Слайд 2План лекции
1.Условия, учитываемые при постановке экономико-математических задач
2.Общие сведения о
симплексном методе
3.Алгоритм вычислений симплекс-методом
4.Формулировка и запись ЭММ в
структурном виде.Составные части модели.
5. Виды переменных в симплекс-задачах
6. Структурный вид задачи
7.Недостатки симплекс-метода
8.Геометрическая интерпретация задач линейного программирования
10.Каноническая форма задачи
11. Виды дополнительных переменных
12. Оптимальный план задачи
13. Анализ оптимального решения
Слайд 31.Условия, учитываемые при постановке экономико-математических задач
При постановке экономико-математических задач
изучаются все экономические, технологические, экологические и социальные условия, которым должно
отвечать оптимальное решение
Слайд 41.Условия, учитываемые при постановке экономико-математических задач
К экономическим условиям в проектах
землеустройства следует отнести все виды производственных ресурсов:
Количество трудоспособных
Состав и соотношение
угодий
Наличие производственных построек, вместимость, стоимость, пригодность
Размеры бригад, ферм, севооборотов
Возможный объем производства
Слайд 51. Условия, учитываемые при постановке экономико-математических задач
Технологические условия выражают
производственные требования к моделируемому процессу и представляют нормы затрат на
единицу переменой: на 1 га, 1 гол, затраты труда, кормов, удобрений техники.
Слайд 61.Условия, учитываемые при постановке экономико-математических задач
Социальные условия — условия,
определяющие материальную основу в развитии производственных отношений и производственных сил.
Слайд 71. Условия, учитываемые при постановке экономико-математических задач
Экологические условия —
условия, определяющие пороговые допустимые условия прорастания, посадки, посева сельскохозяйственных культур,
насаждений.
Слайд 81. Условия, учитываемые при постановке экономико-математических задач
Кроме того, следует учитывать
методологический
уровень разработки решения
объем, достоверность, оперативность получения информации и уровень автоматизации
время, необходимое для разработки решения
субъективные факторы и компетентность субъекта, принимающего решения
Слайд 92.Общие сведения
о симплексном методе
Симплексный метод разработан американским ученым
Дж. Данцигом в 1947 г. и получил широкое распространение в
практике решения экономических задач.
В землеустройстве симплексным методом решаются межотраслевые и внутрихозяйственные классы задач.
Слайд 102.Общие сведения
о симплексном методе
Симплекс-метод — это вычислительная процедура, основанная
на принципе последовательного направленного улучшения решений от одного допустимого решения
к другому, до получения оптимального варианта.
Он основан на важном теоретическом положении: оптимальное решение всегда соответствует одному из крайних точек выпуклого многоугольника или вершинам симплекса.
Слайд 112.Общие сведения
о симплексном методе
Для отыскания оптимального плана нет необходимости
перебирать все варианты, соответствующие вершинам многогранника. Вычисления проводят по определенному
алгоритму.
Алгоритм — это точное описание последовательности выполнения действий при решении задач.
Слайд 123.Алгоритм вычислений симплекс-методом
Процесс решения задач подразделяется на несколько этапов:
Математическая
формулировка условий задач в виде систем неравенств и уравнений;
Решение задачи
симплекс- методом;
приведение задач к канонической форме и нахождение первоначального варианта допустимого плана;
проверка найденного варианта плана на оптимальность;
последовательное улучшение плана до получения оптимального;
Экономический анализ и корректировка оптимального плана.
Слайд 134.Формулировка и запись ЭММ в структурном виде. Составные части модели.
Имеется агрофирма производящая и торгующая с.х. продукцией.
Для процесса производства используются
различные ресурсы: рабочая сила, денежные средства, земля, удобрения. Величина этих ресурсов известна, заданы нормы расхода этих ресурсов на производство единицы продукции.
Известны цены реализации единицы продукции.
Следует определить, например, объемы производства с целью максимальной стоимости продукции, выручки.
Слайд 145. Виды переменных в симплекс-задачах
Вначале до построения модели нужно определить
экзогенные, эндогенные переменные.
Экзогенные переменные – те, которые задаются вне
модели, т.е. известны заранее и параметры – это коэффициенты уравнений модели, свободные члены уравнений и неравенств – ресурсы сырья, земля, корма, капитал.
Эндогенные переменные – это те переменные, которые определяются в ходе расчетов по модели и не задаются в ней извне.
Слайд 15Далее следует задать индексы переменных и перейти к описанию и
формализации задачи: целевой функции и ограничений.
На первом этапе алгоритма вычислений
симплекс-методом записывают математическую формулировку базовой ЭММ.
В структурном виде ЭММ можно представать следующим образом:
Слайд 197.Недостатки симплекс-метода
Недостатки симплекс-метода линейного программирования заключаются в том, что такая
модель не всегда точно и полно описывает ситуацию и соответствует
поставленным практическим задачам.
Это обусловлено следующими причинами:
Слайд 207.Недостатки симплекс-метода
ресурсы частично взаимозаменяемы;
нормы затрат ресурсов не прямо пропорциональны выпуску,
т.е. имеются постоянные издержки, не зависящие от объема и переменные
затраты;
объемы ресурсов могут изменяться (продаваться, покупаться);
Слайд 217.Недостатки симплекс-метода
цены продукции и ресурса меняются от объема их реализации
и покупки;
прибыль является не единственным критерием;
принятие решений важно не только
в один момент, а на протяжении периода;
случайность и неопределенность не принимаются во внимание, т.е. коэффициенты в целевой функции и условиях задачи являются постоянными
Слайд 228.Геометрическая интерпретация задач линейного программирования
Фермерское хозяйство разводит кур и гусей.
На
1 курицу расходуется 5 кг. зерна,
и 10 чел.-часов рабочего
времени.
На 1 гуся расходуется 20 кг.зерна,
и 15 чел.-часов рабочего времени
Всего имеется 400 кг зерна и 450 чел.-часов.
Прибыль от реализации 1 курицы составляет 45 рублей, гуся – 80 рублей.
Слайд 238.Геометрическая интерпретация задач линейного программирования
Сколько кур и гусей нужно вырастить
чтобы получить максимальную прибыль?
Слайд 24Переменные:
x – поголовье кур,
y – поголовье гусей.
Слайд 25Ограничения:
1.По кормам:
5x + 20y £ 400 (кг. зерна)
2.По трудовым
ресурсам:
10x+15y £ 450 (чел.-часов)
Слайд 26Целевая функция:
45x + 80y ® max
Условие неотрицательности переменных:
x ³ 0
y
³ 0
Слайд 30Пересечение прямых
5x + 20y = 400
10x +15y = 450
x =
24
y = 14
Слайд 31В случае двух переменных область допустимых решений, как правило, представляет
собой замкнутый многоугольник.
Симплекс-метод заключается в последовательном целенаправленном обходе вершин
симплекса. В каждой следующей граничной точке симплекса значение целевой функции, в общем случае, улучшается.
Слайд 33Ответ задачи
Максимальная прибыль 2200 руб. будет получена хозяйством при разведении
24 кур и 14 гусей.
Слайд 3410. Каноническая форма задачи
Далее следует перейти к канонической форме задачи,
то есть от неравенств к уравнениям.
Данный переход осуществляется путем
введения дополнительных переменных в определенном порядке: избыточные, остаточные, искусственные.
Слайд 3511. Виды дополнительных переменных
Избыточные переменные вводятся в ограничения типа ≥
со знаком "- ". Они показывают насколько левая часть неравенства
превышает правую, а с экономической точки зрения, показывают - превышение плана.
Избыточные переменные Х11, Х12, Х13, Х14 вставляются в ограничения с 13 по 16 со знаком "-"
Слайд 3611. Виды дополнительных переменных
В ограничениях типа ≤ к основным переменным
добавляется остаточная переменная, она показывает насколько левая часть неравенства меньше
правой, насколько ресурсы недоиспользуются.
Остаточные переменные Х15, Х16, Х17, Х18, Х19, Х20, Х21, Х22, Х23, Х24, Х25, Х26 вставляются в ограничения с 1 по 12 со знаком "+".
Слайд 3711. Виды дополнительных переменных
При решении задач с ограничениями типа ≥
кроме дополнительных переменных вводят искусственные, с целью получения положительных значений
базисных переменных.
Искуственные переменные Х27, Х28, Х29, Х30 вставляются в ограничения с 13 по 16 со знаком "+"
Слайд 3811. Виды дополнительных переменных
Все дополнительные переменные необходимо описать: (их названия
соответствуют названиям ограничений)
Х11 –объем перевыполнения полевых изысканий, тыс руб
Х12– объем
перевыполнения работ на согласование, тыс руб
Х13 – объем перевыполнения работ по экспертизе, тыс руб
Х14 – объем перевыполнения составления смет, тыс руб
Х15 - недоиспользованные трудовые ресурсы, чел-дн
Х16 – недоиспользованные временные ресурсы на проведение камеральных работ, чел-дн
Х17 – площадь непроведенных работ по инвентаризации и кадастровой съемке, га
Х18– площадь непроведенных обследовательских и изыскательских работ, га
Х19 – площадь непроведенных работ на муниципальных землях, га
Слайд 3911. Виды дополнительных переменных
Х20 – площадь непроведенных работ по межхозяйственному
землеустройству, га
Х21 - площадь непроведенных работ по ВХЗ и рабочему
проектированию, га
Х22 – недоиспользованные рабочие материалы, кг
Х23 – недоиспользованный объем фонда оплаты труда, тыс. руб
Х24– недоиспользованные капвложения на приобретение топографического оборудования, тыс.руб
Х25 – недоиспользованные капвложения на приобретение программного обеспечения, тыс.руб
Х26 – недоиспользованный общий объем капвложений, тыс.руб
Х27 - искусственная переменная
Х28 – искусственная переменная
Х29 – искусственная переменная
Х30 – искусственная переменная
Слайд 4012. Оптимальный план задачи
оптимальное решение находится в последней таблице результатов
программы Симпл-Delphi
Слайд 41 ==================
14-я итерация. M =
16, Ni = 10, N = 26,
N1 = 10
==================
На 8-й итерации понижена размерность задачи - исключены искусственные
переменные.
Результаты решения симплексной задачи
(Максимизация целевой функции)
=====================================
Z = 5.47201E+0002
=====================================================================================================
Ном.| базисные|Ном.| Aio |Коэфф. замещ. для некоторых небаз. перем.
ст- | пере- |огр.|(Значение |
ро- | менные |для | базисной | Ai2 | Ai4 | Ai11 | Ai13 | Ai15 | Ai22 | Ai24 |
ки | |доп.| перем.) | (X2) | (X4) | (X11) | (X13) | (X15) | (X22) | (X24) |
i | Xjб |пер.| | (осн.) | (осн.) |(изб. в |(изб. в |(ост. в |(ост. в |(ост. в |
| | | | | |огр. 13)|огр. 15)|огр. 1)|огр. 8)|огр. 10)|
-----------------------------------------------------------------------------------------------------
1 |X7 (осн.)| - | 216.418| -0.221| 0.060| 1.254| 0.254| 0.000| 3.284| -0.299|
2 |X16(ост.)| 2 | 145.672| -0.084| -0.061| 0.015| 0.015| 0.000| 0.134| -0.194|
3 |X17(ост.)| 3 | 3400.000| 1.000| 0.000| 0.000| 0.000| 0.000| 0.000| 0.000|
4 |X18(ост.)| 4 | 425.000| -0.700| 0.000| 1.000| 0.000| 0.000| 0.000| 0.000|
5 |X19(ост.)| 5 | 2300.000| 0.000| 1.000| 0.000| 0.000| 0.000| 0.000| 0.000|
6 |X20(ост.)| 6 | 682.463| -0.973| -1.791| 0.388| -0.612| 0.000| 1.493| -1.045|
7 |X21(ост.)| 7 | 2698.790| 0.110| -0.030| -0.627| 0.373| 0.000| -1.642| 0.149|
8 |X14(изб.)| 16 | 715.672| -0.884| 0.239| 5.015| 1.015| 0.000| 13.134| -1.194|
9 |X23(ост.)| 9 | 1160.260| 0.302| -1.463| -0.416| -0.016| 0.000| -2.448| -0.687|
10 |X3 (осн.)| - | 25.000| 0.700| 0.000| -1.000| 0.000| 0.000| 0.000| 0.000|
11 |X10(осн.)| - | 935.075| -0.654| -1.418| -2.776| 0.224| -1.000| -2.985| 2.090|
12 |X12(изб.)| 14 | 820.149| 3.893| 7.164| -1.552| 2.448| 0.000| -5.970| 4.179|
13 |X8 (осн.)| - | 5.000| -0.960| 0.000| -0.200| 0.000| 0.000| 0.000| -1.000|
14 |X5 (осн.)| - | 292.537| 0.973| 1.791| -0.388| 0.612| 0.000| -1.493| 1.045|
15 |X6 (осн.)| - | 41.791| 0.110| -0.030| -0.627| -0.627| 0.000| -1.642| 0.149|
16 |X9 (осн.)| - | 670.000| 0.960| 0.000| 0.200| 0.000| 0.000| 0.000| 1.000|
=====================================================================================================
(Zj-Cj) 547.201| 0.145| 0.872| 0.204| 0.104| 0.000| 0.940| 0.642|
=====================================================================================================
Индексная строка:
====================================================================================================
Небазисная переменная, | X1 | X2 | X4 | X11 | X13 | X15 |
ее тип (номер соотв. ограничения)|осн. |осн. |осн. |изб. ( 13)|изб. ( 15)|ост. ( 1)|
====================================================================================================
(Zj-Cj) | 8.7E-0001| 1.4E-0001| 8.7E-0001| 2.0E-0001| 1.0E-0001| 0.0E+0000|
====================================================================================================
============================================
X22 | X24 | X25 | X26 |
ост. ( 8)|ост. ( 10)|ост. ( 11)|ост. ( 12)|
============================================
9.4E-0001| 6.4E-0001| 6.4E-0001| 6.4E-0001|
============================================
Слайд 4212. Оптимальный план задачи
Суть решения задачи заключается в таком выборе
значений основных, остаточных и избыточных переменных Xj, при котором,
во-первых,
удовлетворяются ограничения и,
во-вторых, целевая функция принимает оптимальное (наибольшее или наименьшее) значение.
Слайд 4312. Оптимальный план задачи
К основным блокам информации, содержащимся в нем,
относятся:
собственно оптимальное решение — значения в столбце Аio базисных переменных
оптимальное
значение целевой функции, находящееся в индексной строке в том же столбце (Zj);
небазисные переменные равны нулю ;
коэффициенты замещения (коэффициенты структурных сдвигов), расположенные в столбцах небазисных переменных (Aij);
элементы индексной строки, соответствующие небазисным переменным (Zj-Cj).
Слайд 4413. Анализ оптимального решения
Основные переменные, попавшие а базис, характеризуют эффективные
отрасли хозяйства, направления производства, или в нашей задаче виды землеустроительных
работ, которые целесообразно развивать для достижения максимального чистого дохода.
Слайд 4513. Анализ оптимального решения
Основные переменные, не попавшие в базис, характеризуют
неэффективные землеустроительные работы, которые проводить нецелесообразно.
Слайд 4613. Анализ оптимального решения
Экстремальное значение целевой функции показывает максимально возможный
чистый доход фирмы, достигаемый npи оптимальном землеустроительных работ (Zmax);
Любое
другое сочетание отраслей в условиях ограниченности ресурсов, в том числе проведение неэффективных работ (придание ненулевых значений небазисным переменным), будет приводить к ухудшению оптимального плана.
Слайд 4713. Анализ оптимального решения
Остаточные переменные, попавшие в базис, характеризуют недоиспользованные
ресурсы, то есть соответствующие им ресурсы являются недефицитными.
Слайд 4813. Анализ оптимального решения
Остаточные переменные, не попавшие в базис (и
соответственно равные нулю), характеризуют полностью исчерпанные, то есть дефицитные, ресурсы.
Всякое увеличение дефицитного ресурса обеспечивает дополнительное развитие эффективных землеустроительных работ и увеличение дохода фирмы.
Слайд 4913. Анализ оптимального решения
Избыточные переменные, вошедшие в базис, характеризуют сверхплановое
производство работ
Слайд 5013. Анализ оптимального решения
Избыточная переменная, не вошедшая в базис (и,
стало быть, равная нулю), свидетельствует о точном выполнении (без перевыполнения)
заданного в соответствующем ограничении требования по производству работ.
Более того, попадание избыточной переменной в число небазисных свидетельствует о том, что перевыполнение плана невыгодно с точки зрения максимизации целевой функции.
Соответствующие плановые задания можно назвать критическими — их включение в условия задачи, как правило, сдерживает дальнейшее повышение эффективности работы фирмы в целом.
