Теоретические основы математического моделирования экономических процессов в сельском хозяйстве
Основы математического моделирования экономических систем и процессов: особенности в сельском хозяйстве. Качественный и структурный анализ. Линейное программирование, примеры решения задач (симплексный, модифицированный, распределительный методы).
| Рубрика | Экономико-математическое моделирование |
| Вид | учебное пособие |
| Язык | русский |
| Дата добавления | 02.04.2014 |
| Размер файла | 317,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Решить эту проблему помогает наука, занимающаяся разработкой теории и методов обоснования выбора наилучших вариантов плана из множества возможных. Она получила название математическое программирование. Программирование предполагает выбор лучшей программы производства, лучшего плана. Но «лучший» в зависимости от чего? Прежде всего, от конкретной цели производства. Цель обязательно выражается количественным показателем (стоимость валовой продукции, сумма затрат и т. д.). Этот показатель называется критерием оптимальности плана и задается математически в виде некоторой целевой функции (функционала). Таким образом, решение планово-экономических задач сводится к нахождению либо максимального, либо минимального значения, другими словами, экстремального значения критерия оптимальности.
Следовательно, оптимальным вариантом плана называют тот вариант, который обеспечивает достижение экстремального значения критерия оптимальности.
Математическое программирование включает линейное, нелинейное, динамическое, целочисленное, параметрическое, дробно-линейное и стохастическое программирование.
В задачах линейного программирования между переменными существует линейная зависимость, т. е. неизвестные переменные представлены в первой степени. В задачах нелинейного программирования между переменными существует хотя бы одна нелинейная зависимость. В задачах целочисленного программирования неизвестные могут принимать только целочисленные значения. В задачах параметрического программирования переменные являются функциями некоторого параметра. В задачах дробно-линейного программирования целевая функция представляет собой отношение двух линейных функций. В задачах стохастического программирования переменные представлены случайными величинами. В задачах динамического программирования процесс нахождения решения является многоэтапным.
В практике наиболее широкое распространение получили планово-экономические задачи, в которых условия производства и критерий оптимальности могут быть представлены в виде системы линейных уравнений и неравенств. Такого рода задачи изучаются в теории линейного программирования. Линейное программирование - наиболее обширный, хорошо изученный и практически важный раздел математического программирования. Линейное программирование включает общие (симплексный и его модификации) и специальные (распределительный и его модификации) методы.
Экономической целью задач линейного программирования является оптимальное использование и распределение ограниченных ресурсов для достижения желаемой цели. В области сельскохозяйственного производства этими методами можно:
1) решать проблемы наиболее эффективного использования производственных ресурсов (земли, труда, техники и др.) для увеличения производства необходимой сельскохозяйственной продукции;
2) отыскивать пути максимального увеличения производства в условиях ограниченных производственных ресурсов;
3) достигать требующегося объема производства при минимальных затратах производственных ресурсов;
4) осуществлять нужные производственные действия с минимальными, наиболее экономными затратами труда и средств;
5) принимать наиболее эффективные решения по управлению производством.
Этот перечень включает наиболее важные проблемы сельскохозяйственной экономики, которые решаются с помощью методов линейного программирования. По перечисленным проблемам можно также судить, что применение математических методов необходимо в тех случаях, когда требуется отыскать наилучшее, оптимальное решение. Поэтому, принимая термин «линейное программирование», следует вкладывать в него не только математическое, но и экономическое содержание.
Под методами линейного программирования понимаются программы математических действий, позволяющие находить оптимальное решение различных экономических проблем, условия которых - линейные уравнения и неравенства - сведены в единую систему линейных соотношений, подчиненную конкретной целевой функции.
Систематическое исследование задач линейного программирования, прежде всего как экономических задач, разработка общих методов их решения начаты были в 1939 г. в работах советского математика академика Л.В. Канторовича и его учеников. Канторовичем был предложен общий метод, названный им методом разрешающих множителей, который лишь в деталях отличается от общепринятого сейчас симплексного метода. Для решения транспортных задач им же совместно с М.К. Гавуриным в 1949 г. был предложен метод потенциалов, представляющий собой реализацию метода разрешающих множителей применительно к решению транспортных задач. В последующих работах (Л.В. Канторовича, В.С. Немчинова, В.В. Новожилова, А.Л. Лурье, А. Брудно, Г.Ш. Рубинштейна, Ц.Б. Юдина, А.Г. Аганбегяна и многих других советских ученых-математиков и экономистов) получили дальнейшее развитие как математическая теория линейного и нелинейного программирования, так и приложение ее методов к исследованию различных экономических проблем. О заслугах академиков Л.В. Канторовича, В.С. Немчинова и профессора В.В. Новожилова в развитии экономико-математических исследований свидетельствует факт присуждения им в 1965 г. Ленинской премии. Практическое применение методы решения задач линейного программирования нашли в нашей стране только в 50-е годы, когда были созданы первые ЭВМ.
Почти одновременно и, по-видимому, независимо от работ академика Л.В. Канторовича методы линейного программирования разрабатывались зарубежными, и прежде всего американскими, учеными. В американской литературе первая работа, содержащая постановку транспортной задачи, опубликована в 1941 г. Ф.Л. Хичкоком. Основной метод решения задач линейного программирования - симплексный метод - был опубликован в 1949 г. Дж. Данцигом. Дальнейшее развитие методы линейного программирования получили в работах Форда, Фулкерсона, Куна (общий метод), Лемке (двойственный симплексный метод), Гасса (параметрическое программирование), Чарнеса (проблема вырождения), Раднера (выпуклое программирование) и др.
Чтобы раскрыть сущность построения задачи линейного программирования, рассмотрим упрощенный пример.
Экономическая постановка задачи. Допустим, хозяйство занимается возделыванием трех культур (пшеница, ячмень и картофель). Оно располагает следующими ресурсами:
· пашня - 3000 га;
· труд - 133 600 чел.-ч;
· денежные средства - 15 000 000 руб.
Площадь под зерновыми культурами должна быть не менее 2000 га.
Цель производства - получение максимального объема валовой продукции (в стоимостном выражении).
Требуется найти оптимальное сочетание посевных площадей культур. При математической формулировке условий задачи будем пользоваться нормативами затрат и выхода продукции для данного хозяйства, приведенными в табл. 3.1.
В теории линейного программирования разработаны весьма эффективные методы нахождения оптимального варианта плана, соответствующего экстремальному значению целевой функции. Чтобы воспользоваться этими методами, необходимо уметь математически описывать условия и ограничения задачи.
Таблица 3.1 Нормы затрат и выхода продукции в хозяйстве
|
Культура |
Затраты на 1 га посева |
Стоимость валовой продукции с 1 га, руб. |
||
|
труда, чел.-ч |
материально-денежных средств, руб. |
|||
|
Пшеница (Х1) Ячмень (Х2) Картофель (Х3) |
40 35 150 |
1500 1650 3500 |
4000 3500 11 000 |
В нашем примере неизвестными величинами являются посевные площади пшеницы, ячменя и картофеля. Обозначим их через Х1, Х2, Х3 и назовем переменными задачи. Критерий оптимальности в соответствии с требованиями линейного программирования должен быть также сформулирован математически. В данном случае стоимость валовой продукции определяется как сумма произведений стоимости продукции с 1 га на посевную площадь. Критерий оптимальности (функционал задачи или целевую функцию) обозначим через Z. В нашей задаче находим максимум целевой функции, что запишем следующим образом:
Z max = 4000Х1 + 3500Х2 + 11000Х3.
Максимум целевой функции должен быть достигнут при соблюдении следующих условий.
1. Общая посевная площадь зерновых и картофеля не должна превышать площади пашни, га:
Х1 + Х2 + Х3 3000.
2. Общие затраты труда не должны быть больше наличных ресурсов, чел.-ч:
40Х1 + 35Х2 + 150Х2 133 600.
3. Общий объем материально-денежных средств не должен превышать имеющихся ресурсов, руб.:
1500Х1 + 1650Х2 + 3500Х2 15 000 000.
4. Площадь под зерновыми культурами не менее заданной, га:
Х1 + Х2 2000.
5. Площади не могут быть отрицательными величинами:
Х 1 0 , Х2 0, Х3 0.
Таким образом, получили следующую запись условий задачи в исходной форме:
Х1 + Х2 + Х3 3000;
40Х1 + 35Х2 + 150Х2 133 600;
1500Х1 + 1650Х2 + 3500Х2 15 000 000;
Х1 + Х2 2000.
Х 1 0 , Х2 0, Х3 0;
Z max = 4000Х1 + 3500Х2 + 11 000Х3.
Приведенные неравенства называют ограничениями экстремальной задачи линейного программирования. Ограничения бывают трех типов: равенства (=), неравенства типа «меньше либо равно» (), неравенства типа «больше либо равно» ().
Мы привели пример с небольшим количеством переменных и ограничений. Но принципиальное положение заключается в том, что теоретически методы линейного программирования позволяют решать задачи с неограниченным числом переменных и ограничений. Решение зависит только от возможностей (мощностей) электронно-вычислительных машин.
Практически любая система балансов, составляемая при традиционных методах планирования и экономического анализа, может быть записана в виде системы линейных соотношений. Ее решение приведет к нахождению оптимального плана производства. Следовательно, ни количество учитываемых переменных, ни число условий (ограничений) не затрудняют переход от традиционных методов экономического анализа и планирования к методам оптимального решения экономических проблем посредством линейного программирования.
Трудность заключается в том, что методы линейного программирования применимы тогда, когда существует прямая линейная зависимость между причиной и следствием, между функцией и аргументом. Предполагается, что такая зависимость имеет характер прямой пропорциональности. Это, например, означает, что на каждый гектар посева культуры затрачивается одинаковое количество труда, технических средств, каждый центнер удобрений дает одинаковую прибавку урожая, каждый центнер корма позволяет получить равное количество животноводческой продукции. Однако в действительности в сельскохозяйственном производстве зависимость между функцией и аргументом подвержена многим случайным дополнительным факторам, которые нарушают прямую пропорциональность.
Но эта трудность не должна исключать возможность применения методов линейного программирования. Ведь при традиционных методах экономического анализа и планирования в большинстве случаев допускается прямая линейная зависимость. Это же находит свое отражение при составлении систем балансов. Поэтому применение линейного программирования даже в этих условиях даст сельскохозяйственному производству определенную экономическую эффективность, так как за счет более целесообразного использования производственных ресурсов будет произведено больше продукции. Кроме того, нужно учесть и то обстоятельство, что хорошо сбалансированный производственный план, несомненно, легче выполнить, чем плохо сбалансированный.
Применение линейного программирования на основе использования электронно-вычислительной техники значительно сокращает затраты времени на вычисления. Это позволяет больше внимания уделять разработке исходной информации. Можно подготовить исходные данные с меньшим допуском нелинейности по сравнению с тем, которым пользуются при традиционных методах планирования. При обобщении массового материала, используя приемы корреляционной связи, можно проследить определенную линейную зависимость, что позволит получать в решениях практически вполне приемлемые результаты.
Наконец, применение линейного программирования дает возможность во многих случаях отказаться от условностей, которые допускаются при традиционных методах планирования и анализа. Исследуя функциональную зависимость между производственными факторами и результатами производства, привлекая для подготовки исходных данных другие математические методы, можно с помощью линейного программирования намного точнее проводить количественный анализ, что в значительной мере улучшает всю планово-экономическую работу.
Такова экономическая сущность методов линейного программирования как одних из наиболее разработанных в настоящее время методов прикладной математики. Использование этих методов в планово-экономической практике сельскохозяйственного производства оказывает значительное влияние на повышение экономической эффективности сельскохозяйственного производства.
Методами линейного программирования можно решать многие, но не все экономические проблемы. Первой предпосылкой применения методов линейного программирования является допустимость математической формулировки всех условий, определяющих решение экономической проблемы в виде линейных соотношений - уравнений или неравенств. Большинство экономических проблем, относящихся к планированию производства или экономическому анализу, позволяет легко формулировать все условия. В других случаях приходится прибегать к различным приемам, выражая иногда одно условие несколькими линейными соотношениями. Даже те экономические условия, в которых нормативы не постоянны, а изменяются под воздействием переменных факторов или в динамике, можно выразить путем определенных линейных соотношений.
Единственные условия, которые пока не удалось выразить линейными соотношениями, - это такие, в которых переменные величины возводятся в степень или им трудно дать какую-либо прямую количественную оценку и связать функциональной зависимостью с другими условиями системы, допускающими математическую формулировку. Среди этих условий - квалификация кадров, опыт руководства и другие, аналогичные им.
При решении экономических проблем математическими методами, безусловно, должно учитываться и требование неотрицательности значений переменных величин. Ведь в экономической практике какое-либо явление может быть или не быть. Но отрицательное значение этого явления недопустимо, это экономический абсурд.
Применение методов линейного программирования невозможно, если система линейных соотношений не имеет удовлетворительного экономического решения, она несовместна. Несовместность больших систем может быть обнаружена и устранена путем тщательного экономико-математического анализа.
Однако если система ограничений является совместной, но при этом имеет единственное решение, т. е. она - определенная, применение методов линейного программирования становится логически не нужным, так как противоречит самой сути этих методов. Методы линейного программирования применяются для отыскания в совместной системе одного наилучшего решения из множества возможных, с точки зрения некоторого оговоренного условия. С этих позиций совместная неопределенная система линейных соотношений является наиболее подходящей из всех систем.
Экономико-математическая идея методов линейного программирования предполагает, что решение проблемы заключается в нахождении оптимального варианта, наилучшего из всех возможных вариантов. Математический аппарат методов линейного программирования позволяет подойти к конечному решению с учетом определенного критерия оптимальности, который вводится в систему соотношений в виде целевой функции. Но для того чтобы ввести в систему целевую функцию, необходимо, во-первых, четко установить экономическую цель, которая должна быть достигнута при решении системы линейных соотношений, и, во-вторых, эта экономическая цель должна допускать возможность ее формулировки, т. е. выражения в виде особого линейного уравнения - функционала.
Для целевой функции экономический критерий должен быть предельно четок. Если экономическая проблема не допускает точного определения конечной цели или же решение проблемы должно одновременно удовлетворить нескольким целям, то применение методов линейного программирования невозможно.
Обобщая сказанное, можно отметить, что методы линейного программирования применяются при решении экономических проблем, которые удовлетворяют следующим условиям:
1. Все экономические, технологические, социальные и другие требования, определяющие оптимальное решение проблемы, должны допускать их математическую формулировку в виде линейных уравнений и неравенств.
2. Система линейных соотношений, характеризующая все условия данной проблемы, имеет множество допустимых решений, т. е. прежде всего сама экономическая проблема допускает альтернативные решения.
3. Основная цель, которую нужно достичь в результате решения проблемы, четко выражена экономически и сформулирована в виде линейного соотношения.
Различные формы модели задачи линейного программирования. Задача линейного программирования может быть представлена в трех формах.
Первая форма - общая: найти совокупность значений n переменных Х1, Х2, ..., Хn, удовлетворяющих системе ограничений:
a11x1 + ... + a1jxj + ... + a1nxn = a10;
ai1x1 + ... + aijxj + ... + ainxn ai0;
am1x1 + ... + amjxj + ... + amnxn am0
и условиям неотрицательности
хj 0 , j = 1, ..., t, где t n,
для которых целевая функция
Z = C1X1 + ... + CjXj + ... + CnXn
достигает экстремума,
aij - коэффициенты при переменных;
i - номер соответствующего ограничения;
j - номер переменной с данным коэффициентом;
aio - свободные члены;
Cj - коэффициенты целевой функции при переменных.
Особенности этой формы:
1. Система ограничений неоднородна (представлена неравенствами типа «» и «» и уравнениями).
2. Не на все переменные наложено условие неотрицательности.
3. Целевая функция может стремиться и к максимуму и к минимуму.
Общая форма получается, когда записываем модель по условиям конкретной задачи.
Вторая форма - каноническая.
Эта форма модели используется для решения задачи симплексным методом.
Особенности этой формы:
1. Система ограничений однородна и представлена уравнениями:
a11x1 + ... + a1jxj + ... + a1nxn = a10;
ai1x1 + ... + aijxj + ... + ainxn = ai0; I = 1, ..., m;
am1x1 + ... + amjxj + ... + amnxn = am0.
2. На все переменные наложено условие неотрицательности:
Хj 0, j = 1, ..., n.
3. Целевая функция стремится к максимуму:
Z = C1X1 + ... + CjXj + ... + CnXn max.
Третья форма - стандартная. Эта форма модели необходима для графического решения основной задачи линейного программирования при условии, что число переменных равно двум.
Особенности этой формы:
1. Система ограничений однородна и представлена неравенствами типа «», причем число неравенств должно совпадать с рангом системы (r):
a11x1 + ... + a1nxn a10;
i = 1, ..., r;
ar1xr + ... + arnxn ar0.
2. На все переменные наложено условие неотрицательности:
Хj 0, j = 1, ..., n.
3. Целевая функция может стремиться к максимуму или к минимуму:
Z = C1X1 + ... + CjXj + ... + CnXn max (min).
От одной формы модели задачи линейного программирования можно перейти к другой. Для этого необходимо:
1. Научиться переходить от неравенства к равенству. Систему линейных неравенств можно преобразовать в систему линейных уравнений, вводя в левую часть каждого неравенства неотрицательные переменные, которые называют дополнительными переменными. Причем в ограничения типа «меньше либо равно» () эти переменные вводятся с коэффициентом «1», а в ограничения типа «больше либо равно» () - с коэффициентом «-1».
В целевую функцию дополнительные переменные вводятся с нулевыми коэффициентами.
Рассмотрим на конкретном примере. Преобразуем систему ограничений приведенной выше задачи.
Х1 + Х2 + Х3 + Х4 = 3000,
40Х1 + 35Х2 + 150Х2 + Х5 = 133 600,
1500Х 1 + 1650Х2 + 3500Х2 + Х6 = 15 000 000,
Х1 + Х2 - Х7 = 2000.
Хj 0 , j = 1, ..., 7,
Z max = 4000Х1 + 3500Х2 + 11 000Х3 + 0 Х3 + 0 Х4 + 0 Х5 + 0 Х6 + 0 Х7.
Следует обратить внимание на то, что коэффициенты при дополнительных переменных в первых трех ограничениях образуют матрицу, по главной диагонали которой стоят единицы.
Х4 Х5 Х6
1 0 0
0 1 0
0 0 1
Такую матрицу называют единичной. А переменные, образующие единичную матрицу, называются базисными. Остальные переменные, не входящие в единичный базис, называются свободными. Если система ограничений приведена к единичному базису, а все свободные переменные неотрицательны, то такое решение называется базисным. Опорным решением называется базисное решение, в котором базисные переменные неотрицательны. В данном примере базисные переменные - Х4 , Х5 , Х6, а свободные - Х1, Х2 и Х7.
2. Уметь изменить целевую функцию «максимум» на функцию «минимум»:
max = -Zmin.
3. Если в модели не на все переменные наложено условие неотрицательности, уметь преобразовывать отрицательные переменные в неотрицательные. Допустим, что Хn 0, тогда представим:
Xn = Xn - Xn, где Xn Xn , но Xn 0 и Xn 0 .
4. Уметь систему линейных соотношений приводить к единичному базису, пользуясь методом Гаусса.
Методы линейного программирования
В настоящее время существует ряд методов решения задач линейного программирования. Основным из них является симплексный. Это наиболее используемый на практике метод решения задач оптимального программирования. Для него разработаны стандартные и специальные программы решения на ПЭВМ. Симплексный метод дает возможность логической и математической проверки и корректировки результатов решения задач. Он обеспечивает органическую и автоматическую проверку и увязку всех балансовых соотношений исследуемого объекта, что особенно важно для решения плановых задач, и, наконец, дает возможность просчета различных оптимальных вариантов решения по различным критериям оптимальности. В его основе лежит алгоритм симплексных преобразований системы, дополненный правилом, обеспечивающим переход не к любому, а к «лучшему» опорному решению.
Но встречаются такие задачи, когда число переменных значительно превосходит число ограничений, и процесс приведения системы ограничений к единичному базису является неоправданно громоздким. В таких случаях особенно удобен метод искусственного базиса (модифицированный симплексный метод, или М-метод).
Общие методы линейного программирования (симплексный, М-метод и др.) в принципе дают возможность решить любую задачу, однако, как правило, это решение сопряжено со значительными и трудоемкими расчетами. Поэтому представляет интерес выделение отдельных классов задач, решение которых можно получить с помощью приспособленных для них более простых специальных вычислительных методов. Наиболее широким классом таких задач являются так называемые транспортные задачи. Транспортными задачами называются задачи определения оптимального плана перевозок груза из данных пунктов отправления в данные пункты потребления. Решение транспортных задач осуществляется специальным методом - методом потенциалов (модифицированный распределительный метод, или метод «МОДИ»). Он основан на той же идее последовательного улучшения решения, что и симплексный метод, но учитывает специфические свойства математической модели транспортной задачи.
3.2 Симплексный метод линейного программирования
3.2.1 Общая характеристика симплексного метода
Поскольку система линейных уравнений изучается в курсе элементарной алгебры, остановимся лишь на основных определениях, необходимых для понимания дальнейшего материала.
Если система имеет хотя бы одно решение, она называется совместной. Несовместные системы не имеют ни одного решения.
Допустимым решением называется совокупность значений n-переменных, удовлетворяющая системе ограничений и условиям неотрицательности.
Широко используемым на практике методом решения задач линейного программирования является симплексный. Этот метод решения задачи линейного программирования основан на переходе от одного опорного решения к другому, при котором значение целевой функции улучшается (на максимум - увеличивается, на минимум - уменьшается или остается на прежнем уровне) при условии, что данная задача имеет оптимальный план.
При решении задачи симплексным методом можно выделить следующие стадии:
приведение задачи к канонической форме и нахождение первоначального варианта допустимого плана;
проверка найденного варианта плана на оптимальность (если полученный вариант окажется оптимальным, то решение получено, в противном случае план должен быть улучшен);
последовательное улучшение плана в симплексных таблицах до получения оптимального.
3.2.2 Решение задачи линейного программирования в симплексных таблицах. Правила построения симплексных таблиц
Рассмотрим схему построения на примере.
Пример 1.
3Х1 + Х2 4;
Х1 + 3Х2 4.
Хj 0, j = 1, ..., 4,
Zmax = 2 + X1 + 2X2.
Чтобы решить данную задачу линейного программирования симплексным методом, необходимо представить ее в канонической форме, систему ограничений привести к единичному базису. Свободные члены уравнений должны быть неотрицательны.
Как видим, задача не приведена к канонической форме и к единичному базису. Поэтому вводим дополнительные переменные Х3 и Х4.
3Х1 + Х2 + Х3 = 4;
Х1 + 3Х2 + Х4 = 4.
Хj 0, j = 1, ..., 4;
Zmax = 2 + X1 + 2X2 + 0 Х3 + 0 Х4.
Составим первую симплексную таблицу. Она представляет собой форму выражения первого опорного плана. Коэффициенты, стоящие в Z-строке, показывают, как изменяется значение целевой функции при единичном изменении соответствующей свободной переменной. И называются эти коэффициенты оценкой или индексом этой свободной переменной. А сама строка Z называется индексной или оценочной.
Заполнение таблицы:
1. В первом столбце перечисляют базисные переменные.
2. Во второй столбец записывают оценки базисных переменных, указанные в целевой функции.
3. В третьем столбце указывают свободные члены.
4. В остальных столбцах таблицы записывают коэффициенты при свободных переменных по соответствующим уравнениям.
5. Над рабочей частью таблицы перечисляют свободные переменные.
6. Сверху над свободными переменными помещают оценки свободных переменных, указанные в целевой функции. Над столбцом свободных членов записывают свободный член целевой функции (_Сли таковой имеется) с противоположным знаком.
7. Оценки Z-строки рассчитывают по формуле (3.1):
|
a0j=. |
Где j = 1, 2, …, n;
aij - коэффициенты j-го столбца;
Ci - коэффициенты при базисных переменных в уравнении Z;
Cj - коэффициенты при свободных переменных в уравнении Z.
Определение оптимальности плана.
Построение новой симплексной таблицы
В симплексных таблицах формальным признаком оптимальности является содержание оценочной строки.
Ключевая теорема симплексного метода (Z на максимум):
Если после выполнения очередной итерации:
найдется хотя бы одна отрицательная оценка, а в столбце, где она стоит, есть хотя бы один положительный элемент, то опорное решение можно улучшить, выполнив следующую итерацию;
найдется хотя бы одна отрицательная оценка, столбец которой не содержит положительных элементов, то функция Z неограниченна в области допустимых решений (Zmax );
все оценки окажутся неотрицательными, то достигнуто оптимальное решение.
Согласно данной теореме:
1. Просматриваются оценки Z-строки. Если они все неотрицательны, то получено оптимальное решение при решении на максимум целевой функции, если все оценки 0, то получено оптимальное решение при решении на минимум целевой функции.
2. Если оптимальное решение не получено, то выбирается разрешающий столбец по наибольшей абсолютной величине отрицательной оценки Z-строки при решении на максимум и по наибольшей положительной оценке при решении на минимум целевой функции.
3. Составляются симплексные отношения - отношения свободных членов к положительным коэффициентам разрешающего столбца. Минимальное из этих отношений (min ai 0 / aip) определит разрешающую строку. Коэффициент, находящийся на пересечении разрешающей строки и разрешающего столбца, называется разрешающим элементом.
Если в разрешающем столбце нет ни одного положительного коэффициента, то задача не имеет решения по причине неограниченности целевой функции (Zmax +, Zmin -).
4. Осуществляется переход к новой таблице, где базисная переменная заменяется на свободную, соответствующую разрешающему столбцу.
5. Бывший разрешающий элемент заменяется обратным по величине (1/ аqp).
6. Все остальные элементы бывшего разрешающего столбца делятся на разрешающий элемент и меняют знаки на противоположный.
Если в бывшем разрешающем столбце в какой-то строке стоял «0», то эта строка переносится в следующую таблицу без изменений.
7. Все остальные элементы бывшей разрешающей строки делятся на разрешающий элемент.
Если в бывшей разрешающей строке в каком-то столбце стоял «0», то этот столбец переносится в следующую таблицу без изменений.
7. Остальные элементы таблицы пересчитываются по правилу «прямоугольника»:
|
aij = |
Исходный коэффициент |
- |
Коэффициент разрешающей строки |
· |
Коэффициент разрешающего столбца |
|
|
Разрешающий элемент |
aij . . . . aip
. . . . . . . . . aij = aij - aqj · aip / aqp, где
aqj. . . (aqp) i = 1, 2, ... j = 0, 1, ...
9. Осуществляется контроль за правильностью расчетов для элементов Z-строки по формуле (3.1).
10. Если ошибок нет, то алгоритм повторяется с пункта 1.
В первой симплексной таблице нашего примера (табл. 3.2) все коэффициенты оценочной строки отрицательны. Следовательно, согласно теореме, план (на максимум целевой функции) не является оптимальным и требует улучшения.
В последнем столбце рассчитывают симплексные отношения.
Таблица 3.2 Симплексная таблица (исходное опорное решение)
|
Св.П |
Cj |
-2 |
1 |
2 |
ai0/aip |
|
|
Б.П. |
Ci |
ai0 |
X1 |
X2 |
||
|
X3 |
0 |
4 |
3 |
1 |
4 |
|
|
X4 |
0 |
4 |
1 |
(3) |
4/3 |
|
|
Z |
2 |
-1 |
-2 |
Исходное опорное решение: Z1 = 2 при 1 (0, 0, 4, 4).
Во второй симплексной таблице (табл. 3.3) меняем местами базисную переменную X4 и свободную X2. На месте бывшего разрешающего элемента запишем обратную величину, т. е. 1/3.
Все остальные элементы разрешающей строки в новой таблице вычислим путем деления на разрешающий элемент: 4/3; 1/3. Все остальные элементы бывшего разрешающего столбца определим путем деления на разрешающий элемент. Результат запишем в новую таблицу с противоположным знаком: -1/3; 2/3. Все остальные элементы таблицы вычислим по правилу «прямоугольника».
|
Первая строка: 4 - 4 1/3 =8/3 3 - 1 1/3 =8/3 |
Оценочная строка: 2 - 4 (-2)/3 = 14/3 -1 - 1 (-2)/3 = -1/3 |
Таблица 3.3 Вторая симплексная таблица
|
Св.П |
Cj |
-2 |
1 |
0 |
||
|
Б.П. |
Ci |
ai0 |
X1 |
X4 |
ai0/aip |
|
|
X3 |
0 |
8/3 |
(8/3) |
-1/3 |
1 |
|
|
X2 |
2 |
4/3 |
1/3 |
1/3 |
4 |
|
|
Z |
14/3 |
-1/3 |
2/3 |
Проверим правильность заполнения Z-строки по формуле (2.1).
а00 = 0 8/3 + 2 4/3 - (-2) = 14/3,
а01 = 0 8/3 + 2 1/3 - 1 = -1/3,
а02 = 0 (-1/3) + 2 1/3 - 0 = 2/3.
Так как в оценочной строке есть еще отрицательные оценки, оптимальное решение не получено, можем записать только опорное решение: Z2 = 14/3 при 2 (0, 4/3, 8/3, 0).
По тому же алгоритму пересчитываем коэффициенты табл. 3.4.
Таблица 3.4 Третья симплексная таблица
|
Св.П |
Cj |
-2 |
0 |
0 |
|
|
Б.П. |
Ci |
ai0 |
X3 |
X4 |
|
|
X1 |
1 |
1 |
3/8 |
-1/8 |
|
|
X2 |
2 |
1 |
-1/8 |
3/8 |
|
|
Z |
5 |
1/8 |
5/8 |
Все оценки неотрицательны, следовательно, получено оптимальное решение: Zmax = 5 при опт(1, 1, 0, 0).
Пример 2. Задача решалась на максимум функции (Z max). На последнем шаге была получена табл 3.5.
Таблица 3.5 Последняя симплексная таблица
|
Св.П |
Cj |
0 |
1 |
0 |
|
|
Б.П. |
Ci |
ai0 |
X3 |
X2 |
|
|
X1 |
2 |
2 |
1 |
-1 |
|
|
X4 |
0 |
1 |
1 |
-1/2 |
|
|
Z |
4 |
1 |
-2 |
В разрешающем столбце нет ни одного положительного элемента, следовательно, Zmax , т. е. задача линейного программирования не имеет решения по причине неограниченности целевой функции Z сверху.
3.2.3 Альтернативный оптимум
Если среди оценок свободных переменных в последней симплексной таблице есть хотя бы одна оценка равная нулю, то задача имеет альтернативное решение, т. е. хотя бы два оптимальных решения. Для этих решений экстремальное значение функции будет одинаковое. Чем больше будет нулевых оценок, тем больше оптимальных решений.
Пример 3. Представим последнюю симплексную табл 3.6.
Таблица 3.6 Последняя симплексная таблица
|
Св.П |
Cj |
0 |
1 |
5 |
|
|
Б.П. |
Ci |
ai0 |
X1 |
X2 |
|
|
X3 |
1 |
6 |
3 |
(5) |
|
|
X4 |
0 |
8 |
2 |
4 |
|
|
Z |
6 |
2 |
0 |
Zmax = 6 при Xопт(0, 0, 6, 8).
Разрешающий столбец выбираем по нулевой оценке (табл. 3.7).
Таблица 3.7 Альтернативная симплексная таблица
|
Св.П |
Cj |
0 |
1 |
1 |
|
|
Б.П. |
Ci |
ai0 |
X1 |
X3 |
|
|
X2 |
5 |
6/5 |
3/5 |
1/5 |
|
|
X4 |
0 |
26/5 |
-2/5 |
-4/5 |
|
|
Z |
6 |
2 |
0 |
Xопт(0, 6/5, 0, 26/5), Zmax = 6.
3.2.4 Вырождение основной задачи линейного программирования
Если в опорном решении задачи хотя бы одна базисная переменная принимает нулевое значение, то это решение называется вырожденным, а задача линейного программирования, имеющая хотя бы одно вырожденное решение, - вырожденной задачей.
Вырождение наступает в тех случаях, когда при выборе разрешающего элемента получается несколько одинаковых минимальных симплексных отношений. В этом случае в следующей симплексной таблице в столбце свободных членов появится хотя бы один нуль. Вырождение в больших задачах может привести к зацикливанию, т. е. через некоторое число шагов мы можем прийти к опорному решению, которое было уже получено раньше. Чтобы избежать зацикливания, разрешающий элемент нужно выбирать по определенному правилу, а именно: для тех строк разрешающего столбца, где получились одинаковые минимальные симплексные отношения, нужно составить отношения элементов, стоящих в столбце за разрешающим столбцом, к элементам разрешающего столбца. Наименьшее отношение с учетом знака даст разрешающую строку.
Пример 4.
Х1 + 2Х2 4.
2Х1 + Х2 4,
Х1 2,
Х2 2,
Хj 0, j = 1, 2,
Zmax = X1 + X2.
Приводим к канонической форме:
X1 + 2X2 + X3 = 4,
2X1 + X2 + X4 = 4,
X1 + + X5 = 2,
X2 + X6 = 2,
Xj 0, j = 1, ..., 6.
Zmax = X1 + X2 + 0 X3 + 0 X4 + 0 X5 + 0 X6.
Заполняем первую симплексную таблицу по алгоритму симплексного метода (табл. 3.8).
В оценочной строке две одинаковые отрицательные оценки, поэтому разрешающий столбец выбираем тот, который ближе к столбцу свободных членов. Минимальных симплексных отношений два, поэтому находим отношение элементов столбца Х2 к элементам столбца Х1. После пересчета минимальное отношение находится в третьей строке и равно 0, следовательно, разрешающий элемент равен 1. Далее идет обычный пересчет.
Таблица 3.8 Первая симплексная таблица
|
Св.П |
Cj |
0 |
1 |
1 |
ai0/aip |
|
|
Б.П. |
Ci |
ai0 |
X1 |
X2 |
||
|
X3 |
0 |
4 |
1 |
2 |
4 (2) |
|
|
X4 |
0 |
4 |
2 |
1 |
2 (1/2) |
|
|
X5 |
0 |
2 |
(1) |
0 |
2 (0) |
|
|
X6 |
0 |
2 |
0 |
1 |
- |
|
|
Z |
0 |
-1 |
-1 |
3.3 Метод искусственного базиса (м-метод)
До сих пор мы всесторонне рассматривали задачу, решение которой осуществлялось на основе простейшего алгоритма симплексного метода, поскольку все ограничения имели вид «меньше либо равно». В этом случае дополнительные переменные задачи образуют единичный базис. Но может получиться так, что система ограничений представлена в канонической форме, но она не приведена к единичному базису.
При решении таких задач был введен метод искусственного базиса. Он особенно удобен, когда число переменных значительно превосходит число уравнений. Рассмотрим на примере алгоритм решения задачи симплексным методом с искусственным базисом.
Пример 1.
Найти максимум Z = 4X1 + 2X2 + X3.
Х1 + Х2 + Х3 8,
2Х1 + Х2 + Х3 8,
3Х1 + 2Х2 + Х3 = 15,
Хj 0, j = 1, ..., 3.
Переходим к канонической форме:
Х1 + Х2 + Х3 - Х4 = 8,
2Х1 + Х2 + Х3 + Х5 = 8,
3Х1 + 2Х2 + Х3 = 15,
Хj 0, j = 1, ..., 5,
Zmax = 4X1 + 2X2 + X3 + 0 X4 + 0 X5.
Данная система ограничений не имеет единичного базиса, так как дополнительная переменная Х4 имеет коэффициент минус единица, а третье ограничение было представлено уравнением, и в нем отсутствует базисная переменная. Для того чтобы был единичный базис, вводим в соответствующие ограничения искусственные переменные y1 и y2 с положительными коэффициентами (+1).
Следует отметить, что искусственные переменные вводятся только для математической формализации задачи. Поэтому схема вычислений должна быть такой, чтобы искусственные переменные не могли попасть в окончательное решение в числе базисных переменных. С этой целью для искусственных переменных в целевой функции вводят коэффициент М, обозначающий очень большое число. На практике (особенно при решении задачи на ЭВМ) вместо М берут конкретное большое число, например 10 000. Причем при решении задачи на максимум этот коэффициент вводится в целевую функцию со знаком минус, а при решении на минимум - со знаком плюс. Теперь будем решать Т (М) - задачу, целевая функция которой содержит целевую функцию Z-задачи и искусственные переменные с коэффициентом М, т. е.
T = Z - M при решении на максимум целевой функции и
T = Z + M при решении на минимум целевой функции.
В нашем случае:
Х1 + Х2 + Х3 - Х4 + y1 = 8,
2Х1 + Х2 + Х3 + Х5 = 8,
3Х1 + 2Х2 + Х3 + y2 = 15.
Хj 0, j = 1, ..., 5,
Тmax = 4X1 + 2X2 + X3 + 0 X4 + 0 X5 - M(y1 + y2).
Эта задача решается в симплексных таблицах, но для удобства целевую функцию разбивают на две строки:
- в первую строку записываем оценки, которые не содержат коэффициент М;
- во вторую строку - оценки по каждой свободной переменной, содержащие коэффициент М.
Расчет элементов (оценок) этих двух строк производится по формуле (2.1). Однако имеется отличие:
- при расчете оценок Z-строки должны быть учтены коэффициенты Cj , входящие в функцию Z;
- при расчете оценок М-строки этот коэффициент во внимание не берется, а М выносится как общий множитель.
Для того чтобы Т-задача и Z-задача были равны, нужно, чтобы yi были равны нулю. Поэтому пока yi не равны нулю, разрешающий столбец выбирается по оценкам во второй строке, согласно алгоритму симплексного метода.
Лишь после того, как все yi станут равны нулю, дальнейший расчет будет вестись по первой индексной строке (Z-задача).
Причем, когда искусственная переменная будет выводиться из базиса, ее выбросим из симплексной таблицы, а в следующей симплекс-таблице не будет бывшего разрешающего столбца.
Между оптимальными решениями М-задачи и Z-задачи существует связь, устанавливаемая следующей теоремой:
1. Если в оптимальном решении М-задачи все искусственные переменные (yi) равны нулю, то это решение будет являться оптимальным решением Z-задачи.
2. Если в оптимальном решении М-задачи хотя бы одна из искусственных переменных отлична от нуля, то Z-задача не имеет решения по причине несовместности системы ограничений.
3. Если М-задача оказалась неразрешимой (Т или ), то исходная задача также неразрешима либо по причине несовместности системы ограничений, либо по причине неограниченности функции Z.
Составим первую симплексную табл. 3.9. При решении М-методом разрешающий столбец можно выбирать в М-строке не по наибольшей абсолютной величине отрицательной оценки (при решении на максимум) и не по наибольшей положительной оценке (при решении на минимум), а по той из них, которая быстрее выводит Уi из базиса. В данном примере разрешающим столбцом будет столбец свободной переменной X2 с оценкой (-3).
Таблица 3.9 Первая симплексная таблица
|
Св.П |
Cj |
0 |
4 |
2 |
1 |
0 |
ai0/aip |
|
|
Б.П. |
Ci |
ai0 |
X1 |
X2 |
X3 |
X4 |
||
|
У1 |
-М |
8 |
1 |
1 |
1 |
-1 |
8 |
|
|
X5 |
0 |
8 |
2 |
1 |
1 |
0 |
8 |
|
|
У2 |
-М |
15 |
3 |
(2) |
1 |
0 |
7,5 |
|
|
Z |
0 |
-4 |
-2 |
-1 |
0 |
|||
|
М |
-23 |
-4 |
-3 |
-2 |
1 |
Заполнение Z-строки осуществляется по формуле (2.1):
а00 = 0 8 - 0 = 0,
а01 = 0 2 - 4 = -4,
а02 = 0 1 - 2 = -2,
а03 = 0 1 - 1 = -1,
а04 = 0 0 - 0 = 0.
Заполнение М-строки:
а00 = -М 8 + (-М) 15 = -23М,
а01 = -М 1 + (-М) 3 = -4М,
а02 = -М 1 + (-М) 2 = -3М,
а03 = -М 1 + (-М) 1 = -2М,
а04 = -М (-1) + (-М) 0 = 1М.
М выносим как общий множитель.
В последнем столбце в разрешающей строке стоит 0, поэтому столбец свободной переменной X4 переносим без изменений.
Таблица 3.10 Вторая симплексная таблица
|
Св.П |
Cj |
0 |
4 |
1 |
0 |
||
|
Б.П. |
Ci |
ai0 |
X1 |
X3 |
X4 |
ai0/aip |
|
|
У1 |
-М |
1/2 |
-1/2 |
(1/2) |
-1 |
1 (-2) |
|
|
X5 |
0 |
1/2 |
1/2 |
1/2 |
0 |
1 (0) |
|
|
Х2 |
2 |
15/2 |
3/2 |
1/2 |
0 |
15 (0) |
|
|
Z |
15 |
-1 |
0 |
0 |
|||
|
М |
-1/2 |
1/2 |
-1/2 |
1 |
Во второй табл. 3.10 получаем вырожденное решение, так как получаются два одинаковых минимальных симплексных отношения. Поэтому находим отношения элементов столбца следующего за разрешающим к элементам разрешающего столбца с учетом знака (табл. 3.11).
Таблица 3.11 Третья симплексная таблица
|
Св.П |
Cj |
0 |
4 |
0 |
||
|
Б.П. |
Ci |
ai0 |
X1 |
X4 |
ai0/aip |
|
|
Х3 |
1 |
1 |
-1 |
-2 |
- |
|
|
X5 |
0 |
0 |
(1) |
1 |
0 |
|
|
Х2 |
2 |
7 |
2 |
1 |
3,5 |
|
|
Z |
15 |
-1 |
0 |
Теперь решаем обычным симплексным методом (табл. 3.12).
Таблица 3.12 Четвертая симплексная таблица
Подобные документы
Основы математического моделирования экономических процессов. Общая характеристика графического и симплексного методов решения прямой и двойственной задач линейного программирования. Особенности формулирования и методика решения транспортной задачи.
курсовая работа [313,2 K], добавлен 12.11.2010Теоретические основы моделирования оптимизационной программы развития сельскохозяйственной организации с учетом внешнеэкономических связей. Постановка экономико-математической задачи. Обоснование исходной информации и анализы оптимального решения.
курсовая работа [176,8 K], добавлен 06.05.2015Общая постановка задачи линейного программирования (ЛП). Приведение задачи ЛП к стандартной форме. Примеры экономических задач, приводящихся к задачам ЛП. Геометрический и симплексный методы решения. Теоремы двойственности и их использование в задачах ЛП.
курсовая работа [1,1 M], добавлен 21.11.2010Понятие и типы моделей. Этапы построения математической модели. Основы математического моделирования взаимосвязи экономических переменных. Определение параметров линейного однофакторного уравнения регрессии. Оптимизационные методы математики в экономике.
реферат [431,4 K], добавлен 11.02.2011Метод имитационного моделирования, его виды, основные этапы и особенности: статическое и динамическое представление моделируемой системы. Исследование практики использования методов имитационного моделирования в анализе экономических процессов и задач.
курсовая работа [54,3 K], добавлен 26.10.2014Основы и методы математического программирования. Дифференциальные и разностные уравнения. Классические задачи исследования операций. Алгоритмы симплекса-метода. Допустимые решения при поиске оптимального решения. Линейное и нелинейное программирование.
курсовая работа [183,7 K], добавлен 20.01.2011Понятие математического программирования как отрасли математики, являющейся теоретической основой решения задач о нахождении оптимальных решений. Основные этапы нахождения оптимальных решений экономических задач. Примеры задач линейного программирования.
учебное пособие [2,0 M], добавлен 15.06.2015Понятие экономико-математического моделирования. Совершенствование и развитие экономических систем. Сущность, особенности и компоненты имитационной модели. Исследование динамики экономического показателя на основе анализа одномерного временного ряда.
курсовая работа [451,4 K], добавлен 23.04.2013Потенциальная возможность математического моделирования любых экономических объектов и процессов. Методы минимизации, связанные с вычислением градиента. Суть метода градиентного спуска. Анализ симплекс-таблицы. Построение экономико-математической модели.
курсовая работа [998,7 K], добавлен 01.10.2011Изучение и отработка навыков математического моделирования стохастических процессов; исследование реальных моделей и систем с помощью двух типов моделей: аналитических и имитационных. Основные методы анализа: дисперсионный, корреляционный, регрессионный.
курсовая работа [701,2 K], добавлен 19.01.2016Применение методов оптимизации для решения конкретных производственных, экономических и управленческих задач с использованием количественного экономико-математического моделирования. Решение математической модели изучаемого объекта средствами Excel.
курсовая работа [3,8 M], добавлен 29.07.2013Характеристика трансформационных процессов в современной экономике. Особенности нового направления математического моделирования - экспериментальной экономики. Основные этапы проведения эксперимента для исследования динамики сложных экономических систем.
реферат [38,6 K], добавлен 14.12.2010Количественное обоснование управленческих решений по улучшению состояния экономических процессов методом математических моделей. Анализ оптимального решения задачи линейного программирования на чувствительность. Понятие многопараметрической оптимизации.
курсовая работа [4,2 M], добавлен 20.04.2015Основные задачи оценки экономических явлений и процессов. Проведение детерминированного факторного анализа и приемы математического моделирования факторной системы. Суть метода последовательного элиминирования факторов. Оперативный контроль затрат.
шпаргалка [1,1 M], добавлен 08.12.2010Основные подходы к математическому моделированию систем, применение имитационных или эвристических моделей экономической системы. Использование графического метода решения задачи линейного программирования для оптимизации программы выпуска продукции.
курсовая работа [270,4 K], добавлен 15.12.2014Методы исследования и моделирования социально-экономических систем. Этапы эконометрического моделирования и классификация эконометрических моделей. Задачи экономики и социологии труда как объект эконометрического моделирования и прогнозирования.
курсовая работа [701,5 K], добавлен 14.05.2015Основы понятия регрессионного анализа и математического моделирования. Численное решение краевых задач математической физики методом конечных разностей. Решение стандартных и оптимизационных задач, систем линейных уравнений. Метод конечных элементов.
реферат [227,1 K], добавлен 18.04.2015Основы моделирования, прямые и обратные задачи. Линейное программирование и методы решения задач: графический, симплекс-метод. Нахождение решения транспортных и распределительных задач. Теория массового обслуживания. Имитационное моделирование.
курс лекций [1,1 M], добавлен 01.09.2011Теоретические основы математического прогнозирования продвижения инвестиционных инструментов. Понятие системы имитационного моделирования. Этапы построения моделей экономических процессов. Характеристика ООО "Брянск-Капитал". Оценка адекватности модели.
курсовая работа [2,1 M], добавлен 20.11.2013Применение математического моделирования при решении прикладных инженерных задач. Оптимизация параметров технических систем. Использование программ LVMFlow для имитационного моделирования литейных процессов. Изготовление отливки, численное моделирование.
курсовая работа [4,0 M], добавлен 22.11.2012
