Решение оптимизационных задач средствами Excel
Оптимизационная модель - отражение экономической задачи в математической форме, от решения которой зависит выбор оптимального управленческого действия. Графический и симплексный методы решения задач линейного программирования средствами Microsoft Excel.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курс лекций |
| Язык | русский |
| Дата добавления | 18.12.2012 |
| Размер файла | 1,6 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Министерство образования Российской Федерации
Всероссийский заочный финансово-экономический институт
Кафедра экономико-математических методов и моделей
Краткий курс лекций и лабораторная работа № 1 по курсу "Экономико-математические методы и прикладные модели"
Решение оптимизационных задач средствами EXCEL
Орлова И.В., Орлов П.В.
Москва 2001
Оглавление
- 1. Решение систем линейных уравнений методом Жордана - Гаусса
- 2. Общая задача оптимизации
- 3. Графический метод решения задач линейного программирования
- 4. Симплексный метод решения задачи линейного программирования
- 5. Технология решения задач линейного программирования с помощью поиска решений в среде EXCEL
- 6. Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений
- 7. Задания к контрольной работе
- Список литературы, имеющейся в библиотеке ВЗФЭИ
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 - некоторые действительные числа. excel программирование графический симплексный
Задачи математического программирования делятся на задачи линейного и нелинейного программирования. Если все функции 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 соответствует нижняя полуплоскость
Аналогично можно изобразить графически каждое ограничение задачи линейного программирования.
Решением каждого неравенства системы ограничений ЗЛП является полуплоскость, содержащая граничную прямую и расположенная по одну сторону от нее. Пересечение полуплоскостей, каждая из которых определяется соответствующим неравенством системы, называется областью допустимых решений или областью определения. Необходимо помнить, что область допустимых решений удовлетворяет условиям неотрицательности (xj0, j=1,…,n). Координаты любой точки, принадлежащей области определения являются допустимым решением задачи.
Для нахождения экстремального значения целевой функции при графическом решении задач ЛП используют вектор-градиент, координаты которого являются частными производными целевой функции, т.е.
Этот вектор показывает направление наискорейшего изменения целевой функции. Прямая , перпендикулярная вектору-градиенту, является линией уровня целевой функции. В любой точке линии уровня целевая функция принимает одно и то же значение. Приравняем целевую функцию постоянной величине "a". Меняя значение "a", получим семейство параллельных прямых, каждая из которых является линией уровня.
Важное свойство линии уровня линейной функции состоит в том, что при параллельном смещении линии в одну сторону уровень только возрастает, а при смещении в другую сторону - убывает.
С геометрической точки зрения в задаче линейного программирования ищется такая угловая точка или набор точек из допустимого множества решений, на котором достигается самая верхняя (нижняя) линия уровня, расположенная дальше (ближе) остальных в направлении наискорейшего роста.
Графический метод решения ЗЛП состоит из следующих этапов.
Строится многоугольная область допустимых решений ЗЛП - ОДР,
Строится вектор-градиент ЦФ в какой-нибудь точке Х 0 принадлежащей ОДР - .
Линия уровня C1x1+C2x2 = а (а-постоянная величина) - прямая, перпендикулярная вектору -градиенту - передвигается в направлении этого вектора в случае максимизации f(x1,x2) до тех пор, пока не покинет пределов ОДР. Предельная точка (или точки) области при этом движении и является точкой максимума f(x1,x2).
Для нахождения ее координат достаточно решить два уравнения прямых, получаемых из соответствующих ограничений и дающих в пересечении точку максимума. Значение f(x1,x2), найденное в получаемой точке, является максимальным.
При минимизации f(x1,x2) линия уровня перемещается в направлении, противоположном вектору-градиенту. Если прямая при своем движении не покидает ОДР, то соответствующий максимум или минимум f(x1,x2) не существует.
Если линия уровня параллельна какому-либо функциональному ограничению задачи, то оптимальное значение ЦФ будет достигаться в любой точке этого ограничения, лежащей между двумя оптимальными угловыми точками, и, соответственно, любая из этих точек является оптимальным решением ЗЛП.
Рассмотрим графическое решение задач линейного программирования на следующем примере.
Задача 1. О планировании выпуска продукции пошивочному предприятию. (Задача о костюмах).
Намечается выпуск двух видов костюмов - мужских и женских. На женский костюм требуется 1 м шерсти, 2 м лавсана и 1 человеко-день трудозатрат. На мужской костюм - 3,5 м шерсти, 0,5 м лавсана и 1 человеко-день трудозатрат. Всего имеется 350 м шерсти, 240 м лавсана и 150 человеко-дней трудозатрат. Требуется определить, сколько костюмов каждого вида необходимо сшить, чтобы обеспечить максимальную прибыль, если прибыль от реализации женского костюма составляет 10 денежных единиц, а от мужского - 20 денежных единиц. При этом следует иметь в виду, что необходимо сшить не менее 60 мужских костюмов.
Модель задачи
Введем следующие обозначения: х1 - число женских костюмов; x2 - число мужских костюмов.
Прибыль от реализации женских костюмов составляет 10х1, а от реализации мужских 20х2, т.е. необходимо максимизировать целевую функцию
f(x) = 10 х 1 + 20 х 2 -> max
Ограничения задачи имеют вид:
Первое ограничение по труду х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).
В нашем случае движение линии уровня будем осуществлять до ее выхода из области допустимых решений. в крайней, угловой точке достигается максимум целевой функции. Для нахождения координат этой точки достаточно решить два уравнения прямых, получаемых из соответствующих ограничений и дающих в пересечении точку максимума:
х1 + 3.5 х2 = 350
х1 + х2 = 150
Отсюда легко записать решение исходной ЗЛП: max f(x) = 2300 и достигается при x1=70 и x2=80 (рис. 4.)
Рис.4. Максимум целевой функции достигается в точке (70, 80)
Задача 2. Для изготовления двух видов продукции А1 и А2 используют три вида ресурсов S1, S2, S3, запасы которых составляют 18, 15 и 5 усл. ед. Расход ресурсов на 1 ед. продукции приведен в таблице:
Необходимо составить такой план производства продукции, который обеспечит наибольшую прибыль от ее реализации.
Составим экономико-математическую модель (ЭММ) задачи.
Пусть надо выпустить изделий A1 - x1 шт., а изделий А2 - x2 шт. Тогда прибыль
Решим задачу графически
max F достигается в т. С
Таким образом, необходимо выпустить х1=6 шт. изделий А1, x2=4 шт. изделий А2, чтобы получить max F = 2*6 + 3*4 = 24 ден. ед.
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), затем полученный максимум взять с противоположным знаком. Оптимальное решение то же.
Пример. Получить решение по модели:
Эта задача (модель) линейного программирования, приведем ее к каноническому виду путем введения дополнительных переменных x3 и x4:
КЗЛП имеет необходимое число единичных столбцов, т.е. обладает очевидным начальным опорным планом (0,0,300,150). Решение осуществляется симплекс-методом с естественным базисом с оформлением расчетов в симплекс-таблицах:
|
Номер симплекс-таблицы |
Базис |
В план |
2 |
3 |
0 |
0 |
Q |
||
|
0 |
А 3 |
0 |
300 |
1 |
3 |
1 |
0 |
100 |
|
|
А 4 |
0 |
150 |
1 |
1 |
0 |
1 |
150 |
||
|
f(x) |
0 |
-2 |
-3 |
0 |
0 |
||||
|
I |
А 2 |
3 |
100 |
1/3 |
1 |
1/3 |
0 |
300 |
|
|
А 4 |
0 |
50 |
2/3 |
0 |
-1/3 |
1 |
75 |
||
|
f(x) |
300 |
-1 |
0 |
1 |
0 |
||||
|
II |
А 2 |
3 |
75 |
0 |
1 |
1/2 |
-1/2 |
||
|
А 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, которая позволяет решать оптимизационные задачи. Если, в меню Сервис отсутствует команда Поиск решения, значит, необходимо загрузить эту надстройку. Выберите команду Сервис Надстройки и активизируйте надстройку Поиск решения. Если же этой надстройки нет в диалоговом окне Надстройки, то вам необходимо обратиться к панели управления Windows, щелкнуть на пиктограмме Установка и удаление программ и с помощью программы установки Excel (или Office) установить надстройку Поиск решения.
После выбора команд Сервис Поиск решения появится диалоговое окно Поиск решения.
В диалоговом окне Поиск решения есть три основных параметра:
* Установить целевую ячейку
* Изменяя ячейки
* Ограничения
Сначала нужно заполнить поле Установить целевую ячейку. Во всех задачах для средства Поиск решения оптимизируется результат в одной из ячеек рабочего листа. Целевая ячейка связана с другими ячейками этого рабочего листа с помощью формул. Средство Поиск решения использует формулы, которые дают результат в целевой ячейке, для проверки возможных решений. Можно выбрать поиск наименьшего или наибольшего значения для целевой ячейки или же установить конкретное значение.
Второй важный параметр средства Поиск решения - это параметр Изменяя ячейки. Изменяемые ячейки - это те ячейки, значения в которых будут изменяться для того, чтобы оптимизировать результат в целевой ячейке. Для поиска решения можно указать до 200 изменяемых ячеек. К изменяемым ячейкам предъявляется два основных требования. Они не должны содержать формул, и изменение их значений должно отражаться на изменении результата в целевой ячейке. Другими словами, целевая ячейка зависима от изменяемых ячеек.
Третий параметр, который нужно вводить, для Поиска решения - это ограничения.
Для решения задачи необходимо:
Указать адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки).
Ввести исходные данные.
Ввести зависимость для целевой функции
Ввести зависимости для ограничений.
Запустить Поиск решений.
Назначение целевой функции (установить целевую ячейку).
Ввод ограничений.
Ввод параметров для решения ЗЛП.
Рассмотрим технологию решения используя условия Задачи 1 (Задача о костюмах).
Намечается выпуск двух видов костюмов - мужских и женских. На женский костюм требуется 1 м шерсти, 2 м лавсана и 1 человеко-день трудозатрат. На мужской костюм - 3,5 м шерсти, 0,5 м лавсана и 1 человеко-день трудозатрат. Всего имеется 350 м шерсти, 240 м лавсана и 150 человеко-дней трудозатрат. Требуется определить, сколько костюмов каждого вида необходимо сшить, чтобы обеспечить максимальную прибыль, если прибыль от реализации женского костюма составляет 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 будет использоваться при вводе зависимостей для ограничений, поэтому на этот массив надо сделать абсолютную ссылку Относительные и абсолютные ссылки. В зависимости от выполняемых задач в Excel можно использовать относительные ссылки, определяющие положение ячейки относительно положения ячейки формулы, или абсолютные ссылки, которые всегда указывают на конкретные ячейки. Если перед буквой или номером стоит знак доллара, например, $A$2, то ссылка на столбец или строку является абсолютной. Относительные ссылки автоматически корректируются при их копировании, а абсолютные ссылки - нет..
На экране: в ячейку С3 введена функция (рис. 4).
Рис. 4.
4. Ввести зависимости для ограничений.
* Курсор в ячейку "С3".
* На панели инструментов кнопка "Копировать в буфер".
* Курсор в ячейку "С4".
* На панели инструментов кнопка "Вставить из буфера".
* Курсор в ячейку "С5".
* На панели инструментов кнопка "Вставить из буфера".
* Курсор в ячейку "С6".
* На панели инструментов кнопка "Вставить из буфера".
* Курсор в ячейку "С7".
* На панели инструментов кнопка "Вставить из буфера".
Рис.5.
Примечание. Содержимое ячеек С4 - С7 необходимо проверить. Они обязательно должны содержать информацию, как это показано для примера на рис.6 (в качестве примера представлено содержимое ячейки С5).
Рис. 6.
В строке "Меню" указатель мышки на имя "Сервис". В развернутом меню команда "Поиск решения". Появляется диалоговое окно "Поиск решения" (рис. 7).
Рис. 7.
5. Назначить целевую функцию (установить целевую ячейку), указать адреса изменяемых ячеек.
* Курсор в строку "Установить целевую ячейку".
* Введите адрес ячейки "$С$3".
* Введите направление целевой функции в зависимости от условия вашей задачи: "Максимальному значению" ("Минимальному значению").
* Курсор в строку "Изменяя ячейки".
* Ввести адреса искомых переменных А$2:В$2. (Рис. 8.)
Рис. 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Х480
5Х1 +8Х2 +4Х3 +3Х4480
2Х1 +4Х2 +Х3 +8Х4130
Х1, Х2, Х3, Х40
Решение
1. Указать адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки).
Обозначьте через Х1, Х2, Х3, Х4 количество ковров каждого типа. В нашей задаче оптимальные значения вектора Х =(Х1, Х2, Х3, Х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, Х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
...Подобные документы
Анализ метода линейного программирования для решения оптимизационных управленческих задач. Графический метод решения задачи линейного программирования. Проверка оптимального решения в среде MS Excel с использованием программной надстройки "Поиск решения".
курсовая работа [2,2 M], добавлен 29.05.2015Особенности использования электронной таблицы Microsoft Excel для решения оптимизационных задач. Выполнение команды "Поиск решения" в меню "Сервис". Запись ограничений через использование кнопки "Добавить". Сообщение о найденном решении на экране.
лабораторная работа [4,5 M], добавлен 03.08.2011Анализ решения задачи линейного программирования. Симплексный метод с использованием симплекс-таблиц. Моделирование и решение задач ЛП на ЭВМ. Экономическая интерпретация оптимального решения задачи. Математическая формулировка транспортной задачи.
контрольная работа [196,1 K], добавлен 15.01.2009Краткие сведения об электронных таблицах MS Excel. Решение задачи линейного программирования. Решение с помощью средств Microsoft Excel экономической оптимизационной задачи, на примере "транспортной задачи". Особенности оформления документа MS Word.
курсовая работа [1,1 M], добавлен 27.08.2012Основные понятия агентов, термины и определения, принципы классификации. Линейные модели многоагентных систем. Постановка задачи линейного программирования, свойства ее решений. Графический и симплексный способы решения ЗЛП. Использование Microsoft Excel.
курсовая работа [662,4 K], добавлен 03.11.2014Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.
курсовая работа [1,1 M], добавлен 21.03.2012Использование информационных технологий для решения транспортных задач. Составление программ и решение задачи средствами Pascal10; алгоритм решения. Работа со средствами пакета Microsoft Excel18 и MathCad. Таблица исходных данных, построение диаграммы.
курсовая работа [749,1 K], добавлен 13.08.2012Принципы решения задач линейного программирования в среде электронных таблиц Excel, в среде пакета Mathcad. Порядок решения задачи о назначении в среде электронных таблиц Excel. Анализ экономических данных с помощью диаграмм Парето, оценка результатов.
лабораторная работа [2,0 M], добавлен 26.10.2013Изучение и укрепление на практике всех моментов графического метода решения задач линейного программирования о производстве журналов "Автомеханик" и "Инструмент". Построение математической модели. Решение задачи с помощью электронной таблицы Excel.
курсовая работа [663,9 K], добавлен 10.06.2014Применение методов линейного программирования для решения оптимизационных задач. Основные понятия линейного программирования, свойства транспортной задачи и теоремы, применяемые для ее решения. Построение первичного опорного плана и системы потенциалов.
курсовая работа [280,8 K], добавлен 17.11.2011Решение задачи средствами Паскаль и блок-схемы выполненных процедур, составление программы. Результаты решения задачи по перевозке грузов. выполнение задачи средствами MS Excel, создание таблиц. Порядок и особенности решения задачи в среде MathCAD.
курсовая работа [2,5 M], добавлен 27.02.2011Особенности задач линейного программирования. Симплексный метод решения задач линейного программирования. Обоснование выбора языка, инструментария программирования, перечень идентификаторов и блок-схема алгоритма. Логическая схема работы программы.
дипломная работа [2,4 M], добавлен 13.08.2011Теоретическая основа линейного программирования. Задачи линейного программирования, методы решения. Анализ оптимального решения. Решение одноиндексной задачи линейного программирования. Постановка задачи и ввод данных. Построение модели и этапы решения.
курсовая работа [132,0 K], добавлен 09.12.2008Особенности решения задач линейного программирования (ЛП) в табличном редакторе Microsoft Excel. Создание экранной формы для ввода условия задачи. Ограничения и граничные условия, перенесение зависимостей из математической модели в экранную форму.
лабораторная работа [160,5 K], добавлен 26.05.2015Математическая модель задачи оптимизации, принципы составления, содержание и структура, взаимосвязь элементов. Обоснование возможности решения поставленной задачи средствами оптимизации Excel. Оценка экономической эффективности оптимизационных решений.
курсовая работа [3,4 M], добавлен 10.11.2014Ознакомление с разнообразными надстройками, входящими в состав Microsoft Excel; особенности их использования. Примеры решения задач линейного программирования с помощью вспомогательных программ "Подбор параметра", "Поиск решения" и "Анализ данных".
реферат [2,5 M], добавлен 25.04.2013Построение и использование математических и алгоритмических моделей для решения линейных оптимизационных задач. Освоение основных приемов работы с инструментом "Поиск решения" среды Microsoft Excel. Ввод системы ограничений и условий оптимизации.
лабораторная работа [354,7 K], добавлен 21.07.2012Общее понятие и характеристика задачи линейного программирования. Решение транспортной задачи с помощью программы MS Excel. Рекомендации по решению задач оптимизации с помощью надстройки "Поиск решения". Двойственная задача линейного программирования.
дипломная работа [2,4 M], добавлен 20.11.2010Постановка задачи линейного программирования и формы ее записи. Понятие и методика нахождения оптимального решения. Порядок приведения задач к каноническому виду. Механизмы решения задач линейного программирования аналитическим и графическим способами.
методичка [366,8 K], добавлен 16.01.2010Расчеты по таблице перевозок грузов между отдельными регионами. Решение задачи управления процессами перевозок в среде Pascal. Решение задачи средствами MS Excel. Исходные данные и итоги по строкам и столбцам. Решение задачи средствами MATHCAD.
курсовая работа [1,8 M], добавлен 25.03.2015
