Размещено на http://www.allbest.ru/

Содержание

• Введение
• 1. Симплекс-метод
• 1.1 Общая характеристика симплекс-метода
• 1.2 Двухфазный симплекс-метод
• 1.3 Общая идея симплекс-метода
• 1.4 Вычислительная эффективность симплекс-метода
• 1.5 Примеры использования симплекс-метода
• 1.6 Алгоритм решения ЗЛП симплексным методом
• 1.7 Решение задачи с помощью симплекс-метода
• 1.8 Упрощенный вариант решения задачи в Microsoft Excel
• Заключение
• Список использованной литературы


Введение

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

Временем рождения линейного программирования принято считать 1939г., когда была напечатана брошюра Леонида Витальевича Канторовича "Математические методы организации и планирования производства". Поскольку методы, изложенные Л.В. Канторовичем, были мало пригодны для ручного счета, а быстродействующих вычислительных машин в то время не существовало, работа Л.В. Канторовича осталась почти не замеченной.

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

Исторически общая задача линейного программирования была впервые поставлена в 1947 году Джорджем Бернардом Данцигом, Маршаллом Вудом и их сотрудниками в департаменте военно-воздушных сил США. В то время эта группа занималась исследованием возможности использования математических и смежных с ними методов для военных задач и проблем планирования. В дальнейшем для развития этих идей в ВВС была организована исследовательская группа под названием Project SCOOP. Первое успешное решение задачи линейного программирования на ЭВМ SEAC было проведено в январе 1952 года.

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

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

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

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



1. Симплекс-метод

1.1 Общая характеристика симплекс-метода

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

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

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

W(x) = c,

где W(x) - максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость L(c). Зависимость от c порождает семейство параллельных гиперплоскостей. Тогда экстремальная задача приобретает следующую формулировку - требуется найти такое наибольшее c, что гиперплоскость L(c) пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину, причём, их будет более одной, если пересечение содержит ребро или k-мерную грань. Поэтому максимум функционала можно искать в вершинах многогранника. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его рёбрам от вершины к вершине в сторону увеличения значения функционала. Когда переход по ребру из текущей вершины в другую вершину с более высоким значением функционала невозможен, считается, что оптимальное значение С найдено.

Последовательность вычислений симплекс-методом можно разделить на две основные фазы:

- нахождение исходной вершины множества допустимых решений;

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

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

1.2 Двухфазный симплекс-метод

симплекс компьютер программный алгоритм

Причины использования

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

Модификация ограничений

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

- ограничения типа "?" переводятся на равенства созданием дополнительной переменной с коэффициентом "+1". Эта модификация проводится и в однофазном симплекс-методе, дополнительные переменные в дальнейшем используются как исходный базис;

- ограничения типа "?" дополняются одной переменной с коэффициентом "?1". Поскольку такая переменная из-за отрицательного коэффициента не может быть использована в исходном базисе, необходимо создать ещё одну, вспомогательную, переменную. Вспомогательные переменные всегда создаются с коэффициентом "+1";

- ограничения типа "=" дополняются одной вспомогательной переменной.

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

Различия между переменными

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

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

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

То есть ненулевое значение дополнительной переменной может (но не должно) сигнализировать о неоптимальности решения. Ненулевое значение вспомогательной переменной сигнализирует о недопустимости решения.

1.3 Общая идея симплекс-метода

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

Симплекс метод - универсальный метод для решения линейной системы уравнений или неравенств и линейного функционала.

Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП (задачи линейного программирования) состоит:

- умение находить начальный опорный план;

- наличие признака оптимальности опорного плана;

- умение переходить к нехудшему опорному плану.

1.4 Вычислительная эффективность симплекс-метода

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

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

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

Вычислительная эффективность оценивается обычно при помощи двух параметров:

- Числа итераций, необходимого для получения решения;

- Затрат машинного времени.

В результате численных экспериментов получены результаты:

- Число итераций при решении задач линейного программирования в стандартной форме с M ограничениями и N переменными заключено между M и 3M. Среднее число итераций 2M. Верхняя граница числа итераций равна 2M+N;

- Требуемое машинное время пропорционально .

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

Методы повышения эффективности

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

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

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

- Частичное оценивание;

- Циклический просмотр. Поиск вводимой переменной начинается с позиции, следующей за введённой на предыдущей итерации переменной;

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

- Назначение весов. Переменным назначаются веса;

- Поиск наиболее крутого ребра Гольдфарба и Рида. Метод оценивания с поиском наиболее крутого ребра.

Возможны и другие приёмы, такие как правило Заде.

1.5 Примеры использования симплекс-метода

Задачи линейного программирования нашли широкое применение в экономике. Рассмотрим показатели эффективности, которые использование симплекс-метода может вывести при решении задач.

Пример 1.

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

Пример 2.

Группа истребителей поднимается в воздух для перехвата одиночного самолёта противника. Цель операции - сбить самолёт. Показатель эффективности - вероятность поражения цели.

Пример 3.

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

Пример 4.

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

Пример 5.

Предпринимается ряд мер по повышения надёжности электронной цифровой вычислительной техники. Цель операции - уменьшить частоту появления неисправностей ("сбоев") ЭЦВТ, или, что равносильно, увеличить средний промежуток времени между сдоями ("наработку на отказ"). Показатель эффективности - среднее время безотказной работы ЭЦВТ.

Пример 6.

Проводится борьба за экономию средств при производстве определённого вида товара. Показатель эффективности - количество сэкономленных средств.

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

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

1.6 Алгоритм решения ЗЛП симплексным методом

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

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

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

Таблица 1.5 Пример симплекс-таблицы

Третий шаг. На третьем шаге пересчитываем всю симплекс-таблицу по специальным формулам.

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

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

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

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

Оптимизация ресурсов фабрики

Для изготовления изделий А, Б, В и С фабрика расходует в качестве сырья сталь и цветные металлы, имеющиеся в ограниченном количестве. Указанные изделия производят с помощью токарных и фрезерных станков. Определить план выпуска продукции, при котором будет достигнута максимальная прибыль. Необходимые данные приведены в Таблице 1.6:

Таблица 1.6

Вид ресурса	Объем ресурса	Нормы расхода на одно изделие
		А	Б	В	С
Сталь, кг	250	10	20	15	18
Цв. Металлы, кг	40	0	5	8	7
Токарные станки, станко-час	100	15	18	12	20
Фрезерные станки, станко-час	80	8	12	11	10
Прибыль, ден. ед.	4	2	4	3

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

Обозначим через , , , - количество изделий каждого вида соответственно, планируемого к выпуску, а через f-величину прибыли от реализации этих изделий. Тогда, учитывая значение прибыли от единицы продукции П1 = 4 ден. ед., П2= 2 ден. ед., П3= 4 ден. ед., П4= 3 ден. ед., запишем суммарную величину прибыли - целевую функцию - в следующем виде:

f = 4 + 2 +4+ 3 (мах) (2.1)

Переменные , , , должны удовлетворять ограничениям, накладываемым на расход имеющихся в распоряжении предприятия ресурсов. Так, затраты ресурса (сталь, кг) на выполнение плана (, , , ) составят (10 + 20 +15+18) ед., где 10 - затраты ресурса на выпуск ед. изделий А; 20- затраты ресурса на выпуск ед. изделий Б и так далее. Понятно, что указанная сумма не может превышать имеющийся запас в 250 кг., т.е.

10 + 20 +15+18?250 (2.2)

Аналогично получаем ограничение по расходу ресурса (цветные металлы, кг.)

0 + 5+ 8+ 7?40 (2.3)

ограничение по расходу ресурсов (токарные станки, станко-час)

15 + 18+12+ 20 ?100 (2.4)

ограничение по расходу ресурсов (фрезерные станки, станко-час)

8 + 12 + 11+ 10 ?80. (2.5)



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

Хj ?0 (j=1,4) (2.6)

Соотношения (2.1) - (2.6) образуют экономико-математическую модель данной задачи.

Итак, математически задача сводится к нахождению числовых значений *, *, *, * переменных , , , , удовлетворяющих линейным неравенствам (2.2) - (2.6) и доставляющих максимум линейной функции (2.1)

Прежде чем решать задачу линейного программирования симплекс-методом, ее модель приводят к канонической форме. Основным признаком канонической формы является запись ограничений задачи в виде равенств. В нашем же случае ограничения (2.2) - (2.5) имеют вид неравенств типа "?". Чтобы преобразовать их в эквивалентные уравнения, введем в левые части неравенств дополнительные (балансовые) неотрицательные переменные , , , , обозначающие разности между правыми и левыми частями этих неравенств. В результате модель можно записать в виде

f = 75 + 35 +40 +20 (мах) (2.7)

10 + 20 +15+18+ = 250

0 + 5 + 8+ 7 + = 40

15 + 18 +12+ 20 + = 100 (2.8)

8 + 12 + 11+ 10 + = 80

Хj ?0 (j=1,8) (2.9)

Заметим здесь же, что дополнительные переменные ,, , имеют вполне определенный экономический смысл - это возможные остатки ресурсов соответственно , , . Их еще называют резервами.

Анализируя каноническую модель (2.7) - (2.9), замечаем, что каждая из переменных , , , входит только в одно из уравнений системы (2.8). Это обстоятельство свидетельствует о том, что в системе (2.8) переменные , , , являются базисными, а остальные переменные , , , - свободными. В связи с этим в первую симплекс-таблицу систему ограничительных уравнений (2.7) можно записать в виде, разрешенном относительно базиса , , , (табл. 2.1).

Таблица 1

БП	1	СП
		- Х 1	- Х 2	- Х 3	- Х 4
Х 5=	250	10	20	15	18
Х 6=	40	0	5	8	7
Х 7=	100	15	18	12	20
Х 8=	80	8	12	11	10
f		-4	-2	-4	-3

Все элементы столбца свободных членов положительны, поэтому содержащийся в Таблице 1 план (0; 0; 0; 0; 250; 40; 100; 80), является опорным. Однако этот план не является оптимальным: в f - строке имеются отрицательные элементы.

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

Min(250/10; 40/0; 100/15; 80/8)= 100/15 = 6,667

Итак, из базиса надо исключить переменную, стоящую в третьей (разрешающей) строке, то есть . На пересечении разрешающих столбца и строки находится разрешающий элемент 15, с которым и выполняется симплексное преобразование (шаг жорданова исключения). В результате приходим к Таблице 2.

В f-строке Таблицы 2 есть отрицательные элементы, значит, опорный план оптимальным не является.

Таблица 2

БП	1	СП
		- Х 7	- Х 2	- Х 3	- Х 4
Х 5=	183,3	-0,667	8	7	4,667
Х 6=	40	0	5	8	7
Х 1=	6,667	0,067	1,2	0,8	1,333
Х 8=	26,667	-0,533	2,4	4,6	0,667
F	26,667	0,267	2,8	-0,8	2,333

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

Таблица 3

БП	1	СП
		- Х 7	- Х 2	- Х 6	- Х 4
Х 5=	148,3	-0,667	3,625	-0,875	-1,46
Х 3=	5	0	0,625	0,125	0,875
Х 1=	2,667	0,0667	0,7	-0,1	0,633
Х 8=	3,667	-0,5333	-0,475	-0,575	-4,69
F	30,667	0,2667	3,3	0,1	3,033

Следовательно, опорный план (2,667; 0; 5; 0; 148,3; 0; 0; 3,667) является оптимальным, а соответствующее ему значение 30,667 целевой функции будет максимальным.

Итак, по оптимальному плану следует производить 2,667 ед. изделий А; 0 ед. изделий Б; 5 ед. изделий В; 0 ед. изделий С.

При этом предприятие получит максимальную прибыль в размере 30,667 ден. ед. Останутся неиспользованными 148,3 ед. ресурса (сталь, кг.), и 3,667 ед. ресурса (фрезерные станки, станко-час), а ресурсы и будут израсходованы полностью.

1.8 Упрощенный вариант решения задачи в Microsoft Excel

Сделаем форму и введем исходные данные:

Введем зависимости

Чтобы получить значение целевой функции в ячейке F5, воспользуемся функцией СУУММПРОИЗВ. Для этого поместим курсор в ячейку F5 и с помощью команды МАСТЕР ФУНКЦИЙ вызовем математическую функцию СУММПРОИЗВ. На экране появится ее диалоговое окно. В массив 1 ввести строку со значениями переменных, то есть $B$3:$E$3. В массив 2 ввести адрес строки коэффициентов целевой функции, то есть B5:E5. Копируем формулу из ячейки E5 в ячейки E7, E8, E9,E10.

Решение задачи осуществляем с помощью средства Поиск решения из меню Сервис:

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

Оптимальное значение целевой функции при целочисленном решении будет 28 ден.ед., что на 2,667 ден. ед. меньше, чем при нецелочисленном решении.

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



Заключение

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

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

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



Список использованной литературы

1. Акулич И.Л. Математическое программирование в примерах и задачах: учеб.пособие для ВУЗов / И.Л. Акулич. - М.: Высшая школа, 1986.

2. Гончаров Е.Н. Исследование операций. Примеры и задачи: учеб.пособие / Е.Н. Гончаров, А.И. Ерзин, В.В. Залюбовский. -Н.: Гос. ун-т. Новосибирск, 2005.

3. Павлова Т.Н. Линейное программирование: учеб.пособие / Т.Н. Павлова, О.А. Ракова. - Д.: 2002.

4. БерюховаТ.Н.Банк производственных задач в расчетах на ЭВМ: учебное пособие. - Тюмень.: ТюмИИ, 1992. - 124с.

5. Карманов В.Г. Математическое программирование: учебное пособие для студентов вузов. - М.: Физматлит, 2001. - 264с.

6. Кузнецов А.В. Математическое программирование: учебное пособие для вузов. - М.: Высшая школа, 1976. - 352с.

7. Мочалов И.А. Нечеткое линейное программирование. // Промышленные АСУ и контроллеры. - 2006. - № 10. - с.26-29.

8. Пашутин С.Оптимизация издержек и технология формирования оптимального ассортимента. // Управление персоналом. - 2005. - №5. - с.20-24.

9. Жиглявский А.А., Жилинкас А.Г. Методы поиска глобального экстремума. - М.: Наука, Физматлит, 1991.

10. Карманов В.Г. Математическое программирование = Математическое программирование. - Изд-во физ.-мат. литературы, 2004.

11. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. - М.: Наука, 1970. - С. 575-576.

12. http://ru.wikipedia.org/wiki

13. http://revolution.allbest.ru

Размещено на Allbest.ru

...