Содержание
Введение3
Общая задача линейного программирования4
Формула задачи4
Геометрическая интерпретация задачи линейного программирования6
Графический метод решения задачи линейного программирования8
Область применения8
Выдержка из текста работы
Постановка задачи линейного программирования идвойственная задача линейного программирования.Линейное программирование является составной частьюраздела математики, который изучает методы нахождения условного экстремумафункции многих переменных и называется математическим программированием. Вклассическом математическом анализе рассматривается задача отыскания условногоэкстремума функции.Тем не менее, время показало, что для многих задач,возникающих под влиянием запросов практики, классические методы недостаточны.
Всвязи с развитием техники, ростом промышленного производства и с появлением ЭВМвсе большую роль начали играть задачи отыскания оптимальных решений в различныхсферах человеческой деятельности.Основным инструментом при решении этих задачстало математическое моделирование формальное описание изучаемого явления иисследование с помощью математического аппарата.Искусство математическогомоделирования состоит в том, чтобы учесть как можно больше факторов повозможности простыми средствами.
Именно в силу этого процесс моделированиячасто носит итеративный характер. На первой стадии строится относительнопростая модель и проводится ее исследование, позволяющее понять, какие из существенныхсвойств изучаемого объекта не улавливаются данной формальной схемой.Затем происходитуточнение, усложнение модели.В большинстве случаевпервой степенью приближения к реальности является модель, в которой всезависимости между переменными, характеризующими состояние объекта,предполагаются линейными.
Здесь имеется полная аналогия с тем, как весьма важнаи зачастую исчерпывающая информация о поведении произвольной функции получаетсяна основе изучения ее производной происходит замена этой функции вокрестности каждой точки линейной зависимостью. Значительное количество экономических,технических и других процессов достаточно хорошо и полно описывается линейнымимоделями.Основные формы задачи ЛП.Различают три основныеформы задач линейного программирование в зависимости от наличия ограниченийразного типа.Стандартная задача ЛП.или, в матричной записи,где матрица коэффициентов.
Вектор называется вектором коэффициентов линейной формы, вектором ограничений.Стандартная задача важна ввиду наличия большого числа прикладныхмоделей, сводящихся наиболее естественным образом к этому классу задач ЛП.Каноническая задача ЛП.или, в матричной записи,Основные вычислительные схемы решения задач ЛПразработаны именно для канонической задачи.Общая задача ЛП.В этой задачи часть ограничений носит характернеравенств, а часть является уравнениями.
Кроме того, не на все переменныеналожено условие неотрицательности Здесь . Ясно, что стандартная задача получается как частныйслучай общей при каноническая при . Все три перечисленные задачи эквивалентны в том смысле,что каждую из них можно простыми преобразованиями привести к любой из двухостальных.При изучении задач ЛП сложилась определеннаятерминалогия.Линейная форма , подлежащая максимизации или минимизации , называется целевойфункцией.
Вектор , удовлетворяющий всем ограничениям задачи ЛП, называетсядопустимым вектором, или планом. Задача ЛП, для которой существуют допустимыевекторы, называется допустимой задачей. Допустимый вектор , доставляющий наибольшее значение целевой функции посравнению с любым другим допустимым вектором , т.е называется решением задачи, или оптимальным планом.Максимальноезначение целевой функции называется значением задачи.Двойственнаязадача линейного программирования.Рассмотрим задачу ЛП 1 или, в матричной записи, 2 Задачей, двойственной к 1 двойственной задачей ,называется задача ЛП от переменных вида 3 или, в матричной записи, 4 где .Правила построения задачи 3 по форме записи задачи 1 таковы в задаче 3 переменных столько же, сколькострок в матрице задачи 1 . Матрицаограничений в 3 транспортированная матрица . Вектор правой части ограничений в 3 служит векторомкоэффициентов максимизируемой линейной форме в 1 , при этом знаки неравенствменяются на равенство.
Наоборот, в качестве целевой функции в 3 выступаетлинейная форма, коэффициентами которой задаются вектором правой частиограничений задачи 1 , при этом максимизация меняется на минимизацию.
Надвойственные переменные накладывается условиенеотрицательности. Задача 1 , в отличии от двойственной задачи 3 называетсяпрямой.Теорема двойственности. Если взаимодвойственныезадачи 2 , 4 допустимы, то они обе имеют решение и одинаковое значение.Теорема равновесия.Пусть оптимальные планы прямой 1 и двойственной 3 задачсоответственно.
Тогда если то.
