Моделирование оптимизационных экономико-математических задач линейного вида в компьютерной среде EXCEL

Министерство образования Республики Беларусь

Учреждение образования:

«Гомельский государственный технический университет имени П.О.Сухого»

Кафедра «Экономика и управление в отраслях»

КУРСОВАЯ РАБОТА

по предмету «Экономико-математические методы и модели»

НА ТЕМУ:

Моделирование оптимизационных экономико-математических за­дач линейного вида в компьютерной среде EXCEL.

Выполнил:

Студент гр. МТ-32

Повалко Д.В.

Проверил:

Голубцов Б.И.

Гомель 2009

4

Содержание

Введение………………………………………………………………………….3

Глава 1. Общая характеристика задач линейного программирования .….….4

Глава 2. Решение задачи линейного вида в компьютерной среде EXCEL.…13

Заключение…………………………………………………………………….…

Список использованной литературы…………………………………………...

Введение

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

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

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

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

1.      Изучение сущности задач линейного программирования;

2.      Использование компьютерной среды EXCEL при решении экономико-математических за­дач линейного вида;

Данная курсовая работа состоит из двух глав. В первой главе дается краткое описание задач линейного программирования. Во второй главе приведено решение задачи линейного вида в компьютерной среде EXCEL.

Для написания курсовой работы были использованы литературные источники, статьи журналов.

Глава 1. Общая характеристика задач линейного программирования

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

Отличительными признаками оптимизационных моделей являются:

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

-  система ограничений, которая формируется, исходя из содержа­тельной постановки задачи, и представляет собой систему уравнений или неравенств.

Математически эти задачи относятся к задачам на условный экс­тремум. Постановка таких задач, представленных в общем виде, вы­глядит следующим образом:

      найти условный максимум (или минимум) функции:

F=f(х1, х2,...,хn) -> тах(min);                                                         (1.1)

      при условии, что независимые переменные удовлетворяют ограниче­ниям:

G(х1, х2,,.., хn) = 0.                                                          (1.2)

Эта задача является задачей на условный локальный максимум или минимум. Термин «условный» появляется в данном случае в связи с тем, что независимые переменные удовлетворяют условию - системе ограничений (1.2). Обычно вместо двух терминов «максимум и ми­нимум» используют один - экстремум. В задаче на условный экстре­мум функцию F=f(х1, х2,...,хn) называют целевой, так как ее макси­мизация или минимизация часто есть формальное выражение какой-либо цели (например, максимизация объема производства продукции при фиксированных затратах).

Функцию G называют функцией, задающей ограничения.

Если в задаче на условный экстремум ограничения в виде системы уравнений G(х1, х2,,.., хn) = 0 заменить на ограничения в виде систе­мы неравенств и добавить требования (ограничения) неотрицательно­сти переменных х1 ≥ 0, х2 ≥ 0, ... , хn ≥ 0, то получим задачу математи­ческого программирования, в которой необходимо:

      найти экстремум функции

f(х1, х2,...,хn) -> тах(min);                                                                 (1.3)

      при условии, что независимые переменные удовлетворяют систе­мам ограничений

g1(х1, х2,...,хn)≤0,

                                                                                      ... ... ...                                                                                             (1.4)

gт(х1,х2,...,хп)≤0,

    х1≥0,х2≥0,...,хп≥0.                                                                                 (1.5)

В задаче математического программирования функцию f(х1, х2,...,хn) также называют целевой функцией; систему неравенств (1.4) -специальными ограничениями задачи математического программиро­вания, а неравенства (1.5) — общими ограничениями задачи линейного программирования.

Задача линейного программирования - частный случай задачи математического программирования, в которой целевая функция и ограничения являются линейными.

Именно этот класс оптимизационных моделей наиболее широко применяется в экономике.

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

Общая форма задачи линейного программирования

Задана система т линейных уравнений с п переменными:

a11x1+a12x2+…+a1nxn ≤ b1,

a21x1+a22x2+…+a2nxn ≤ b2,

a31x1+a32x2+…+a3nxn ≤ b3,

…… …                                                                             (1.6)

ak1x1+ak2x2+…+aknxn ≤ bk,

ak+1,1x1+ak+1,2x2+…+ak+1,nxn = bk+1,

ak+2,1x1+ak+2,2x2+…+ak+2,nxn = bk+2,

… … …                                                                            (1.7)

am1x1+am2x2+…+amnxn = bm;

а линейная функция:

F = с1x1 + с2x2 + с3xз + ... + сnxn ->max(min)                                                  (1.8)

Необходимо найти такой вектор X = (х1, х2, x3, ... , xn), который удовлетворяет ограничениям (1. 6) и (1.7) и при котором линейная функции F принимает максимальное (или минимальное) значение.

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

Более кратко задачу линейного программирования в общей форме можно представить в следующем виде:

                                 n

F = ∑cjxj -> max(min),                                                       (1.9)

                                             J=1

                               n

∑ajjxj ≤ bi (i=1, … ,k),                                                           (1.10)

                              J=1

                 n

∑ajjxj = bi (i=k+1, k+2, … ,m),                                                           (1.11)

             J=1

xj>0, где(j=1, ... ,n).                                                                 (1.12)

Оптимальным решением (или оптимальным планом) задачи линей­ного программирования называется решение X* =(х1*,х2*, ... ,хп*), удовле­творяющее системам ограничений (1.10)—(1.12), при которых линей­ная функция F достигает экстремального значения (минимума или максимума).

Термины «решение» или «план» - синонимы, однако первый ис­пользуется чаще, когда речь идет о формализованной постановке зада­чи, а второй - о содержательной.

Стандартная форма задачи линейного программирования

Задача линейного программирования, представленная в форме:

a11x1+a12x2+…+a1nxn ≤ b1,

a21x1+a22x2+…+a2nxn ≤ b2,

a31x1+a32x2+…+a3nxn ≤ b3,

… … …                                                                          (1.13)

am1x1+am2x2+…+amnxn ≤ bm,

xj ≥ 0, где(j=1, ... ,n).

а линейная функция:

F = с1x1 + с2х2 + с3х3 + ... + сnхn -> mах (min),                                                (1.14)

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

Особенность данной формы заключается в том, что в ней система как функциональных, так и прямых ограничений состоит из одних не­равенств, переменные хj> 0, (где j = 1, ... , п) являются неотрицатель­ными, а целевая функция может стремиться как к минимуму, так и к максимуму.

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

Форма, в которой:

F = с1x1 + с2х2 + с3х3 + ... + сnхn -> mах                                                                  (1.15)

a11x1+a12x2+…+a1nxn = b1,

a21x1+a22x2+…+a2nxn = b2,

a31x1+a32x2+…+a3nxn = b3,

… … …                                                                          (1.16)

am1x1+am2x2+…+amnxn = bm,

xj ≥ 0, где(j=1, ... ,n).                                                                          (1.17)

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

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

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

Рассмотрим два частных вида задач линейного программирования. Одна

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

моделью:

                                                         (1.18)

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

После приведения к канонической форме задача (1.18) будет иметь вид:

                           (1.19)

.

Переменные xn+1, хn+2,…, хn+m называются дополнительными.

Рассмотрим другой частный вид задачи линейного программирования:

                                                         (1.20)

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

Для приведения ограничений вида “” к ограничениям-равенствам необходимо из левой части каждого ограничения вычесть соответственно неотрицательные переменные xn+1, xn+2,…, xn+m. Эти переменные вводятся в целевую функцию с нулевыми коэффициентами, чтобы не изменить ее значение.