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

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

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

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

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

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

 

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

 

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

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

 

 

         Выполнила: студентка  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.