Линейное программирование

  • 06 апр. 2012 г.
  • 2048 Слова
Введение
Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.
Линейное программирование является частным случаем выпуклого программирования, которое в свою очередь является частным случаем математического программирования. Одновременнооно — основа нескольких методов решения задач целочисленного и нелинейного программирования. Одним из обобщений линейного программирования является дробно-линейное программирование.
Многие свойства задач линейного программирования можно интерпретировать также как свойства многогранников и таким образом геометрически формулировать и доказывать их.
Термин «программирование» нужно понимать всмысле «планирования». Он был предложен в середине 1940-х годов Джорджем Данцигом, одним из основателей линейного программирования, ещё до того, как компьютеры были использованы для решения линейных задач оптимизации.
Линейное программирование является основным разделом математического программирования. Термин математическое программирование 1950г. предложил математик Р. Дорфман. Впервые официально онпоявился, по-видимому, в 1959
в названии международного вещания: The Rano Symposium on mathematical programming, Santa Monica, California (1959). Содержание математического программирования составляют теория и методы решения задач о нахождении экстремумов функций на множествах, определяемых линейными и нелинейными ограничениями (равенствами и/или неравенствами). Математическое программирование являетсяодним из разделов науки об исследовании операций.
К задачам линейного программирования относятся задачи, в которых требуется найти максимальное или минимальное значение некоторой линейной целевой функции на множестве, определяемом системой линейных равенств или неравенств. В линейном программировании существует класс задач, структура которого позволяет создать специальные методы их решения, выгодноотличающиеся от методов решения задач общего характера. Так в линейном программировании появился раздел транспортных задач.
Наиболее исследованной областью математического программирования является линейное программирование. Полученные результаты столь значительны, что достигнутый здесь уровень позволяет решать большинство практических задач.
При выборе наиболее подходящего способа описанияреальных процессов приходится сталкиваться с рядом трудностей, которые можно подразделить на две группы. Одна группа связана с построением математической модели процесса, а другая - с методами решения этой модели. Теория математических моделей является предметом специального курса и требует от исследователя знания той области, которой принадлежит моделируемый объект, Здесь же будут рассмотренытрадиционные примеры, иллюстрирующие применение метода математического моделирования в экономических задачах.
Для практического решения экономической задачи математическими методами, прежде всего ее следует записать с помощью математических выражений (уравнений, неравенств и т.п.), т.е. составить экономико-математическую модель.

Глава I Линейное программирование
§ 1.1 История зарождения и созданиялинейного программирования.

Каждый человек ежедневно, не всегда осознавая это, решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда ограничены. Жизнь была бы менее интересной, если бы это было не так. Не трудно выиграть сражение, имея армию в 10 раз большую, чем у противника. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надосоставить план, или программу действий. Раньше план в таких случаях составлялся “на глазок” (теперь, впрочем, зачастую тоже). В середине XX века был создан специальный математический аппарат, помогающий это делать “по науке”. Соответствующий раздел математики называется математическим программированием. Слово “программирование” здесь и в аналогичных терминах (“линейное...
tracking img