Реализация симплекс–метода в случае положительных свободных членов

Введение

 

В данной курсовой работе я хочу представить метод решения «Реализация симплекс-метода в случае положительных свободных членов».

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

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

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

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

Действительно, путь необходимо исследовать на экстремум линейную функцию

 

Z = С1х1+С2х2+... +СNxN

при линейных ограничениях

a11x1 + a22x2 + ... + a1NХN = b1

a21x1 + a22x2 + ... + a2NХN = b2

. . . . . . . . . . . . . . .

aМ1x1 + aМ2x2 + ... + aМNХN = bМ

 

Так как Z - линейная функция, то Z = Сj, (j = 1, 2, ..., n), то все коэффициенты линейной функции не могут быть равны нулю, следовательно, внутри области, образованной системой ограничений, экстремальные точки не существуют. Они могут быть на границе области, но исследовать точки границы невозможно, поскольку частные производные являются константами.

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

 

1. Решение задач линейного программирования средствами табличного процессора Excel

 

Электронные таблицы MS Excel содержат модуль «Поиск решения» позволяющий осуществлять поиск оптимальных решений, в том числе решение задач линейного и нелинейного программирования.

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

В качестве параметров режима задаются ограничения по времени поиска решения в секундах (Максимальное время) (максимально 32767), количеству итераций (Предельное число итераций), точности соответствия результата заданному значению (Относительная погрешность), допустимого отклонения экстремума от оптимального значения при использовании режима целочисленной математики (Допустимое отклонение), а также условие прекращения поиска экстремума (Сходимость), задающее величину относительного приращения экстремума за последние пять итераций.

Решение задачи линейного программирования средствами табличного процессора Excel осуществляется в режиме Сервис/Поиск решения, открывается диалоговое окно «Поиск решения». Здесь указывается ячейки целевой функции, переменных и устанавливаются ограничения исходя из системы ограничений. Можно начать решение, или установить «параметры» решения. симплекс линейное программирование прибыль

Решением задачи является рассчитываемый надстройкой Поиск решения набор переменных X = (x1, x2 ,..., xn), обеспечивающий максимальное (минимальное, заданное) значение целевой функции E(x1, x2 ,..., xn).

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

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

 

 

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

 

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

 

Система ограничений, в которой x1, x2 >= 0:

 

x2+x3<= 8

x1+x2<= 5

2x2 +x3<= 12

 

Целевая функция:

 

Z = 1x1 + 5x2 + 2x3 → max

 

2.2 Приводим задачу к каноническому виду

 

Введем дополнительные переменные х4 , х5 , х6. 

 

x2+x3+х4= 8

x1+x2+х5= 5

2x2 +x3+х6 = 12

 

Начальный опорный план

 

х0=(0, 0, 0, 8, 5, 12)

z0=z(x0)=1*0+5*0+2*0=0

z0-z=-1x1-5x2-2x3→ min

 

F(X)=

1

X1

+

5

X2

+

2

X3

(max)

 

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

0	X1	+	1	X2	+	1	X3	+	X4	=	8
1	X1	+	1	X2	+	0	X3	+	X5	=	5
0	X1	+	2	X2	+	1	X3	+	X6	=	12

 

Xi≥0

 

Составим симплекс таблицу:

Базисные переменные	Свободные члены	X1	X2	X3	X4	X5	X6
X4	8	0	1	1	1	0	0
X5	5	1	1	0	0	1	0
X6	12	0	2	1	0	0	1
z0-z	0	-1	-5	-2	0	0	0

 

Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. Так как в строке F есть отрицательные элементы, то полученное решение не оптимально. Для определения ведущего столбца найдем максимальный по модулю отрицательный элемент в строке F (-5). А ведущая строка та, у которой наименьшее положительное отношение свободного члена к соответствующему элементу ведущего столбца.

 

Пересчитаем таблицу

Базисные переменные	Свободные члены	X1	X5	X3	X4	X5	X6
X4	3	-1	-1	1	1	-1	0
X2	5	1	1	2	0	1	0
X6	2	-2	-2	1	0	-2	1
z0-z	25	4	5	-2	0	5	0

 

Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. Так как в строке F есть отрицательные элементы, то полученное решение не оптимально. Для определения ведущего столбца найдем максимальный по модулю отрицательный элемент в строке F (-2). А ведущая строка та, у которой наименьшее положительное отношение свободного члена к соответствующему элементу ведущего столбца.

 

Пересчитаем таблицу

Базисные переменные	Свободные члены	X1	X5	X6	X4	X5	X6
X4	1	1	1	-1	1	1	-1
X2	5	1	1	0	0	1	0
X3	2	-2	-2	1	0	-2	1
z0-z	29	0	1	2	0	1	2

 

Так как в столбце «Свободные члены» нет отрицательных элементов, то найдено допустимое решение. Так как в строке «z0-z» тоже нет отрицательных элементов, то найдено допустимое решение.

Найдено оптимальное решение

 

3.3.Блок-схема

 

 

 

3.4 Анализ решения

 

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

В результате получены следующие результаты:

- сырье первого вида =5 л. ;

- план выпуска продукции =58,25;

- сырье второго вида = 8 л.

В ходе решения задачи было построено 3 симплексные таблицы:

1. Первая симплексная таблица была построена по исходным данным;
2. В результате построения второй симплексной таблицы было вычислено максимальное количество ед. сырья второго вида = 8 л.;
3. В результате построения третьей симплексной таблицы было вычислено максимальное количество ед. сырья первого вида =0,75 л.;
4. Т. к. в третьей симплексной таблице в строке целевой функции все элементы стали оптимальными, завершили решение;
5. Из третьей симплексной таблицы выписываем необходимые данные: количество сырья первого и второго вида. После чего высчитываем максимальный план выпуска продукции – подставляя в целевую функцию полученные в ходе решения данные (8 и 0,75 ) и получаем 43 цен.ед.

 

Вывод

 

В данной курсовой работе я представил метод решения «Реализация симплекс-метода в случае положительных свободных членов».

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

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