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

Санкт-петербургский  Институт Внешнеэкономических

Связей, Экономики и Права

Факультет Международных Отношений 
 
 
 
 
 
 

Аналитическая работа по дисциплине:

Математические  методы исследования международных отношений 

На тему:

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

Студентка 422  группы

                                                                 специальность

                                                                 «Международные отношения» 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Санкт - Петербург

2011 

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

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

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

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

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

    Линейное  программирование применяется при  решении экономических задач, в  таких задачах как управление и планирование производства; в задачах  определения оптимального размещения оборудования на морских судах, в  цехах; в задачах определения  оптимального плана перевозок груза (транспортная задача); в задачах  оптимального распределения кадров и т.д.

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

    Общая форма задачи имеет вид: при условиях

где

 

Возможные тематики задач ЛП:

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

 

Пример 

    Исторические  задача о диете является одной  из первых задач линейного программирования.

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

    Даме  необходимо похудеть, за помощью обратилась к подруге.

    Построение  модели - рассмотрение этого этапа  и является главной целью.

    Подруга посоветовала перейти на рациональное питание, состоящее из двух продуктов P и Q.

    Суточное  питание этими продуктами должно давать не более 14 единиц жира (чтобы  похудеть), но не менее 300 калорий. На упаковке продукта Р написано, что в одном  килограмме этого продукта содержится 15 единиц жира и 150 калорий, а на упаковке с продуктом Q - 4 единицы жира и 200 калорий соответственно. При этом цена 1 килограмма продукта Р равна 15 руб., а 1 кг продукта Q - 25 руб.

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

    Перейдем  к формализации данной ситуации на языке математических символов.

    Обозначим через х количество продукта Р  и через у количество продукта Q, требуемые для выполнения условий  диеты.

    Количество  единиц жира, содержащегося в х  кг продукта Р и в у кг продукта Q, равно 15х + 4 и по условию диеты  не должно превосходить 14: 

 
 

    В свою очередь, количество калорий, содержащихся в х кг продукта Р и в у  кг продукта Q, равно 150х + 200у и по условию диеты должно быть не меньше 300: 

 

Теперь  о стоимости z продуктов. Она равна 

 

и в  соответствии с высказанными пожеланиями  должна быть минимальной. 

Последнее записывается так 

 

Тем самым  мы получили систему формул 

 

которую решим графическим способом. 

 

Нас интересует только та ее часть, которая лежит  над треугольником BDE. Вычисляя значения z во всех трех вершинах этого треугольника 

 

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

и искомая  пропорция - 2 : 3.