Оптимизация структуры посевных площадей

Министерство образования  и науки РФ

Министерство  сельского хозяйства РФ

Департамент научно-технической  политики и образования

Федеральное Государственное  образовательное учреждение высшего  профессионального образования

Иркутская Государственная  Сельскохозяйственная Академия

 

кафедра информатики  и                                                           математического моделирования

 

Курсовая работа

на тему: «Оптимизация структуры посевных площадей»

 

 

         Выполнила: студентка  4 курса

    заочного обучения

    специальности 080502.65

    Гришко А.С.

    Проверила:

    Вашукевич   Е.В.

 

Иркутск 2006

 

Содержание

 

         стр.

Введение                    3

1. Основные понятия   математического  программирования.  4

1.1. Постановка задачи линейного программирования    4

1.2. Задача оптимального  использования ресурсов.    7

1.3. Методы решения задач линейного программирования.   8

2. Построение модели  оптимизации структуры посевных   

площадей. 12

3. Анализ решения задачи.        14

Заключение                   15

Список используемой литературы.                16

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

Темой данной курсовой является «Оптимизация структуры посевных  площадей».

В колхозах и совхозах можно выделить несколько основных групп задач, правильное решение которых требует привлечения математических методов и использования электронно-вычислительной техники. Среди них задачи оптимизации растениеводства (расчет оптимальной структуры посевных площадей, оптимальных севооборотов, оптимального распределения средств химизации и др.)

Задачами написания  курсовой работы являются:

1. Изучить теоретический материал постановки задач оптимизации растениеводства.
2. Изучить методы решения задач.
3. Научиться строить оптимизационную модель.
4. Проанализировать решение задач.
5. Изучить специфику и особенности задачи расчета структуры посевных площадей.

Объектом исследования служит конкретное хозяйство. На примере этого хозяйства  решим конкретную задачу для получения  максимум прибыли от реализации продукции.

 

 

 

 

 

 

 

 

 

1. Основные понятия   математического  программирования

 

1.1. Постановка  задачи линейного программирования 

 

Линейное программирование – это частный раздел оптимального программирования. В свою очередь  оптимальное (математическое) программирование – раздел прикладной математики, изучающий задачи условной и безусловной оптимизации. В экономике такие задачи возникают при практической реализации принципа оптимальности в планировании  управлении.

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

В самом общем виде задача математически  записывается так:

 

             U = f(X) → max; X Є W ,   (1)                

где Х =  ( х₁, х₂,…,х_n);

      W – область допустимых  значений переменных х₁, х₂,…, х_n;

      f(X) – целевая функция.

Для того чтобы решить задачу оптимизации, достаточно найти  ее оптимальное решение, т.е. Х₀ Î W такое, что f (X₀) ³ f (X)  при любом Х Î W, или для случая минимизации – f (X₀) £ f (X) при любом Х Î W.

Оптимизационная задача является неразрешимой, если она не имеет оптимального решения. В частности, задача максимизации будет  неразрешима, если целевая функция f(X) не огрничена сверху на допустимом множестве W.

Методы решения оптимизационных  задач зависят как от вида целевой  функции  f (X), так и от строения допустимого множества W. Если целевая  функция в задаче является в функции n  переменных, то методы решения  называют методами математического программирования.

В математическом программировании принято выделять следующие основные задачи в зависимости  от вида целевой функции  f (X)  и  от области W:

• задачи  линейного программирования, если f (X) и W  линейны;
• задачи целочисленного программирования, если ставится условие целочисленности переменных х₁, х₂,…, х_n;
• задачи нелинейного программирования, если форма f (X) носит нелинейный характер.

Задачей линейного программирования называется задача исследования операций, математическая модель которой имеет вид:

 

                       f(X) = ∑c_jx_j → max (min)        (2)

 

            ∑ a_ij x_j = b_i,    i Î I,  I Í М = {1,2,…,m};  (3)

     

 ∑ a_ij x_i £ b_i, i Î M;    (4)

 

                         x_j ³ 0, j Î J,  J Í N = {1, 2,…, n}.   (5)

 

При этом система линейных уравнений (3) и неравенств (4), (5), определяющая допустимое множество решений задачи W, называется системой ограничений задачи линейного программирования, а линейная функция f(X) называется целевой функцией или критерием оптимальности.

В частом случае, если I = Ø, то система (3)- (4) состоит только из линейных неравенств, а если I = M, то - из линейных уравнений.

Если математическая модель задачи линейного программирования имеет  вид:

 

    f(X) = ∑ c_j * x_j → min    (6)

 

∑ a_ij * x_j = b_i, I = 1,m    (7)

 

b_i ≥ 0;

 

     x_j ≥ 0, j = 1,n     (8)

то говорят, что задача представлена в канонической форме.

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

Правило приведения задачи линейного программирования к каноническому виду состоит  в следующем:

1) если в исходной  задаче требуется определить  максимум линейной функции, то  следует изменить знак и искать минимум этой функции;

2) если в ограничениях  правая часть отрицательна, то  следует умножить это ограничение  на -1;

3) если среди ограничений  имеются равенства, то путем  введения дополнительных неотрицательных  переменных они преобразуются в равенства;

4) если некоторая переменная  х_к не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными х_к = х’_k – x_l, где l -  свободный индекс, x’_k ≥ 0, x_l ≥ 0. 

 

1.2. Задача оптимального  использования ресурсов.

 

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

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

 

 

 

 

 

 

 

1.3. Методы решения  задач линейного программирования.

 

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

Симплексный метод решения задачи линейного программирования основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает (при условии, что данная задача имеет оптимальный план и каждый ее опорный план является невырожденным). Указанный переход возможен, если известен какой – нибудь исходный опорный план. Рассмотрим этот метод на примере: Пусть требуется найти максимальное значение функции

F = c₁х₁ + с₂х₂ +…+ с_nx_n

при  условиях

х₁ + a_1m+1 + x_m+1 +…+ a_1nx_n = b₁

х₂ + a_2m+1 + x_m+1 +…+ a_2nx_n = b₂

……………………………………..

х_m + a_mm+1 + x_m+1 +…+ a_mnx_n = b_m

x_j ³ 0 (j = 1,n)

 Здесь a_ij, b_i и c_j; j = 1,n – заданные постоянные числа (m<n и

b_i > 0).

 Векторная форма задачи имеет следующий вид: найти максимум функции

                            F = å c_jx_j.

  Алгоритм решения этой задачи  состоит в следующем:

1. Определить разрешающий элемент в столбцах, где коэффициенты целевой функции являются отрицательными.
2. После определения разрешающего элемента, определяем элементы разрешающей строки.
3. Определяем элементы разрешающего столбца.
4. Определяем остальные элементы симплекс – таблицы.

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

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

Столбец и строка на пересечении  которых имеется разрешающий элемент называется разрешающей строкой (столбцом). Другие элементы таблицы называются остальными элементами.

Суть симплекс-метода  состоит в переборе решений соответствующих  вариантов выпуклого множества.

Метод искусственного базиса. Как показано выше, для задачи, записанной в форме основной задачи линейного программирования, можно непосредственно указать ее опорный план, если среди векторов (P_j), компонентами которых служат коэффициенты при неизвестных в системе уравнений имеется m- единичных.

Рассмотрим пример такой  задачи:

Пусть требуется найти  максимум функции:

F = c₁x₁+c₂x₂+…+c_nx_n

при  условиях

 

a₁₁ + a₁₂x₂ +…+ a_1nx_n = b₁

a₁₂ + a₂₂x₂ +…+ a_2nx_n = b₂

……………………………………..

a_m1x₁ + a_m2x₂ +…+ a_mnx_n = b_m,

x_j ³ 0 (j = 1,n)

где  b_i ³ 0; i = 1,m, m<n и среди векторов нет m – единичных.

Процесс нахождения решения  задачи метод искусственного базиса включает такие  основные этапы:

1. Составляют расширенную  задачу.

2. Находят опорный  план расширенной задачи.

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

4.  используя опорный  план задачи находят симплекс  – методом оптимальный план  исходной задачи либо устанавливают  ее неразрешимость.

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

Эта необходимость отпадает при решении задач линейного  программирования модифицированным симплекс – методом.

Он включает следующие  этапы:

1. Находят опорный  план задачи.

2. Вычисляют матрицу  B^-1 , обратную матрицу B, составленной из компонент векторов исходного базиса.

3. Находят вектор W = Сd B^-1

4. Вычисляют числа D_j = W P_j-c_j.  Если все D_j не отрицательны, то исследуемый опорный план является оптимальным. Если же среди чисел D_j имеются отрицательные, то выбирают среди них наибольшие по абсолютной величине. Пусть это Ds.

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

6. по известным правилам  симплекс - метода находят разрешающую  строку и вычисляют положительные  компоненты нового опорного плана,  а также матрицу B^-1, обратную матрице В, составленной из компонент векторов нового базиса.

7. Проверяют новый  опорный план на оптимальность  и  в случае необходимости  проводят вычисления начиная  с третьего этапа.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Построение  модели оптимизации структуры посевных площадей.

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

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

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

 Для того чтобы  понять важность и назначение  такой задачи, рассмотрим пример:

В хозяйстве возделывается  озимая пшеница, сахарная свекла, однолетние травы. Хозяйство может выделить для их выращивания 2000 га пашни, 12000 человеко – дней трудовых ресурсов.

Урожай озимой пшеницы  запланирован на уровне 20 ц с 1 га, сахарной свеклы – 250 ц и однолетних трав – 25 ц. Средняя цена реализации 1 ц пшеницы  – 5 руб., 1 ц сахарной свеклы – 17 руб., 1 ц кормовых единиц – 3 руб.

На основании условий  задачи необходимо:

а) построить матрицу  задачи;

б) записать данную задачу в виде неравенств;

в) превратить неравенства  в уравнения;

г) решить задачу по критерию максимальное количество прибыли в  денежном  выражении;

д) произвести анализ решения задачи.

Для решения данной задачи используем следующие исходные данные:

Таблица 1.

Затраты труда и себестоимость 1 ц продукции.

Показатели	Озимая пшеница	Овощи	Однолетние травы
Затраты труда (человеко-часы)	4	8	1
Себестоимость (руб.)	3,5	17	0,4

 

Х₁- озимая пшеница;

Х₂- сахарная свекла;

Х₃- однолетние травы.

Целевая функция по максимизации прибыли  равна:

20х₁ + 500х₂ + 65х₃ ® max

ограничения  на использование  площади пашни

                х₁ + х₂ + х₃ £  2000

ограничения по затратам трудовых ресурсов

4х₁ + 8х₂ +2х₃ £ 12000

 

                   

 

 

Заключение

 

В планово-экономической практике наиболее разработаны и распространены методы, обеспечивающие решение задач, относящихся к классу линейного  программирования. Под методами линейного программирования понимают такие программы математических действий, которые позволяют отыскивать оптимальные решения различных экономических задач, условия которых выражены (сформулированы) в виде системы линейных уравнений и неравенств, а целевая установка – в виде  линейной функции.

Методы решения задач  линейного программирования объединяют ряд алгоритмов. Из них наиболее часто используют алгоритм метода последовательного  улучшения плана (симплекс-метод) и  распределительного метода.

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

 

 

 

 

 

 

 

 

 

 

 

Список используемой литературы

 

1.  Акулич И.Л. Математическое  программирование в примерах и задачах. М.: Высшая школа, 1993. – 336с.

2. Бережная Е.В., Бережной  В.И. Математические методы моделирования  экономических систем: Учебное пособие.  М.: Финансы и статистика, 2002. с. 187-250

3. Кравченко Р.Г. Математическое  моделирование экономических процессов в сельском хозяйстве. М.: Колос, 1978. 424с.

4.  Математическое  моделирование экономических процессов  в сельском хозяйстве/ А.М. Гатаулин, Г.В Гаврилов,                           Т.М. Сорокина, и др. М.: Агропромиздат  1990. 432с.

5. Практикум по математическому моделированию экономических процессов в сельском хозяйстве/ А.Ф. Карпенко, В.А. Кардаш, Н.С. Низова и др. М.: Финансы и статистика, 1985. 269с.

6. Сергованцев В.Т., Бледных В.В.  Вычислительная техника в инженерных  и экономических  расчетах  М.: Финансы и статистика, 1988. с 156-200.

7. Шпак Т.А. Особенности моделирования  машинно-тракторного парка в отдельных  районах промышленной зоны// Материалы  научно-практической конференции,  посвященной 70-летию образования  ИрГСХА, Иркутск, 2004 с. 146-149.

8. Экономико-математические методы  и прикладные модели: Учебное  пособие для ВУЗов/ В.В. Федосеев, А.Н. Гармаш,         Д.М. Дайитбеков и др. М.: ЮНИТИ, 1999 с 20-30, 49-66.