Моделирование оптимизационных экономико-математических задач линейного вида в компьютерной среде 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. Эти переменные вводятся в целевую функцию с нулевыми коэффициентами, чтобы не изменить ее значение.

                                  (1.21)

Таким образом, если в задаче линейного программирования определяется минимум целевой функции, то такую задачу необходимо свести к определению максимума целевой функции, а все имеющиеся ограничения вида “” и “” привести к ограничениям-равенствам [8, стр.63].

В ограничениях задачи (1.18) все переменные можно разделить на две группы. Первая группа – основные (зависимые) переменные, число которых должно быть равно числу линейно независимых уравнений m, вторая – неосновные (независимые) переменные, число которых будет равно (n-m). Такое разделение не связывается с индексами (порядковыми номерами) переменных. Будем считать, что ограничения задачи (1.18), записанной в канонической форме путем последовательных элементарных преобразований могут быть приведены к виду:

                                                                          (1.22)

где .

В системе (1.11) коэффициенты при каждом неизвестном х1, х2,…, xm образуют единичные векторы

    …,

Совокупность единичных векторов Е1, Е2,...,Еm образует базис m-мерного пространства, а переменные х1, x2,...,xm называются базисными. Переменная является базисной, если она входит только в одно из уравнений системы с коэффициентом, равным единице. Все остальные переменные являются небазисными.

Частное решение, полученное путем приравнивания небазисных (независимых) переменных нулю и нахождения значений базисных (зависимых) переменных, называется базисным решением. Следовательно, если xm+1=0, хm+2=0,..., хn=0, то x1=, . Первое решение задачи, полученное таким образом, называется исходным базисным решением.

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

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

После приведения частной задачи, имеющей ограничения “” (1.18), к канонической форме (1.19) каждое уравнение будет содержать базисную переменную, а именно хn+1. хn+2,..., xn+m. Приравняв небазисные переменные к нулю: x1=0, x2=0,…,xn=0, получим допустимое базисное решение:

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

В каждое ограничение задачи (1.20) вводятся соответственно искусственные неотрицательные переменные хn+m+1, xn+m+2,…, xn+m+m, которые принимаются в качестве базисных. Искусственные переменные входят в целевую функцию задачи с коэффициентом М, где М – большое положительное число, во много раз больше заданных в условии задачи. В целевую функцию приписывают для задач максимизации очень большие по модулю отрицательные коэффициенты (-М), где M>ci, (i = 1, 2, ..,m).

В случае решения задач минимизаци искусственные переменные вводят в целевую функцию с большими положительными коэффициентами (+М).

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

Классификация задач оптимизации:

      Задача о рациональном питании (задача о пищевом рационе);

      Задача о планировании производства;

      Задача о загрузки оборудования;

      Задача о снабжении сырьём;

      Определение оптимального ассортимента;

      Оптимальное распределение взаимозаменяемых ресурсов;

      Задача о смесях;

      Задача о раскрое материалов;

      Оптимальные балансовые модели;

      Задача о диете;

      Задача о раскрое и т.д.

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

ПОСТАНОВКА ЗАДАЧИ:

              Предприятие производит две модели-А и В-сборных книжных полок. Их производство ограничено наличием сырья (высококачественных досок) и временем машинной обработки. Для каждого изделия модели А требуется 3м2 досок, для изделия В требуется 4 м2. Предприятие может получить от своих поставщиков до 1700 м2 досок в неделю. Для каждого изделия модели А требуется 12 минут машинного времени, модели В – 30 минут. В неделю можно использовать 160 часов машинного времени. Сколько изделий каждой модели следует предприятию выпускать в неделю, если каждое изделие модели А приносит 2 рубля прибыли, а каждое изделие модели В – 4 рубля прибыли?

Построение математической модели

              Обозначим через x1 количество, планируемое к выпуску за неделю полок модели А, а через x2 – количество, планируемое к выпуску модели В. Задача состоит  том, чтобы найти значения x1и x2, при которых полученная прибыль будет наибольшей. Согласно условиям задачи это прибыль Z выражается формулой

Z=2* x1+4* x2

              Поскольку x1 и x2 выражают еженедельный объем выпускаемых изделий, они не могут быть отрицательными, т.е.

                                          x1≥0; x2 ≥0;

              Теперь ограничение на наличие досок и машинного времени могут быть записаны так:

                                          3* x1+4*x2 ≤1700

                                          0,2*x1+0,5*x2 ≤160

              Отметим, что 12мин.=1/5ч, 30мин.=1/2ч.

Итак, задача состоит в том, чтобы найти значения x1 и x2, удовлетворяющие условиям неотрицательности и ограничением типа неравенств и максимизирующие прибыль Z. В результате получим следующую математическую модель:

Максимизировать функцию

Z=2*x1+4* x2

При ограничениях

     3*x1+4*x2 ≤1700;

2*x1+5*x2 ≤160;

x1≥0, x2 ≥0

Решение задачи

1.      Заполняем таблицу:

2. Выбираем меню Сервис, пункт Поиск решения программы Excel. Появляется следующее окно:

В нем устанавливаем целевую ячейку $D$6, равную максимальному значению. Изменяемые ячейки: $B$8:$B$9. Эти значения Поиск решения будет подбирать. Всего можно указать до 200  изменяемых ячеек.

Oграничения  в окно добавляем с помощью кнопки «Добавить»:

$D$8<=$D$3

$D$9<=$D$4

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

Чтобы указать значение «больше либо равно нулю»  для переменных, следует нажать на кнопку «Параметры» и в появившемся окне выбрать «Неотрицательные значения».

Для получения решения выбираем кнопку «Выполнить» и получаем:

Используемые формулы для целевой функции: =B6*B8+C6*B9

Для ограничений:

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

АНАЛИЗ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ И СОСТАВЛЕНИЕ ОТЧЕТА

По полученному решению составляется отчет: