Решение задач симплекс-методом

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

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

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

Итак, нахождение оптимального плана  симплексным методом включает следующие  этапы:

1) Находят опорный план;

2) Составляют симплекс-таблицу;

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

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

5) По формулам

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3 Постановка задания  1

Найти область решения:

 

 

                                                 

3.1 Решение задания 1

 

                                     

Приведем данную систему неравенств в новую систему равенств

 

                                                 

Найдем точки решения  каждого из данных уравнений

 

Подставим в данное уравнение , получим

;  ;  

Подставим в данное уравнение , получим

; 

Построим график этой функции  через точки

	0	5
	-1	0

 

 

Подставим в данное уравнение , получим

;   ;  

Подставим в данное уравнение ,

Построим график этой функции  через точки

	0	3
	1	0

 

 

Построим график этой функции через точки

	5	5
	2	-2

Многоугольник ABC с координатами вершин: A(5;0) , B(11,2;3,2) , C(5;0,8) является областью решения данной системы неравенств:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4 Постановка задания  2

Предприятие выпускает два  вида продукции: А и В, которая поступает в оптовую продажу. Для производства этих видов продукции используется три вида сырья. Расход сырья каждого вида на изготовление единицы продукции А соответственно а1, а2, а3. На изготовление единицы продукции В соответственно b1, b2, b3. Максимально возможные запасы сырья каждого вида в сутки составляют S1, S2, S3 кг соответственно. Оптовая цена единицы продукции А равна С1 руб., а единицы продукции В равна С2 руб. Требуется составить план производства каждого вида продукции, чтобы доход от реализации был максимальным.

Идентификация переменных:

x1 – суточный объем производства продукции А;

x2 – суточный объем производства продукции В.

Ограничения переменных:

а1	а2	а3	b1	b2	b3	S1	S2	S3	C1	C2
5	4	1	2	5	7	750	807	840	30	49

 

Цель задачи:

Найти оптимальный план максимизации прибыли от реализации продукции.

4.1 Решение задачи  графическим методом

Необходимо максимизировать функцию  при ограничениях:

 

 

 

 

 

 

Приведем данную систему неравенств в новую систему равенств

                                                                                           (L1)

                                                                                           (L2)

                                                                                           (L3)

Построим графики уравнений  по точкам:

(L1)    

	0	375
	150	0

 

(L2)

	0	201,7
	161,4	0

 

(L3)

	0	840
	120	0

 

Последней точкой через которую  проходит перпендикуляр к вектору  OR  является точка D(40;140) образуемая линиями L1 и L2.

                                                                               (L1)

                                                                              (L2)

Из первого уравнения  следует, что 

 

Подставив во второе уравнение  получим

, отсюда 

Подставим полученный x в первое уравнение, получим

, отсюда

Подставим полученные результаты в  ,получим отсюда

Вывод: чтобы получить 6757 надо запланировать 125,6 единиц товара А и 61 единицу товара В.

4.2 Решение задачи  симплекс методом

Необходимо максимизировать функцию  при ограничениях:

 

 

 

 

Приведем задачу к каноническому  виду, то есть представим систему ограничений  в виде равенств:

 

 

 

,, – базисные переменные; , – свободные переменные.

Первое базисное решение: 

 

 

 

 

Приведем задачу к жордановой форме:

 

 

 

 

Построим первую симплекс таблицу:

Таблица 4.2.1 - Симплекс таблица 1

			1
	5	2	750
	4	5	807
	1	7	840
	-30	-49	0

 

Разрешающий коэффициент  находится в ячейке на пересечении  столбца  
и строки и равен 7.

Построим вторую симплекс таблицу:

Таблица 4.2.2 - Симплекс таблица 2

			1
	4,714	-0,286	510
	3,286	-0,714	207
	0,143	0,143	120
	-23	7	5880

 

В строке целевой функции  имеются отрицательные элементы. Это означает что полученное решение не оптимально.

Второе базисное решение:

 

 

 

 

 

Разрешающий коэффициент  находится в ячейке на пересечении  столбца  
и строки и равен 3,286.

Построим третью симплекс таблицу:

Таблица 4.2.3 - Симплекс таблица 3

			1
	-1.435	0.739	213
	0.304	-0.217	63
	-0.043	0.174	111
	7	2	7329

 

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

Вывод: чтобы получить 7329 нужно запланировать 63 единицы товара А, и 111 единиц товара В.

 

 

 

 

 

 

 

 

Заключение

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

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

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

 

 

 

Список использованных источников

1 ГОСТ 7.32-2001 СИБИД. Отчёт  о научно-исследовательской работе. Структура и правила оформления. – Взамен ГОСТ 7.32-91; Введ. 01.07.2002. –  Минск: Изд-во стандартов, 2001.- 16с.

2 ГОСТ  2.105- 95 ЕСКД. Общие требования  к текстовым документам. – Взамен  ГОСТ 2.105-79, ГОСТ 2.906-71; Введ.07.01.96. – М.: Изд-во стандартов, 1996. – 36 с.

 

3 Курс записанных лекций  по предмету “Математические методы”

4 “Введение в системный анализ” Перегудов Ф.И., Тарасенко Ф.П. 1989г.

5 “Системный анализ” Антонов А.В. 2004г.