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

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

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

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

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

 

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

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

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

 

 

 

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

студент группы 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.

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

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

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

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

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

После заполнения таблицы 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) число, стоящее в новой симплекс-таблице  на пересечении столбца, в котором  стоит искомый элемент, и строки  вновь вводимого в базис вектора  (как отмечено выше, эта строка  получается из строки исходной  симплекс-таблицы делением ее  элементов на разрешающий элемент).