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

Негосударственное частное  образовательное учреждение

среднего  профессионального  образования

«КРАСНОДАРСКИЙ КОЛЛЕДЖ

УПРАВЛЕНИЯ, ТЕХНИКИ И ТЕХНОЛОГИЙ»

 

КУРСОВАЯ  РАБОТА

по дисциплине  «Математические методы»

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

 

 

 

Работу выполнил:

студент группы 08-ПО-02                             Шабля Александр Александрович

Специальность:                                    230105 – «Программное        обеспечение

                                                               вычислительной техники и 

                                                               автоматизированных систем»

 

Руководитель:                                                преподаватель  

                                                                         Величко Тамара Ивановна

Краснодар 2011

Содержание

Введение……………………………………….....…….....……....……………….3

1 Постановка задачи оптимизации……….…………….…….................….……5

2 Описание симплекс метода.....…………………...……………..............……...6

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

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

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

4.1 Решение задания 2 графическим методом...................................….......18

4.2 Решение задания 2 симплекс методом………………………………....20

Заключение……………………………………………………………………….23

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

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

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

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

1) улучшение финансовых показателей;

2) повышение уровня производства;

3)наращивание объемов производства.

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

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

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

Предмет – сырьевая структура предприятия при планировании выпуска продукции.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1 Постановка задачи оптимизации

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

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

Составной частью методов  оптимизации является линейное программирование.

 

 

 

 

 

 

2 Описание симплекс  метода

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

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

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

Пусть требуется найти максимальное значение функции

при условиях

Здесь и – заданные постоянные числа

Векторная форма данной задачи имеет  следующий вид: найти максимум функции

при условиях

где

Так как

то по определению опорного плана  является опорным планом данной задачи (последние компонент вектора Х равны нулю). Этот план определяется системой единичных векторов которые образуют базис m-мерного пространства. Поэтому каждый из векторов а также вектор могут быть представлены в виде линейной комбинации векторов данного базиса. Пусть

Положим Так как векторы – единичные, то и а

Теорема оптимальности опорного плана

(признак оптимальности опорного  плана). Опорный план задачи является оптимальным, если для любого j

Теорема об ограничении целевой функции на множестве ее планов

Если для некоторого j=k и среди чисел нет положительных , то целевая функция задачи не ограничена на множестве ее планов.

Если опорный план Х задачи невырожден и , но среди чисел есть положительные (не все ), то существует опорный план X' такой, что

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

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

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

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

В таблице 1 первые m строк определяются исходными данными задачи, а показатели (m+1)-й строки вычисляют. В этой строке в столбце вектора записывают значение целевой функции, которое она принимает при данном опорном плане, а в столбце вектора – значение

Значение Zj находится как скалярное произведение вектора на вектор

Значение  равно скалярному произведению вектора P0 на вектор :

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

1) для j=m+1, (при ). Поэтому в данном случае числа для всех j от 1 до n;

2) для некоторого j, и все соответствующие этому индексу величины

3) для некоторых индексов j, и для каждого такого j , по крайней мере, одно из чисел положительно.

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

Для определения вектора, подлежащего  исключению из базиса, находят  для всех Пусть этот минимум достигается при i=r. Тогда из базиса исключают вектор , а число называют разрешающим элементом.

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

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

а коэффициенты разложения векторов через векторы нового базиса, соответствующего новому опорному плану, – по формулам

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

либо на основании их определения.

Таблица 2.1 – Первая симплекс таблица

Наличие двух способов нахождения элементов  -й строки позволяет осуществлять контроль правильности проводимых вычислений.

 

 

 

Таблица 2.2 – Вторая симплекс таблица

Из формулы 

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

.

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

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

 так и по правилам, непосредственно  вытекающим из них. Эти правила  состоят в следующем.

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

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

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

1) число, стоящее в исходной  симплекс-таблице на месте искомого  элемента новой симплекс-таблицы;

2) число, стоящее в исходной  симплекс-таблице на пересечении  строки, в которой находится искомый  элемент новой симплекс-таблицы,  и столбца, соответствующего вектору,  вводимому в базис;

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

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

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

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

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

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г.