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

СОДЕРЖАНИЕ

 

ВВЕДЕНИЕ………………………………………………………….…………….3

Глава 1. «Основные теоретические положения симплексного метода при решении задач линейного программирования»………………………………...5

1. Теория линейного программирования………………………………..5
2. Общая задача и основные понятия линейного программирования…7
3. Особенности симплекс-метода………………………………………13

Глава 2. «Решение задач линейного программирования симплексным методом»………………………………………………………………………...15

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

2.2 Рассмотрение примера решения задачи линейного программирования………………………………………………………..18

2.2.1 Постановка задачи……………………………………………..18

2.2.2 Построение математической модели поставленной задачи…………………………………………………………………19

2.2.3 Решение ЗЛП графическим методом на примере задачи о выпуске продукции …………………………………………………20

2.2.4 Решение ЗЛП симплекс-методом на примере задачи о выпуске продукции.……………………………………….…….…..23

ЗАКЛЮЧЕНИЕ ……………………………………………………………..…. 38

СПИСОК ЛИТЕРАТУРЫ ...…………………..……………………………… ..40

 

ВВЕДЕНИЕ

 

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

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

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

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

• улучшение финансовых показателей;
• повышение уровня производства;
• наращивание объемов производства.

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

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

Цель данной курсовой работы: изучить и научиться применять на практике симплекс-метод для решения конкретной задачи линейного программирования.

 

ОСНОВНЫЕ ТЕОРЕТИЧЕСКИЕ  ПОЛОЖЕНИЯ СИМПЛЕКСНОГО МЕТОДА ПРИ  РЕШЕНИИ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

 

Теория линейного  программирования

 

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

Решить подобную задачу бывает непросто, особенно при наличии большого числа вариантов. Время и затраты  при выборе оптимума не всегда оправданны: издержки поиска и перебора вариантов  могут превысить достигнутый  выигрыш. Как показывает практика, опыт и интуиция оказываются недостаточными для обоснования оптимального решения. Более надежный и эффективный  способ — использование математических (количественных) подходов и расчетов. Однако математические подходы и  обоснования длительное время игнорировались. Многие важные работы были заморожены, публикации экономистов-математиков  тормозились и ограничивались. И  все же в тот период математические изыскания продолжались, даже в условиях гонения на математиков были достигнуты блестящие результаты. Одним из наиболее значительных и ярких достижений в области экономико-математических исследований было открытие Леонидом Витальевичем Канторовичем (1912—1986) Метода линейного программирования

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

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

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

Общая задача и основные понятия линейного программирования

Линейное программирование - наиболее разработанный и широко применяемый  раздел математического программирования. Это объясняется следующим:

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

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

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

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

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

 

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

Имеются какие-то переменные х = (х₁ , х₂ , … х_n ) и функция этих переменных f(x) = f (х₁ , х₂ , … х_n ), которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции f(x) при условии, что переменные x принадлежат некоторой области G:

 

 

В зависимости от вида функции f(x) и области G и различают разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное программирование и т.д. Линейное программирование характеризуется тем, что  
а) функция f(x) является линейной функцией переменных х₁ , х₂ , … х_n 
б) область G определяется системой линейных равенств или неравенств.

Математическая модель любой задачи линейного программирования включает в себя:

• максимум или минимум целевой функции (критерий оптимальности);
• систему ограничений в форме линейных уравнений и неравенств;
• требование неотрицательности переменных.

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

 

 

 

Коэффициенты a_i,j, b_i, c_j, j = 1, 2, ... , n, i =1, 2, ... , m – любые действительные числа (возможно 0).

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

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

В канонической форме задача является задачей на максимум (минимум) некоторой линейной функции F, ее система ограничений состоит только из равенств (уравнений). При этом переменные задачи х₁, х₂, ..., х_n являются неотрицательными:

 

 

 

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

Правило приведения ЗЛП к каноническому виду:

1. Если в исходной задаче некоторое ограничение (например, первое) было неравенством, то оно преобразуется в равенство, введением в левую часть некоторой неотрицательной переменной, при чем в неравенства «≤» вводится дополнительная неотрицательная переменная со знаком «+»; в случаи неравенства «≥» - со знаком «-»

 

Вводим переменную

 

Тогда неравенство запишется в  виде:

 

В каждое из неравенств вводится своя “уравнивающая” переменная, после чего система ограничений становится системой уравнений.

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

, l - свободный индекс

3. Если в ограничениях правая  часть отрицательна, то следует  умножить это ограничение на (-1)

4. Наконец, если исходная задача  была задачей на минимум, то  введением новой целевой функции F₁ = -F мы преобразуем нашу задачу на минимум функции F в задачу на максимум функции F₁.