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

 

Содержание


Введение

Теоретическая часть

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

.2 Алгоритм решения задач линейного программирования в Microsoft Excel

Практическая часть

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

.2 Нахождение максимальной прибыли

.3 Решение задачи линейного программирования в Microsoft Excel

Заключение

Список используемых источников


Введение


Дисциплины, в которых изучаются модели и методы оптимизации («Методы оптимизации и теория принятия решений», «Исследование операций», Математические модели исследования экономики и математическое программирование») присутствуют во многих образовательных программах профессионального образования. Как правило, это программы по направлениям инженерного образования, и по направлениям, связанным с управлением (менеджментом) и экономикой.

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

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

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

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

В 1939 году Леонид Витальевич Канторович опубликовал работу «Математические методы организации и планирования производства», в которой сформулировал новый класс экстремальных задач с ограничениями и разработал эффективный метод их решения, таким образом были заложены основы линейного программирования. Линейное программирование является частным случаем математического программирования <#"justify">-чтобы ограничения задачи были совместимы;

-целевая функция была ограничена сверху при поиске максимального значения и снизу при поиске минимального значения.

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

-ограничения вида «меньше или равно» приводятся к строгому равенству путём добавления к левой части каждого ограничения неотрицательной целой переменной, которая записывается в целевую функцию с коэффициентом равным нулю;

-чтобы привести ограничения вида «больше или равно» к строгому равенству надо из левой части каждого ограничения вычесть неотрицательную целую переменную и добавить искусственную неотрицательную переменную (y1,y2…yn), которая войдёт в целевую функцию с коэффициентом (-M).

Алгоритм:

)Привести математическую модель к канонической форме, заполнить симплекс таблицу и вычислить значение целевой функции и относительных оценок ?i.

)Если все относительные оценки не отрицательны и среди базисных переменных нет искусственных, то план оптимален и задача решена. Решение находится в столбце B:


;

;

.


Если искомая переменная не вышла в базис, значит, она равна нулю.

Если все относительные оценки не отрицательны и среди них есть хотя бы одна равная нулю, а в базисе нет искусственных переменных, то задача решена и имеет бесконечное множество решений, одно из которых вышло в базис и находится в столбце B;

Если все ?i ? 0, а в базисе остались искусственные переменные, то задача решений не имеет;

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

3)Из всех относительных оценок выбирается наибольшая по модулю, столбец соответствующий ей называется главным. Для определения главной строки надо поэлементно разделить столбец B на главный столбец, наименьшее из получившихся частных соответствует главной строке. Главный элемент симплекс-таблицы находится на пересечении главной строки и главного столбца. Далее необходимо произвести пересчёт симплекс-таблицы.

)В новой итерации элементы главной строки делятся на главный элемент, а элементы главного столбца делят на «минус главный элемент». Если в главной строке или в главном столбце есть ноль, то элементы, соответствующие этим нулям столбца и строки переписываются в новую таблицу без изменений. Остальные клетки симплекс-таблицы пересчитываются по правилу прямоугольника - из произведения элементов главной диагонали, проходящей через главный элемент, вычитают произведение элементов побочной диагонали и результат делят на главный элемент.

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

)Через конечное число итераций либо будет получено решение задачи линейного программирования, либо будет установлено, что решение неограниченно.


.2 Алгоритм решения задач линейного программирования в Microsoft Excel


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

-Ввести условия задачи:

а)создать экранную форму для ввода условия задачи:

1)переменных (дать имя массиву переменных);

2)ограничений;

3)целевой функции;

4)граничных условий;

б)ввести исходные данные в экранную форму:

1)коэффициенты целевой функции;

2)коэффициенты при переменных в ограничениях;

3)правые части ограничений;

в)ввести зависимости из математической модели в экранную форму:

1)формулу для расчета целевой функции;

2)формулы для расчета значений левых частей ограничений;

г)задать целевую функцию (в окне «Поиск решения»):

1)целевую ячейку;

2)направление оптимизации целевой функции;

д)ввести ограничения и граничные условия (в окне «Поиск решения»):

1)ячейки со значениями переменных;

2)граничные условия для допустимых значений переменных;

3)соотношения между правыми и левыми частями ограничений;

-Решить задачу:

а)Для решения задач в Microsoft Excel необходимо иметь надстройку«Поиск решения». Если в меню Сервис нет такого пункта, то установите пакет «Поиск решения». Для этого запустите Сервис-> Надстройки. В открывшемся окне выберите надстройку Поиск решения. После этого пункт «Поиск решения» появится в меню Сервис.

б)Запустить задачу на решение (в окне «Поиск решения»).


2 Практическая часть


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


Для решения задачи составим ее математическую модель. Для этого введем обозначения:

Х1 - прибыль от реализации 1 т молока;

Х2 - прибыль от реализации 1 т кефира;

X3 - прибыль от реализации 1 т сметаны.

Стоимость:

X1 = 30 руб. ;

X2 = 28 руб;

X3 = 150 руб.

Критерий задачи:

Максимальная прибыль(max).

Итак, модель имеет вид:


.


.2 Нахождение максимальной прибыли


Для нахождения максимальной прибыли приведём модель к канонической форме.

Каноническая форма:

;


Симплекс-таблица заполняется в соответствии с алгоритмом, изложенным в пункте 1.1.

Нахождение оптимального плана, приводящего к максимальной прибыли, приведено в таблицах 1-5.


Таблица 1 - Итерация 0

-103028150000CBX1X2X3X7X8X9X4021,40,30,323,25000X505001000X60136111000Y1 -M60100-100Y2 -M100100-10Y3 -M 500100-1?iF0(x) -75M-M-30-M-28-M-150MMM

Значения целевой функции определяется путём вычисления суммы парных произведений столбца C и столбца B:


(руб.)

Значение относительных оценок так же вычисляются как сумма парных произведений элементов столбца C на соответствующий столбец:



Данный план не оптимален т.к. среди относительных оценок есть отрицательные:

M-30;

M-28;

M-150.

Из отрицательных относительных оценок нужно выбрать наибольшую по модулю, (-M-150), соответствующий ей столбец называется главным.

Для определения главной строки нужно столбец B поэлементно разделить на главный столбец:

,25÷1=16,25;

÷1=136;

5÷1=5.

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

На пересечении главной строки и главного столбца находится главный элемент, и он равен единице. В базисе остались искусственные переменные Y1 и Y2, Y3 .

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


Таблица 2 - Итерация 1

-103028000CBX1X2X7X8X9X4021,40,30,32000X50000001X6013111001Y1-M6010-100Y2-M10010-10X315050000-1F1(x) -70M+750-M-30-M-28MM-150

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

Элементы главной строки делятся на главный элемент:

,4÷0,3=71,333;

÷1=131;

60÷1=60.

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

Данный план не оптимален т.к. среди относительных оценок есть отрицательные:

M-30;

M-28;

.

В базисе остались две искусственные переменные Y2 и Y1.

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


Таблица 3 - Итерация 2

-10200000CBX2X7X8X9X403,40,320,300X5000001X60711101X130600-100Y2-M1010-10X31505000-1?iF2(x) -M+2550-М-28-30ММ

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

Элементы главной строки делятся на главный элемент:

,4÷0,32=10,625;

÷1=71;

10÷1=10.

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

Данный план не оптимален т.к. среди относительных оценок есть отрицательные:

M-28;

.

В базисе осталась одна искусственная переменная Y1.

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


Таблица 4 - Итерация 3

-10000CBX7X8X9X400,20,30,320X500001X6061111X13060-100X228100-10X3150500-1?iF3(x) 2830-30-28-150

В таблице 4 переменные главного столбца и главной строки вместе со своими коэффициентами меняются местами, а все остальные переменные и их коэффициенты переписываются без изменений.

Элементы главной строки пересчитываются согласно алгоритму.

Элементы главного столбца делятся на «минус главный элемент».

Вместо главного элемента необходимо записать обратное ему число и оно равно единице.

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

В базисе не остались искусственные переменные, но данный план не оптимален т.к. среди относительных оценок есть одна отрицательная (-150).

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


Таблица 5 - Итерация 4

-10000CBX7X8X9X400,20,30,320X900001X606111-1X13060-100X228100-10X31505001?iF4(x) 2830-30-28150

Заполнение и пересчёт новой итерации происходит аналогично предыдущей итерации.

В базисе нет искусственных переменных, но данный план не оптимален т.к. среди относительных оценок есть одна отрицательная (-30).

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


Таблица 6 - Итерация 0

-10000CBX4X8X 5X700,663,31,060X900001X6060,33-0,3-0,02-1X13060,666670,30,320X22810010X31505001?iF5(x) 2850937,6150

Заполнение и пересчёт новой итерации происходит аналогично предыдущей итерации.

Все относительные оценки положительные и среди базисных переменных нет искусственных, следовательно, план является оптимальным и задача решена, решение находится в столбце B.


x1=60,66667 (руб.);

x2=10 (руб.).

x3=5 (руб.)


2.3 Решение задачи линейного программирования в Microsoft Excel


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

По условию задачи составим начальный план в Microsoft Excel. Выделим сначала ячейки под набор ограничений, под искомые переменные коэффициенты, значение целевой функции. Необходимо задать значение целевой функции как сумму произведений искомых переменных на коэффициенты. Так же надо сделать и для набора ограничений.

Начальный план решения задачи в Microsoft Excel дан на рисунке 1.


Рисунок 1 - Начальный план решения задачи


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


Рисунок 2 - Поиск решений


Вводим набор ограничений и нажимаем кнопку «выполнить».

После первых вычислений получаем X1, это представлено на рисунке 3.


Рисунок 3 - Первое значение


Далее нажимаем на кнопку «продолжить».

После второго вычисления получим X2, это показано на рисунке 4.

Рисунок 4 - Второе значение


Повторяя те же самые действия, решим задачу.

Результат решения задачи и значение целевой функции представлено на рисунке 5.


Рисунок 5 - Результат поиска решения


Заключение


В данной курсовой работе было рассмотрено решение задачи линейного программирования симплекс методом. Задача была решена симплекс методом, также решение задачи линейного программирования представлено в Microsoft Excel.

Таким образом, вычислительная техника в настоящее время находит широкое применение, как в общей математике, так и в одном из её разделов - математических методах.

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

линейное программирование симплекс метод

Список используемой литературы


1Зайченко Ю.П. Исследование операций. Киев: Высшая школа, 1997. - 152 с.

2Шумилова Л. Исследование операций. Киев: Высшая школа, 2004. - 137 с.

Реклейтис Г. Оптимизация в технике. М.:Мир,1982г. (В 2-х томах).

Вентцель Е.С. Исследование операций. М.: Высшая школа, 2002. - 255 с.

Кузнецов Ю.Н. Математическое программирование. М.: ЮНИТИ, 1999. - 311 с.

Химмельблау Д. Прикладное программирование. М.: Мир, 1999. - 391 с.

Коршунов Ю.М. Математические основы кибернетики. М.: Энергия, 2001. - 214 с.

Сакович В.А. Исследование операций. Минск: Высшая школа, 1998. - 162 с.


Содержание Введение Теоретическая часть .1 Алгоритм решения задач линейного программирования симплекс-методом .2 Алгоритм решения задач линейног

Больше работ по теме:

КОНТАКТНЫЙ EMAIL: [email protected]

Скачать реферат © 2017 | Пользовательское соглашение

Скачать      Реферат

ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ