Решение оптимизационных задач средствами EXCEL

 

 

 

 

 

 

КАФЕДРА ЭКОНОМИКО-МАТЕМАТИЧЕСКИХ МЕТОДОВ  И МОДЕЛЕЙ

 

Орлова И. В., Орлов П.В.

 

 

 

 

 

 

 

Решение оптимизационных  задач средствами EXCEL.

Краткий конспект  лекций  и лабораторная работа  № 1 по курсу  «Экономико-математические методы и  прикладные модели»

 

 

 

 

 

 

 

 

 

 

 

 

 

Москва 

2001 г.

 

Оглавление

 

 

 

 

 решение систем линейных уравнений 
методом жордана  - гаусса

 

Пример 1.     Решить методом Жордана-Гаусса систему линейных уравнений:

            а)  Х₁ + Х₂ + 2Х₃ = -1

               2Х₁ -  Х₂ + 2Х₃ = -4

               4Х₁ + Х₂ + 4Х₃ = -2

 

Решение:

 Составим расширенную матрицу

1 Итерация.

В качестве направляющего  элемента выбираем элемент  . Преобразуем первый столбец в единичный. Для этого к второй и третьей строкам прибавляем первую строку, соответственно умноженную на -2  и -4. Получим матрицу:

На этом первая итерация закончена.

2 Итерация.

Выбираем направляющий элемент  . Так как , то делим вторую строку на -3. Затем умножаем вторую строку на 1 и 3 и складываем соответственно с первой и третьей строками. Получим матрицу:

3 Итерация.

Выбираем направляющий элемент . Так как , то делим третью строку на -2. Преобразуем третий столбец в единичный. Для этого умножаем третью строку на -4/3 и -2/3 и складываем соответственно с первой и второй строками. Получим матрицу:

откуда Х₁ = 1,  Х₂ = 2,  Х₃ = -2.

 

Пример 2. Решить методом Жордана - Гаусса систему линейных уравнений:

              Х₁ + 2Х₂ + 2Х₃ +22Х₄ –4Х₅= 11

              Х₁ +2Х₂ + Х₃ +16Х₄–4Х₅= 9

              Х₁ + Х₂ + Х₃ +12Х₄ -2Х₅= 6

 

Решение:

Составим расширенную матрицу

 

1 Итерация.

В качестве направляющего элемента выбираем элемент  . Преобразуем первый столбец в единичный. Для этого ко второй и третьей строкам прибавляем первую строку, соответственно умноженную на -1. Получим матрицу:

На этом первая итерация закончена.

2 Итерация.

Выбираем направляющий элемент  . Умножаем  третью строку на -1. Преобразуем второй столбец в единичный. Для этого к первой строке прибавляем третью строку, соответственно умноженную на -2.

Получим матрицу:

3 Итерация.

Выбираем направляющий элемент  . Так как , то умножаем вторую строку на –1. Преобразуем третий столбец в единичный. Для этого вторую строку складываем  с третьей строкой. Получим матрицу:

 

	Х1	Х2	Х3	Х4	Х5
	1	2	2	22	-4	1	0	0	11
	1	2	1	16	-4	0	1	0	9
	1	1	1	12	-2	0	0	1	6
	1	2	2	22	-4	1	0	0	11
1	0	0	-1	-6	0	-1	1	0	-2
	0	-1	-1	-10	2	-1	0	1	-5
	1	0	0	2	0	-1	0	2	1
2	0	0	-1	-6	0	-1	1	0	-2
	0	1	1	10	-2	1	0	-1	5
	1	0	0	2	0	-1	0	2	1
3	0	0	1	6	0	1	-1	0	2
	0	1	0	4	-2	0	1	-1	3
	1	0	0	2	0	-1	0	2	1
	0	1	0	4	-2	0	1	-1	3
	0	0	1	6	0	1	-1	0	2

 

Исходная система эквивалентна следующей системе уравнений:

                Х₁ + 2Х₄ = 1

                Х₂ +4Х₄ -2Х₅= 3

                Х₃ +6Х₄= 2

Система уравнений имеет  бесконечное множество решений.

             Общее решение имеет вид:

             Х₁ =  1-2Х₄

                    Х₂ = 3-4Х₄ +2Х₅

             Х₃ = 2-6Х_4.

      переменные Х₁, Х_2, Х₃ являются основными (или базисными). Любое частное решение получается из общего путем придания конкретных значений свободным переменным. Если свободные переменные Х₄ и Х₅ положить равными нулю, то получим первое базисное решение Х₁ =  1,      Х₂ = 3,   Х₃ = 2, Х₄ = 0,   Х₅=0.

Первое базисное решение  имеет вид: (1,3,2,0,0).

Общее число  групп основных переменных, т.е. базисных решений не более, чем = = .

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

Общая задача оптимизации

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

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

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

В общем виде математическая постановка задачи математического программирования состоит в определении наибольшего или наименьшего значения целевой функции f (х₁, х₂, ..., х_n) при условиях g_i(х₁, х₂, ..., х_n) £ b_i;  (i =1,2,…m), где f и g_i; – заданные функции, а b_i – некоторые действительные числа. 

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

В общем виде задача линейного программирования (ЗЛП) ставится следующим образом:

Найти вектор , максимизирующий линейную форму

                           (1)

и удовлетворяющий условиям

                        (2)

                   (3)

Линейная функция  называется целевой функцией задачи. Условия (2)  называются функциональными, а (3) - прямыми ограничениями задачи.

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

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

,

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

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

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

 

Наиболее простым и  наглядным  методом линейного программирования (ЛП) является графический метод. Он применяется для решения задач  ЛП с двумя переменными.

Рассмотрим задачу ЛП в стандартной  форме записи:

                

                         

Положим n=2, т.е. рассмотрим эту задачу на плоскости. Пусть система неравенств совместна (имеет хотя бы одно решение).

Каждое неравенство этой системы  геометрически определяет полуплоскость  с граничной прямой  a_i1 x₁ + a_i2 x₂  =  b_i   , i=1,2,…m. Условия неотрицательности определяют полуплоскости, соответственно, с граничными прямыми x1=0,x2 =0. Система совместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых являются решением данной системы. Совокупность этих точек называют многоугольником решений. Он может быть точкой, отрезком, лучом, многоугольником, неограниченной многоугольной областью.

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

           Линейное  уравнение описывает множество  точек, лежащих на одной прямой. Линейное неравенство описывает  некоторую область на плоскости.  Определим, какую часть плоскости описывает неравенство 2х₁+3х₂£ 12.  Во-первых, построим прямую 2х₁+3х₂=12.  Эта прямая проходит через точки (6, 0) и (0, 4).  Для того чтобы определить, какая полуплоскость удовлетворяет неравенству необходимо выбрать любую точку на графике, не принадлежащую прямой, и подставить ее координаты в неравенство. Если неравенство будет выполняться, то данная точка является допустимым решением и полуплоскость, содержащая точку, удовлетворяет

неравенству. Удобной для использования при подстановке в неравенство является начало координат. Подставим х₁=х₂=0 в неравенство 2х₁+3х₂£12. Получим 2´0+3´0£12.  Данное утверждение является верным, следовательно, неравенству 2х₁+3х₂£12 соответствует нижняя полуплоскость, содержащая точку (0.0). Это отражено на графике, изображенном на рис.1.

 

 

Рис. 1.  Неравенству 2х₁+3х₂£12 соответствует нижняя полуплоскость.

 

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

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