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

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

Содержание

Введение

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

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

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

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

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

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

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

Заключение

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

Введение

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

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

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

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

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

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

Термин «программирование» нужно понимать в смысле «планирования» Он был предложен в середине 1940-х годов Джорджем Данцигом, одним из основателей линейного программирования, ещё до того, как компьютеры были использованы для решения линейных задач оптимизации.

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

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

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

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

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

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

Процесс применения симплексного метода предполагает реализацию трех его основных элементов:

1) способ определения какого-либо первоначального допустимого базисного решения задачи;

2) правило перехода к лучшему (точнее, не худшему) решению;

3) критерий проверки оптимальности найденного решения.

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

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

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

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

Для того чтобы задача имела оптимальное решение необходимо:

- чтобы ограничения задачи были совместимы;

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

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

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

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

Алгоритм:

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

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

;

;

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Стоимость:

X1 = 30 руб. ;

X2 = 28 руб;

X3 = 150 руб.

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

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

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

.

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

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

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



;

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

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

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

	-1	0	30	28	150	0	0	0
	C	B	X1	X2	X3	X7	X8	X9
X4	0	21,4	0,3	0,32	3,25	0	0	0
X5	0	5	0	0	1	0	0	0
X6	0	136	1	1	1	0	0	0
Y1	-M	60	1	0	0	-1	0	0
Y2	-M	10	0	1	0	0	-1	0
Y3	-M	5	0	0	1	0	0	-1
	?i	F0(x) -75M	-M-30	-M-28	-M-150	M	M	M

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

(руб.)

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

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

-M-30;

-M-28;

-M-150.

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

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

16,25ч1=16,25;

136ч1=136;

5ч1=5.

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

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

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

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

	-1	0	30	28	0	0	0
	C	B	X1	X2	X7	X8	X9
X4	0	21,4	0,3	0,32	0	0	0
X5	0	0	0	0	0	0	1
X6	0	131	1	1	0	0	1
Y1	-M	60	1	0	-1	0	0
Y2	-M	10	0	1	0	-1	0
X3	150	5	0	0	0	0	-1
		F1(x) -70M+750	-M-30	-M-28	M	M	-150

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

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

21,4ч0,3=71,333;

131ч1=131;

60ч1=60.

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

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

-M-30;

-M-28;

-150.

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

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

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

	-1	0	200	0	0	0
	C	B	X2	X7	X8	X9
X4	0	3,4	0,32	0,3	0	0
X5	0	0	0	0	0	1
X6	0	71	1	1	0	1
X1	30	60	0	-1	0	0
Y2	-M	10	1	0	-1	0
X3	150	5	0	0	0	-1
	?i	F2(x) -M+2550	-М-28	-30	М	М

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

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

3,4ч0,32=10,625;

71ч1=71;

10ч1=10.

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

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

-M-28;

-30.

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

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

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

	-1	0	0	0	0
	C	B	X7	X8	X9
X4	0	0,2	0,3	0,32	0
X5	0	0	0	0	1
X6	0	61	1	1	1
X1	30	60	-1	0	0
X2	28	10	0	-1	0
X3	150	5	0	0	-1
	?i	F3(x) 2830	-30	-28	-150

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

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

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

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

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

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

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

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

	-1	0	0	0	0
	C	B	X7	X8	X9
X4	0	0,2	0,3	0,32	0
X9	0	0	0	0	1
X6	0	61	1	1	-1
X1	30	60	-1	0	0
X2	28	10	0	-1	0
X3	150	5	0	0	1
	?i	F4(x) 2830	-30	-28	150

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

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

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

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

	-1	0	0	0	0
	C	B	X4	X8	X 5
X7	0	0,66	3,3	1,06	0
X9	0	0	0	0	1
X6	0	60,33	-0,3	-0,02	-1
X1	30	60,66667	0,3	0,32	0
X2	28	10	0	1	0
X3	150	5	0	0	1
	?i	F5(x) 2850	9	37,6	150

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

Все относительные оценки положительные и среди базисных переменных нет искусственных, следовательно, план является оптимальным и задача решена, решение находится в столбце 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 с.

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

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

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

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

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

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

Размещено на Allbest.ru