Главная Коллекция "Revolution" Программирование, компьютеры и кибернетика Решение оптимизационных задач средствами EXCEL

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

Решение систем линейных уравнений формулами Жордана-Гаусса. Графический и симплексный методы для задач линейного программирования. Технология решения с помощью поиска решений в среде EXCEL. Характеристика двойственности и анализ оптимальных решений.

Рубрика Программирование, компьютеры и кибернетика
Вид лабораторная работа
Язык русский
Дата добавления 03.12.2012
Размер файла 1,8 M
рефераты на заказ со скидкой

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Страница:

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Кафедра экономико-математических методов и моделей

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

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

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

Москва 2001 г.

Оглавление

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

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

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

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

5. Технология решения задач линейного программирования с помощью поиска решений в среде EXCEL

6. Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений

7. Задания к контрольной работе

7.1 Задача 1

7.2 Задача 2

Список литературы, имеющейся в библиотеке ВЗФЭИ

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

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

а) Х1 + Х2 + 2Х3 = -1

2Х1 - Х2 + 2Х3 = -4

4Х1 + Х2 + 4Х3 = -2

Решение:

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

1. Итерация.

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

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

2. Итерация.

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

3. Итерация.

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

откуда Х1 = 1, Х2 = 2, Х3 = -2.

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

Х1 + 2Х2 + 2Х3 +22Х4 -4Х5= 11

Х1 +2Х2 + Х3 +16Х4-4Х5= 9

Х1 + Х2 + Х3 +12Х4 -2Х5= 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

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

Х1 + 2Х4 = 1

Х2 +4Х4 -2Х5= 3

Х3 +6Х4= 2

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

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

Х1 = 1-2Х4

Х2 = 3-4Х4 +2Х5

Х3 = 2-6Х4.

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

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

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

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

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

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

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

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

В общем виде математическая постановка задачи математического программирования состоит в определении наибольшего или наименьшего значения целевой функции f (х1, х2, ..., хn) при условиях gi(х1, х2, ..., хn) bi; (i =1,2,…m), где f и gi; - заданные функции, а bi - некоторые действительные числа.

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

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

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

(1)

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

(2)

(3)

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

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

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

,

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

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

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

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

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

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

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

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

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

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

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

Решением каждого неравенства системы ограничений ЗЛП является полуплоскость, содержащая граничную прямую и расположенная по одну сторону от нее. Пересечение полуплоскостей, каждая из которых определяется соответствующим неравенством системы, называется областью допустимых решений или областью определения. Необходимо помнить, что область допустимых решений удовлетворяет условиям неотрицательности (xj 0, j=1,…,n). Координаты любой точки, принадлежащей области определения являются допустимым решением задачи.

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

.

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

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

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

Графический метод решения ЗЛП состоит из следующих этапов.

Строится многоугольная область допустимых решений ЗЛП - ОДР,

Строится вектор-градиент ЦФ в какой-нибудь точке Х0 принадлежащей ОДР - .

3. Линия уровня C1x1+C2x2 = а (а-постоянная величина) - прямая, перпендикулярная вектору -градиенту - передвигается в направлении этого вектора в случае максимизации f(x1,x2) до тех пор, пока не покинет пределов ОДР. Предельная точка (или точки) области при этом движении и является точкой максимума f(x1,x2).

4. Для нахождения ее координат достаточно решить два уравнения прямых, получаемых из соответствующих ограничений и дающих в пересечении точку максимума. Значение f(x1,x2), найденное в получаемой точке, является максимальным.

При минимизации f(x1,x2) линия уровня перемещается в направлении, противоположном вектору-градиенту. Если прямая при своем движении не покидает ОДР, то соответствующий максимум или минимум f(x1,x2) не существует.

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

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

Задача 1. о планировании выпуска продукции пошивочному предприятию. (Задача о костюмах).

Намечается выпуск двух видов костюмов - мужских и женских. На женский костюм требуется 1 м шерсти, 2 м лавсана и 1 человеко-день трудозатрат. На мужской костюм - 3,5 м шерсти, 0,5 м лавсана и 1 человеко-день трудозатрат. Всего имеется 350 м шерсти, 240 м лавсана и 150 человеко-дней трудозатрат. Tребуется определить, сколько костюмов каждого вида необходимо сшить, чтобы обеспечить максимальную прибыль, если прибыль от реализации женского костюма составляет 10 денежных единиц, а от мужского - 20 денежных единиц. При этом следует иметь в виду, что необходимо сшить не менее 60 мужских костюмов.

Модель задачи.

Введем следующие обозначения: х1 - число женских костюмов; x2 - число мужских костюмов.

Прибыль от реализации женских костюмов составляет 10х1, а от реализации мужских 20х2, т.е. необходимо максимизировать целевую функцию: f(x) = 10 х1 + 20 х2 -> max.

Ограничения задачи имеют вид:

х1 + х2 150

2 х1 + 0.5 х2 240

х1 + 3.5 х2 350

х2 60

х1 0

Первое ограничение по труду х1 + х2 150. Прямая х1 + х2 = 150 проходит через точки (150, 0) и (0, 150).

Рис. 2 Решением первого неравенства является нижняя полуплоскость

Второе ограничение по лавсану 2 х1 + 0.5 х2 240. Прямая 2 х1 + 0.5 х2 = 240 проходит через точки (120, 0) и (0, 480). Третье ограничение по шерсти х1 + 3.5 х2 350. Добавим четвертое ограничение по количеству мужских костюмов х2 60. Решением этого неравенства является полуплоскость, лежащая выше прямой х2 = 60. На рис.3. заштрихована область допустимых решений.

Рис. 3 Заштрихована область допустимых решений

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

= (10;20).

Что бы построить этот вектор, нужно соединить точку (10;20) с началом координат. При максимизации целевой функции необходимо двигаться в направлении вектора-градиента, а при минимизации -- в противоположном направлении. Для удобства можно строить вектор, пропорциональный вектору . Так, на рис. 2.1.6. изображен вектор градиент (30;60).

Рис.4. Максимум целевой функции достигается в точке (70, 80)

В нашем случае движение линии уровня будем осуществлять до ее выхода из области допустимых решений. в крайней, угловой точке достигается максимум целевой функции. Для нахождения координат этой точки достаточно решить два уравнения прямых, получаемых из соответствующих ограничений и дающих в пересечении точку максимума: х1 + 3.5 х2 = 350

х1 + х2 = 150 .

Отсюда легко записать решение исходной ЗЛП: max f(x) = 2300 и достигается при x1=70 и x2=80 (рис. 4.)

Задача 2. Для изготовления двух видов продукции А1 и А2 используют три вида ресурсов S1, S2, S3, запасы которых составляют усл.ед. Расход ресурсов на 1ед. продукции приведен в таблице:

Виды ресурсов

Запасы ресурсов

Расходы ресурсов на 1 изд.

А1

А2

S1

S2

S3

Прибыль

руб.

руб.

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

Составим экономико-математическую модель (ЭММ) задачи.

Пусть надо выпустить изделий A1 - x1 шт., а изделий А2 - x2 шт. Тогда прибыль F = 2x1 + 3x2 ??max

Решим задачу графически.

max F достигается в т. С

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

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

Выбор конкретной вычислительной процедуры осуществляется после приведения исходной ЗЛП к каноническому виду (КЗЛП):

В теории линейного программирования (ЛП) показано, что оптимальное решение ЗЛП связано с угловыми (крайними) точками многогранника решений, которым отвечают опорные планы (неотрицательные базисные решения системы уравнений КЗЛП). Каждый из опорных планов определяется системой m линейно независимых векторов, содержащихся в данной системе из n векторов А1, А2,…, Аn. Верхняя граница количества опорных планов, содержащихся в данной задаче, определяется числом сочетаний Сnm.

Задача 3. Получить решение по модели задачи об оптимальном использовании ограниченных ресурсов (решить ЗЛП):

Приведем задачу к каноническому виду путем введения дополнительных переменных x 3 и x4:

Найдем все опорные планы КЗЛП. Используя метод Жордана-Гаусса выписываем все базисные решения системы уравнений:

Последовательно будем иметь:

Х1 = (0,0,300,150); Х2= (150,0,150,0); Х3= (0,150,-150,0); Х4= (75,75,0,0); Х5= (300,0,0,-150); Х6= (0,100,0,50).

Среди этих базисных решений четыре опорных:

Х1 = (0,0,300,150); Х2= (150,0,150,0); Х4= (75,75,0,0); Х6= (0,100,0,50).

Указанным опорным планам на рис.5 отвечают соответственно следующие угловые точки и значения ЦФ в них:

А(0,0) и f(0,0)=0; Д(150,0) и f(150,0)=300; С(75,75) и f(75,75)=375; В(0,100) и f(0,100)=300.

Согласно теории ЛП оптимальное решение содержится среди опорных планов.

Рис. 5

Таким образом, максимальное значение, равное 375, целевая функция f (x1,x2) достигает на опорном плане Х4= (75,75,0,0), т.е. оптимальное решение рассматриваемой ЗЛП: x1 = 75, x2 = 75.

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

Симплекс-метод с естественным базисом

Для применения симплекс-метода с естественным базисом КЗЛП должна содержать единичную подматрицу размером mxm - в этом случае очевиден начальный опорный план (неотрицательное базисное решение системы ограничений КЗЛП).

Для определенности предположим, что первые m векторов матрицы системы уравнений составляют единичную матрицу. Тогда первоначальный опорный план очевиден - (b1, b2 ,…, bm ,0,…,0).

Проверка на оптимальность опорного плана проходит с помощью признака оптимальности, переход к другому опорному плану проводится с помощью преобразований Жордана-Гаусса при использовании математического признака оптимальности. Полученный опорный план снова проверяется на оптимальность и так далее. Процесс заканчивается за конечное число шагов, причем на последнем шаге либо выявляется неразрешимость задачи (конечного оптимума нет), либо получается оптимальный опорный план и соответствующее ему оптимальное значение ЦФ.

Математический признак оптимальности состоит из следующих двух теорем:

Если для всех векторов А1, А2,…, Аn выполняется условие

где ,

то полученный опорный план является оптимальным.

Если для некоторого вектора, не входящего в базис, выполняется условие , то можно получить новый опорный план, для которого значение ЦФ будет больше исходного, при этом могут быть два случая:

если все компоненты вектора, подлежащего вводу в базис, неположительны, то ЗЛП не имеет решения (конечного оптимума нет);

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

На основании признака оптимальности в базис вводится вектор Ак , давший минимальную отрицательную величину симплекс разности:

Чтобы выполнялось условие неотрицательности значений опорного плана, выводится из базиса вектор Аr, который дает минимальное положительное оценочное отношение

Строка Аr называется направляющей, столбец Ак и элемент ar к - направляющими.

Элементы направляющей строки в новой симплекс-таблице вычисляются по формулам:

а элементы i-й строки - по формулам:

Значения нового опорного плана рассчитываются по формулам:

для i = r ;

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

Примечание. Для использования приведенной процедуры к минимизации линейной функции f (x1,x2,…, xn) следует искать максимум - f (x1,x2,…, xn), затем полученный максимум взять с противоположным знаком. Оптимальное решение то же.

Пример. Получить решение по модели:

Эта задача (модель) линейного программирования, приведем ее к каноническому виду путем введения дополнительных переменных x 3 и x4:

КЗЛП имеет необходимое число единичных столбцов, т.е. обладает очевидным начальным опорным планом (0,0,300,150). Решение осуществляется симплекс-методом с естественным базисом с оформлением расчетов в симплекс-таблицах:

Номер симплекс-таблицы

Базис

В

2

3

0

0

Q

план

А3

0

300

1

3

1

0

100

0

А4

0

150

1

1

0

1

150

f(x)

0

-2

-3

0

0

А2

3

100

1/3

1

1/3

0

300

I

А4

0

50

2/3

0

-1/3

1

75

f(x)

300

-1

0

1

0

А2

3

75

0

1

1/2

-1/2

II

А1

2

75

1

0

-1/2

3/2

f(x)

375

0

0

1/2

3/2

В симплекс-таблице II получен оптимальный опорный план, поскольку все симплекс-разности (оценки) j. Оптимальные значения переменных равны: x1*=75, x2* =75 (основные переменные), x3* =0, x4* =0 (дополнительные переменные). Максимальное значение целевой функции равно 375.

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

5. Технология решения задач линейного программирования с помощью Поиска решений в среде EXCEL

Поиск решения - это надстройка EXCEL, которая позволяет решать оптимизационные задачи. Ecли, в меню Сервис отсутствует команда Поиск решения, значит, необходимо загрузить эту надстройку. Выберите команду Сервис Надстройки и активизируйте надстройку Поиск решения. Если же этой надстройки нет в диалоговом окне Надстройки, то вам необходимо обратиться к панели управления Windows, щелкнуть на пиктограмме Установка и удаление программ и с помощью программы установки Excel (или Office) установить надстройку Поиск решения.

После выбора команд Сервис Поиск решения появится диалоговое окно Поиск решения.

В диалоговом окне Поиск решения есть три основных параметра:

* Установить целевую ячейку

* Изменяя ячейки

* Ограничения

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

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

Третий параметр, который нужно вводить, для Поиска решения - это ограничения.

Для решения задачи необходимо:

Указать адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки).

Ввести исходные данные.

Ввести зависимость для целевой функции

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

Запустить Поиск решений.

Назначение целевой функции (установить целевую ячейку).

Ввод ограничений.

Ввод параметров для решения ЗЛП.

Рассмотрим технологию решения используя условия Задачи 1 (Задача о костюмах).

Намечается выпуск двух видов костюмов - мужских и женских. На женский костюм требуется 1 м шерсти, 2 м лавсана и 1 человеко-день трудозатрат. На мужской костюм - 3,5 м шерсти, 0,5 м лавсана и 1 человеко-день трудозатрат. Всего имеется 350 м шерсти, 240 м лавсана и 150 человеко-дней трудозатрат. Tребуется определить, сколько костюмов каждого вида необходимо сшить, чтобы обеспечить максимальную прибыль, если прибыль от реализации женского костюма составляет 10 денежных единиц, а от мужского - 20 денежных единиц. При этом следует иметь в виду, что необходимо сшить не менее 60 мужских костюмов.

Сформулируем экономико-математическую модель задачи.

Введем следующие обозначения: х1 - число женских костюмов; x2 - число мужских костюмов.

Прибыль от реализации женских костюмов составляет 10х1, а от реализации мужских 20х2, т.е. необходимо максимизировать целевую функцию: f(x) = 10 х1 + 20 х2 -> max.

Ограничения задачи имеют вид:

х1 + х2 150 - ограничение по труду

2 х1 + 0.5 х2 240 - ограничение по лавсану

х1 + 3.5 х2 350 - ограничение по шерсти

х2 60 - ограничение по костюмам

х1 0

Решение.

1. Указать адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки).

Обозначьте через Х1, Х2 количество костюмов каждого типа. В нашей задаче оптимальные значения вектора Х =(Х1, Х2,) будут помещены в ячейках A2:B2, оптимальное значение целевой функции в ячейке C3.

2. Ввести исходные данные.

Введите исходные данные задачи, как показано на рис.1.

Рис. 1

3. Ввести зависимость для целевой функции

*Курсор в ячейку «С3».

*Курсор на кнопку «Мастер функций», расположенную на панели инструментов.

*М1. На экране появляется диалоговое окно «Мастер функций шаг 1 из 2»

* Курсор в окно «Категория» на категорию «Математические».

* Курсор в окно «Функции» на «СУММПРОИЗВ» (рис.2).

Рис. 2

На экране появляется диалоговое окно «СУММПРОИЗВ» (рис. 3)

Рис. 3

* В строку «Массив 1» ввести А2:В2

* В строку «Массив 2» ввести А3:В3.

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

На экране: в ячейку С3 введена функция (рис. 4).

Рис. 4

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

* Курсор в ячейку «С3».

* На панели инструментов кнопка «Копировать в буфер».

* Курсор в ячейку «С4».

* На панели инструментов кнопка «Вставить из буфера».

* Курсор в ячейку «С5».

* На панели инструментов кнопка «Вставить из буфера».

* Курсор в ячейку «С6».

* На панели инструментов кнопка «Вставить из буфера».

* Курсор в ячейку «С7».

* На панели инструментов кнопка «Вставить из буфера».

Рис. 5

Примечание. Содержимое ячеек С4 - С7 необходимо проверить. Они обязательно должны содержать информацию, как это показано для примера на рис.6 (в качестве примера представлено содержимое ячейки С5).

Рис. 6

В строке «Меню» указатель мышки на имя «Сервис». В развернутом меню команда «Поиск решения». Появляется диалоговое окно «Поиск решения» (рис. 7).

Рис. 7

Назначить целевую функцию (установить целевую ячейку), указать адреса изменяемых ячеек.

* Курсор в строку «Установить целевую ячейку».

* Введите адрес ячейки «$С$3».

* Введите направление целевой функции в зависимости от условия вашей задачи: «Максимальному значению» («Минимальному значению»).

* Курсор в строку «Изменяя ячейки».

* Ввести адреса искомых переменных А$2:В$2. (Рис. 8.)

программирование двойственность оптимальный excel

Рис. 8

6. Ввести ограничения

* Указатель мышки на кнопку «Добавить. Появляется диалоговое окно «Добавление ограничения»

* В строке «Ссылка на ячейку» введите адрес $С$4.

* Ввести знак ограничения ?.

* В строке «Ограничение» введите адрес $D$4 (рис. 9)..

* Указатель мышки на кнопку «Добавить». На экране вновь диалоговое окно «Добавление ограничения».

* Введите остальные ограничения задачи, по выше описанному алгоритму

* После введения последнего ограничения кнопка «ОК».

На экране появится диалоговое окно «Поиск решения» с введенными условиями (рис.10).

Рис. 9

Рис. 10

7. Ввести параметры для решения ЗЛП

* В диалоговом окне указатель мышки на кнопку «Параметры». На экране появляется диалоговое окно «Параметры поиска решения» (рис. 11).

Рис. 11

* Установите флажки в окнах «Линейная модель» (это обеспечит применение симплекс - метода) и «Неотрицательные значения».

* Указатель мышки на кнопку «ОК». На экране диалоговое окно «Поиск решения».

* Указатель мышки на кнопку «Выполнить».

Через непродолжительное время появится диалоговое окно «Результаты поиска решения» и исходная таблица с заполненными ячейками А3:В3 для значений Хi и ячейка С3 с максимальным значением целевой функции (рис.12).

Рис. 12

Если указать тип отчета «Устойчивость», то можно получить дополнительную информацию об оптимальном решении (Рис. 13).

Рис. 13

В результате решения задачи получили ответ:

Х1 = 70 - необходимо сшить женских костюмов,

Х2 = 80 - необходимо сшить мужских костюмов,

F(x) = 2300 что бы получить максимальную прибыль.

Решим еще одну задачу.

Задача 4. (Задача о коврах).

Фабрика имеет в своем распоряжении определенное количество ресурсов: рабочую силу, деньги, сырье, оборудование, производственные площади и т. п. Допустим, например, ресурсы трех видов рабочая сила, сырье и оборудование имеются в количестве соответственно 80(чел/дней), 480(кг), 130(станко/часов). Фабрика может выпускать ковры четырех видов. Информация о количестве единиц каждого ресурса необходимых для производства одного ковра каждого вида и доходах, получаемых предприятием от единицы каждого вида товаров, приведена в табл.1.

Таблица 1

Ресурсы

Нормы расхода ресурсов на единицу изделия

Наличие

ресурсов

Ковер А

Ковер В

Ковер С

Ковер D

Труд

7

2

2

6

80

Сырье

5

8

4

3

480

Оборудование

2

4

1

8

130

Цена (тыс.руб.)

3

4

3

1

Требуется найти такой план выпуска продукции, при котором общая стоимость продукции будет максимальная.

1. Сформулируем экономико-математическую модель задачи.

Обозначим через Х1, Х2, Х3, Х4 количество ковров каждого типа.

Целевая функция - это выражение, которое необходимо максимизировать f(x) = 3Х1 +4Х2 +3Х3 +Х4

Ограничения по ресурсам

7Х1 +2Х2 +2Х3 +6Х4 80

5Х1 +8Х2 +4Х3 +3Х4480

2Х1 +4Х2 +Х3 +8Х4130

Х1, Х2, Х3, Х40

Решение

1. Указать адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки).

Обозначьте через Х1, Х2, Хз, Х4 количество ковров каждого типа. В нашей задаче оптимальные значения вектора Х =(Х1, Х2, Хз, Х4) будут помещены в ячейках ВЗ:ЕЗ, оптимальное значение целевой функции в ячейке F4.

2. Ввести исходные данные.

Введем исходные данные в созданную форму. В результате получим (Рисунок 14):

Рисунок 14 Данные введены

3. Введем зависимость для целевой функции

* Курсор в F4.

* Курсор на кнопку Мастер функций.

На экране диалоговое окно Мастер функций шаг 1 из 2.

* Курсор в окно Категория на категорию Математические.

Рисунок 15 Вводится функция для вычисления целевой функции

* Курсор в окно Функции на СУММПРОИЗВ.

* В массив 1 ввести В$3:E$3.

* В массив 2 ввести В4:E4.

* Готово. На экране: в F4 введена функция, как показано на Рисунке 15.

4. Введем зависимость для левых частей ограничений:

* Курсор в F4.

* Копировать в буфер.

* Курсор в F7.

* Вставить из буфера.

* Курсор в F8.

* Вставить из буфера.

* Курсор в F9.

* Вставить из буфера.

На этом ввод зависимостей закончен.

Запуск Поиска решения.

Назначение целевой функции (установить целевую ячейку).

Курсор в поле Установить целевую ячейку.

Ввести адрес $F$4.

Ввести направление целевой функции: Максимальному значению.

Ввести адреса искомых переменных:

Курсор в поле Изменяя ячейки.

Ввести адреса В$3:E$3.

5. Ввод ограничений.

Курсор в поле Добавить. Появится диалоговое окно Добавление ограничения (Рисунок 16.).

Рисунок 16 Ввод правых и левых частей ограничений

В окне Ссылка на ячейку ввести $F$7.

Ввести знак ограничение ..

Курсор в правое окно.

Вести $H$7.

Добавить. На экране опять диалоговое окно Добавление ограничения. Ввести остальные ограничения.

После ввода последнего ограничения ввести ОК.

На экране появится диалоговое окно Поиск решения с введенными условиями (Рисунок 17).

Рисунок 17 Введены все условия для решения задачи

8) Ввод параметров для решения ЗЛП (Рисунок 18).

Открыть окно Параметры поиска решения.

Установить флажок Линейная модель, что обеспечивает применение симплекс-метода.

Установить флажок Неотрицательные значения.

ОК (На экране диалоговое окно поиска решения).

Выполнить (На экране диалоговое окно результаты поиска решения - Рисунок 19.).

Рисунок 18 Ввод параметров

Рисунок 19 Решение найдено

Полученное решение означает, что максимальный доход 150 тыс. руб. фабрика может получить при выпуске 30 ковров второго вида и 10 ковров третьего вида. При этом ресурсы труд и оборудование будут использованы полностью, а из 480 кг пряжи (ресурс сырье) будет использовано 280 кг.

Создание отчета по результатам поиска решения

Excel позволяет представить результаты поиска решения в форме отчёта. Существует три типа таких отчетов:

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

Устойчивость (Sensitivity). Отчет, содержащий сведения о чувствительности решения к малым изменениям в изменяемых ячейках иди в формулах ограничений.

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

1. Отчет по результатам.

В отчете по результатам содержатся оптимальные значения переменных Х1, Х2, Х3, Х4 , которые соответственно равны 0,10, 30,0; значение целевой функции - 150, а также левые части ограничений.

6. Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений

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

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

Переменные двойственной задачи yi называют объективно обусловленными оценками, или двойственными оценками, или «ценами» ресурсов, или теневыми ценами.

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

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

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

2) матрица А, составленная из коэффициентов при неизвестных в системе ограничений исходной задачи и аналогичная матрица Ат в двойственной задаче получаются друг из друга транспонированием;

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

4) коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе ограничений исходной задачи, а правыми частями в ограничениях двойственной задачи -- коэффициенты при неизвестных в целевой функции исходной задачи;

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

Модель исходной (прямой) задачи в общем виде может быть записана следующим образом:

Модель двойственной задачи имеет вид:

Две приведенные задачи образуют пару симметричных двойственных задач. Основные утверждения о взаимно двойственных задачах содержатся в двух следующих теоремах.

Первая теорема двойственности.

Для взаимно двойственных задач имеет место один из взаимоисключающих случаев:

1. В прямой и двойственной задачах имеются оптимальные решения, при этом значения целевых функций на оптимальных решениях совпадают: f(x) = g(y).

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

3. В двойственной задаче допустимое множество не пусто, а целевая функция на этом множестве не ограничена снизу. При этом у прямой задачи допустимое множество оказывается пустым.

4.Обе из рассматриваемых задач имеют пустые допустимые множества.

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

f(X) < g(Y}, т. е. ценность всей выпущенной продукции не превосходит суммарной оценки имеющихся ресурсов. Значит величина g(Y) - f(X) характеризует производственные потери в зависимости от рассматриваемой производственной программы и выбранных Оценок ресурсов.

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

Вторая теорема двойственности (теорема о дополняющей нежесткости).

Пусть X=(x1,x2,...xn) - допустимое решение прямой задачи, а Y= (y1,y2,...ym) - допустимое решение двойственной задачи. Для того чтобы они были оптимальными решениями соответственно прямой и двойственной задач необходимо и достаточно, чтобы выполнялись следующие соотношения:

*

**

Условия (*) и (**) позволяют, зная оптимальное решение одной из взаимно двойственных задач, найти оптимальное решение другой задачи.

Из второй теоремы двойственности в данном случае следуют такие требования на оптимальную производственную программу X=(X1,X2,...,Xn) и оптимальный вектор оценок Y=(Y1,Y2,...,Ym):

(4)

(5)

Условия (4) можно интерпретировать так: если оценка yi единицы ресурса i-го вида положительна, то при оптимальной производственной программе этот ресурс используется полностью, если же ресурс используется не полностью, то его оценка равна нулю. Из условия (5) следует, что если j-й вид продукции вошел в оптимальный план, то он в оптимальных оценках неубыточен, если же j-й вид продукции убыточен, то он не войдет в план, не будет выпускаться.

Рассмотрим еще одну теорему, выводы которой будут использованы в дальнейшем.

Теорема об оценках.

Значения переменных Yi в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов bi системы ограничений-неравенств прямой задачи на величину

Решая ЗЛП симплексным методом, мы одновременно решаем двойственную ЗЛП. Переменные двойственной задачи yi называют объективно обусловленными оценками.

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

Пример. Сформулируем экономико-математическую модель двойственной задачи к задаче о коврах.

Прямая задача:

f(x) = 3Х1 +4Х2 +3Х3 +1Х4

Ограничения по ресурсам

7Х1 +2Х2 +2Х3 +6Х4 80

5Х1 +8Х2 +4Х3 +3Х4480

2Х1 +4Х2 +Х3 +8Х4130

Х1, Х2, Х3, Х40

Количество неизвестных в двойственной задаче равно числу функциональных ограничений в исходной задаче. В исходной задаче три ограничения - по труду, по сырью и по оборудованию. Следовательно, в двойственной задаче - три неизвестных:

Y1 - двойственная оценка ресурса труд, или «цена» труда;

Y2 - двойственная оценка ресурса сырье, или «цена» сырья;

Y3 - двойственная оценка ресурса оборудование, или «цена» оборудования.

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

g = 80 Y1 + 480Y2 + 130Y3 min

Необходимо найти такие “цены” на ресурсы (Yi), чтобы общая стоимость используемых ресурсов была минимальной.

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

7 Y1 + 5Y2 + 2Y3 3

2 Y1 + 8Y2 + 4Y3 4

2 Y1 + 4Y2 + 1Y3 3

6 Y1 + 3Y2 + 8Y3 1

Y1 ,Y2 ,Y3 0

Решение двойственной задачи можно найти в отчете Поиска решений. Отчет по устойчивости. Теневые цены ресурсов труд, сырье и оборудование соответственно равны 4/3, 0, 1/3 или в десятичных дробях 1.3333, 0, 0.3333.

Отчет по устойчивости

Изменяемые ячейки

Ячейка

Имя

Результ.

Нормир.

Целевой

Допустимое

Допустимое

Значение

Стоимость

Коэффициент

Увеличение

Уменьшение

$B$3

Значение Х1

0

...

Страница:


Подобные документы

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.

© 2000 — 2023, ООО «Олбест» Все права защищены