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

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

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

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1.ИСТОРИЯ ЗАРОЖДЕНИЯ И СОЗДАНИЯ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

2.ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГОПРОГРАММИРОВАНИЯ

2.1 Стандартная задача линейного программирования

2.2 Каноническая задача линейного программирования

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

2.4 Двойственная задача линейного программирования

2.5 Геометрическая интерпретация задачи линейного программирования

3.РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

3.1 Графический способ решения задачи линейного программирования

3.2 Метод исключения Жордана-Гаусса для системы линейных уравнений

4.ПРИМЕРЫ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

4.1 Задача о рациональном питании (задача о пищевом рационе

4.2 Задача о планировании производства

4.3 Задача о загрузки оборудования

4.4 Задача о снабжении сырьём

ЗАКЛЮЧЕНИЕ

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

Введение

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

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

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

В автобиографии, представленной в Нобелевский комитет, Леонид Витальевич Канторович рассказывает о событиях, случившихся в 1939 году. К нему, 26-летнему профессору-математику, обратились за консультацией сотрудники лаборатории планерного треста, которым нужно было решить задачу о наиболее выгодном распределении материала между станками. Эта задача сводилась к нахождению максимума линейной функции, заданной на многограннике. Максимум такой функции достигался в вершине, однако число вершин в этой задаче достигало миллиарда. Поэтому простой перебор вершин не годился. Леонид Витальевич писал: “оказалось, что эта задача не является случайной. Я обнаружил большое число разнообразных по содержанию задач, имеющих аналогичный математический характер: наилучшее использование посевных площадей, выбор загрузки оборудования, рациональный раскрой материала, распределение транспортных грузопотоков. Это настойчиво побудило меня к поиску эффективного метода их решения”. И уже летом 1939 года была сдана в набор книга Л.В.Канторовича “Математические методы организации и планирования производства”, в которой закладывались основания того, что ныне называется математической экономикой.

1.История зарождения и создания линейного программирования

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

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

Примерно в это время Купманс узнал, что еще до войны в далекой России уже было сделано нечто похожее на разработку начал линейного программирования. Купманс настаивает на переводе и издании на западе книги Канторовича. Его имя и идеи становятся известны всем.

Л.В.Канторович продолжает писать математические работы, навеянные экономическими идеями, участвует и в конкретных разработках на производстве. При этом (одновременно с Данцигом, но, не зная его работ) он разрабатывает метод, позже названный симплекс-методом. Как только в 50-е годы образуется маленький просвет, и кое-что из запретного становится возможным, он организует группу студентов на экономическом факультете ЛГУ для обучения методам оптимального планирования. А, начиная с 1960 года, Леонид Витальевич занимается только экономической и связанной с нею математической проблемами. Его вклад в этой области был отмечен Ленинской премией в 1965 году (присуждена ему совместно с В.С.Немчиновым и В.В.Новожиловым) и, как уже говорилось, Нобелевской премией в 1975 году.

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

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

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

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

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

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

Действительно, путь необходимо исследовать на экстремум линейную функцию

при линейных ограничениях

Так как Z - линейная функция, то n= С_j (j = 1, 2, ..., n), то все коэффициенты линейной функции не могут быть равны нулю, следовательно, внутри области, образованной системой ограничений, экстремальные точки не существуют. Они могут быть на границе области, но исследовать точки границы невозможно, поскольку частные производные являются константами.

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

Линейная форма , подлежащая максимизации (или минимизации), называется целевой функцией.

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

Задача ЛП, для которой существуют допустимые векторы, называется допустимой задачей. Допустимый вектор , доставляющий наибольшее значение целевой функции по сравнению с любым другим допустимым вектором , т.е. , называется решением задачи, или оптимальным планом. Максимальное значение целевой функции называется значением задачи. Различают три основные формы задач линейного программирования в зависимости от наличия ограничений разного типа.

2.1 Стандартная задача линейного программирования

или, в матричной записи,

где -- матрица коэффициентов. Вектор называется вектором коэффициентов линейной формы, -- вектором ограничений.

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

2.2 Каноническая задача линейного программирования

или, в матричной записи,

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

Пример. Приведем стандартную задачу линейного программирования к каноническому виду:

и обращающее в максимум линейную функцию от этих переменных:

Начнём с того, что приведём условия (1) к стандартной форме, так, чтобы знак неравенства был , а справа стоял нуль. Получим:

А теперь обозначим левые части неравенств (3) соответственно через y₁ и y₂:

Из условий (3) и (4) видно, что новые переменные y₁, y₂ также должны быть неотрицательными.

Какая же теперь перед нами стоит задача? Найти неотрицательные значения переменных x₁,x₂,x₃,y₁,y₂ такие, чтобы они удовлетворяли условиям - равенствам (4) и обращали в максимум линейную функцию этих переменных (то, что в L не входит дополнительные переменные y₁, y₂, неважно: можно считать, что они входят, но с нулевыми коэффициентами). Перед нами - каноническая задача линейного программирования. Переход к ней от первоначальной задачи с ограничениями - неравенствами (2) «куплен» ценой увеличения числа переменных на два (число неравенств).

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

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

Здесь . Ясно, что стандартная задача получается как частный случай общей при ; каноническая -- при .

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

2.4 Двойственная задача линейного программирования

Рассмотрим задачу линейного программирования

или, в матричной записи

Задачей, двойственной к (5) (двойственной задачей), называется задача ЛП от переменных вида

или, в матричной записи,

где .

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

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

Теорема двойственности. Если взаимодвойственные задачи (6) и (8) допустимы, то они обе имеют решение и одинаковое значение.

2.5 Геометрическая интерпретация задачи линейного программирования

Рассмотрим задачу линейного программирования, система ограничений которой задана в виде неравенств.

Найти минимальное значение линейной функции

При ограничениях

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

Рассмотрим на плоскости х₁,х₂ совместную систему линейных неравенств

Это все равно, что в системе (10) - (11) положить n=2. Каждое неравенство этой системы геометрически определяет полуплоскость с граничной прямой Условия неотрицательности определяют полуплоскости соответственно с граничными прямыми Система совместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых являются решением данной системы.

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

Если в системе ограничений (10) - (1) n= 3, то каждое неравенство геометрически представляет полупространство трехмерного пространства, граничная плоскость которого , а условия неотрицательности - полупространства с граничными плоскостями соответственно . Если система ограничений совместна, то эти полупространства, как выпуклые множества, пересекаясь, образуют в трехмерном пространстве общую часть, которая называется многогранником решений. Многогранник решений может быть точкой, отрезком, лучом, многоугольником, многогранником, многогранной неограниченной областью.

Пусть в системе ограничений (10) - (11) n=?; тогда каждое неравенство определяет полупространство n-мерного пространства с граничной гиперплоскостью , а условия неотрицательности - полупространства с граничными гиперплоскостями .

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

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

линейное программирование симплекс экстремум

3.Решение задачи линейного программирования

Рассмотрим основную задачу линейного программирования: найти неотрицательные значения переменных x₁, x₂, …, x_n, удовлетворяющие m условиям - равенствам:

и обращающие в максимум линейную функцию этих переменных:

Для простоты предположим, что все условия (12) линейно независимы (r=m), и будем вести рассуждения в этом предположении.

Назовём ДОПУСТИМЫМ решением задачи линейного программирования всякую совокупность неотрицательных значений x₁, x₂, …, x_n, удовлетворяющую условиям (12).

ОПТИМАЛЬНЫМ назовём то из допустимых решений, которое обращает в максимум функцию (13).

Требуется найти оптимальное решение. Всегда ли эта задача имеет решение? Нет, не всегда.

1. Может оказаться, что уравнения (12) вообще несовместимы (противоречат друг другу).

2. Может оказаться и так, что они совместимы, но не в области неотрицательных решений, т.е. не существует ни одной совокупности чисел x₁0, x₂0, …, x_n0, удовлетворяющей условиям (12).

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

Попробуем разрешить уравнения (12) относительно каких-нибудь m базисных переменных и выразим их через остальные k свободных. Попробуем положить эти свободные переменные равными нулю - авось повезёт, наткнёмся на опорную точку. Вычислим базисные переменные при нулевых значениях свободных. Если все они оказались неотрицательными, значит, нам повезло, мы сразу же получим допустимое (опорное) решение, и его остаётся только оптимизировать. А если нет? Значит, данный выбор свободных и базисных переменных допустимого решения не даёт; точка лежит не на границе, а вне области допустимых решений. Что делать? Надо «пере разрешить» уравнения относительно каких-то других базисных переменных, но не как попало, а так, чтобы это приближало нас к области допустимых решений. Пусть, наконец, несколько раз повторив такую процедуру, мы нашли опорное решение задачи линейного программирования. Но это ещё не всё. Тут надо поставить вопрос: а является ли это решение оптимальным? Выразим функцию L через последние получившиеся свободные переменные и попробуем увеличить их сверх нуля. Если от этого значения L только уменьшается, значит, нам повезло, и мы нашли оптимальное решение, задачи линейного программирования решена. А если нет? Снова «пере разрешаем» систему уравнений относительно других базисных переменных, и снова не как попало, а так чтобы, не выходя за пределы допустимых решений, приблизиться к оптимальному. Для этого в линейном программировании существуют специальные приёмы, гарантирующие, что при каждом новом «пере разрешении» мы будем приближаться к оптимальному решению, а не удаляться от него. После конечного числа таких шагов цель будет достигнута - оптимальное решение найдено. А если его не существует? Алгоритм решения задачи линейного программирования сам покажет вам, что решения нет.

Для простых задач, где число переменных невелико, такой «слепой перебор» может привести к решению, и довольно быстро. Но на практике часто встречаются задачи, в которых число переменных (и наложенных условий) очень велико, порядка сотен и даже тысяч. Для таких задач простой перебор становится практически невозможным: слишком велико число комбинаций свободных и базисных переменных. Пример: только при n=30 и m=10 число возможных комбинаций свободных переменных с базисными равно, т.е. свыше 30 миллионов! А эта задача - далеко не из сложных. Разработанные в теории линейного программирования вычислительные методы («симплекс-метод», «Метод исключения Жордана-Гауса» и другие) позволяют находить оптимальное решение не «слепым» перебором, а «целенаправленным», с постоянным приближением к решению. Добавим, что совместимые ЭВМ, как правило, снабжены подпрограммами для решения задач линейного программирования, так что лицу, желающему их решить, нет даже особой надобности обучаться решению таких задач «вручную» - труд крайне неприятный и изнурительный. Рассмотрим некоторые методы последовательного поиска решения задач линейного программирования.

3.1 Графический способ решения задачи линейного программирования

Чтобы представить себе принципиальную сторону задачи линейного программирования, обратимся к геометрической интерпретации. Пусть число уравнений m на два меньше числа переменных n (n-m=k=2). Такой частный случай даёт возможность геометрической интерпретации задачи линейного программирования на плоскости.

Мы знаем, что n линейно независимых уравнений (3.1.1) всегда можно разрешить относительно каких-то m базисных переменных, выразив их через остальные, свободные, число которых равно n-m=k (в нашем случае k=2). Предположим, что свободные переменные - это x₁ и x₂ (если это не так, то всегда можно заново перенумеровать переменные), а остальные: x₃, x₄, …, x_n - базисные. Тогда вместо m уравнений (3.1.1) мы получим тоже m уравнений, но записанных в другой форме, разрешённых относительно x₃, x₄,

Будем изображать пару значений свободных переменных точкой с координатами x₁, x₂, изображённых на рис.1. Так как переменные x₁, x₂ должны быть неотрицательными, то допустимые значения свободных переменных лежат только выше оси Ox₁ (на которой x₂=0) и правее оси Ox₂ (на которой x₁=0). Это мы отметим штриховкой, обозначающей «допустимую» сторону каждой оси. Теперь построим на плоскости x₁Ox₂ область допустимых решений или же убедимся, что её не существует. Базисные переменные x₃, x₄, …, x_n тоже должны быть неотрицательными и удовлетворять уравнениям (14). Каждое такое уравнение ограничивает область допустимых решений.

Рис. 1

Действительно, положим в первом уравнении (14) x₃=0; получим уравнение прямой линии:



На этой прямой x₃=0; по одну сторону от неё x₃>0, по другую - x₃<0. Отметим штриховкой ту сторону (полуплоскость), где x₃>0 (рис. 2). Пусть эта сторона оказалась правее и выше прямой x₃=0. Значит, вся область допустимых решений лежит в первом координатном угле, правее и выше прямой x₃=0. Аналогично поступим и со всеми остальными условиями (14). Каждое из них изобразится прямой со штриховкой, указывающей «допустимую» полуплоскость, где только и может лежать решение (рис. 3).

Рис. 2

Рис. 3

Таким образом, мы построили n прямых: две оси координат (Ox₁ и Ox₂) и n-2 прямых x₃=0, x₄=0, …, x_n=0. Каждая из них определяет «допустимую» полуплоскость, где может лежать решение. Часть первого координатного угла, принадлежащая одновременно всем этим полуплоскостям, и есть область допустимых решений. На рис. 3 показан случай, когда области допустимых решений существует, т.е. система уравнений (14) имеет неотрицательные решения. Заметим, что этих решений - бесконечное множество, так как любая пара значений свободных переменных, взятая из область допустимых решений, «годится», а из x₁ и x₂ могут быть определены и базисные переменные.

Может оказаться, что область допустимых решений не существует, и значит, уравнения (14) несовместимы в области неотрицательных значений. Такой случай показан на рис. 4, где нет области, лежащей одновременно по «нужную» сторону от всех прямых. Значит, задача линейного программирования не имеет решения.

Рис. 4

Предположим, что область допустимых решений существует, и мы её построили. Как же теперь найти среди них оптимальное?

Для этого дадим геометрическую интерпретацию условию (13) Lmax. Подставив выражения (13) в формулу (14), выразим L через свободные переменные x₁, x₂. после приведения подобных членов получим:



где ₁, ₂ - какие-то коэффициенты, ₀ - свободный член, которого в первоначальном виде у функции L не было; теперь, при переходе к переменным x₁, x₂, он мог и появится. Однако мы его тут же и отбросим: ведь максимум линейной функции L достигается при тех же значениях x₁, x₂, что и максимум однородной линейной функции (без свободного члена):

Посмотрим, как изобразить геометрически условие L'max. Положим сначала L'=0, т.е. и построим на плоскости x₁Ox₂ прямую с таким уравнением; очевидно, она проходит через начало координат (рис. 5)

Рис. 5

Назовём её «опорной прямой». Если мы будем придавать L' какие-то значения C₁, C₂, C₃, …, прямая будет перемещаться параллельно самой себе; при перемещении в одну сторону L' будет возрастать, в другую - убывать. Отметим на рис. 5. стрелками, поставленными у опорной рамой, то направление, в котором L' возрастает. На рис. 5. это оказалось направление «направо - вверх», но могло быть и наоборот: всё зависит от коэффициентов ₁, ₂. теперь изобразим опорную прямую и область допустимых решений на одном чертеже (Рис. 6). Давайте будем мысленно двигать опорную прямую параллельно самой себе в направлении стрелок (возрастания L'). Когда L' достигнет максимума? Очевидно, в точке A (крайней точке области допустимых решений в направлении стрелок). В этой точке свободные переменные принимают оптимальные значения x₁^*,x₂^*, а из них можно по формулам (14) найти и оптимальные значения всех остальных (базисных) переменных x₃^*, x₄^*, …, x_n^*. Заметим, что максимум L' достигается в одной из вершин области допустимых решений, где, по крайней мере, две из базисных переменных (в нашем случае это x₃ и x₅) обращаются в нуль. Могло бы обращаться в нуль и больше базисных переменных, если бы через точку А проходило более двух прямых x_i=0.

А может ли оказаться, что оптимального решения не существует? Да, может, если в области допустимых решений функция L' (а значит и L) не ограничена сверху. Пример такого ненормального случая показан на рис. 7(в разумно поставленных задачах обычно такого недоразумения не возникает).

Рис. 6



Рис. 7

На рис. 6. оптимальное решение существовало и было единственным. А сейчас рассмотрим, когда оптимальное решение существует, но не единственно (их бесконечное множество). Это случай, когда максимум L' достигается не в одной точке А, а на целом отрезке АВ, параллельном опорной прямой (рис. 8). Итак, мы рассмотрели в геометрической интерпретации случай n-m=k=2 и убедились в следующем: оптимальное решение (если оно существует) всегда достигается в одной из переменных x₁, x₂, …, x_n равны нулю. Оказывается, аналогичное правило справедливо и в случае n-m=k>2 (только геометрическая интерпретация теряет в этом случае свою наглядность). Обойдёмся без доказательства, просто сформулируем это правило.

Рис. 8

Оптимальное решение задачи линейного программирования (если оно существует) достигается при такой совокупности значений переменных x₁, x₂, …, x_n, где, по крайней мере, k из них обращаются в нуль, а остальные неотрицательны.

При k=2 такая совокупность значений изображается точкой на плоскости, лежащей в одной из вершин многоугольника допустимых решений. При k=3 многоугольник допустимых решений представляет собой уже не многоугольник, а многогранник, и оптимальное решение достигается в одной из его вершин. При k>3 геометрическая интерпретация теряет наглядность, но всё же геометрическая терминология остаётся удобной. Мы будем продолжать говорить о «многограннике допустимых решений» в k-мерном пространстве, а оптимальное решение (если оно существует) будет достигаться водной из вершин этого многогранника, где, по крайней мере, k переменных равны нулю, а остальные - неотрицательны. Будем для краткости называть такую вершину «опорной точкой», а вытекающее из неё решение «опорным решением».

3.2 Метод исключения Жордана-Гаусса для системы линейных уравнений

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

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

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

Результатом применения метода Жордада-Гаусса является следующее: либо устанавливается, что система несовместна, либо выявляются и отбрасываются все «лишние» уравнения; при этом итоговая система уравнений имеет вид

, ,

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

Полученную системы уравнений называют приведенной системой, соответствующей множеству номеров базисных переменных.

4.Примеры задач линейного программирования

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

4.1 Задача о рациональном питании (задача о пищевом рационе

Постановка задачи. Ферма производит откорм скота с коммерческой целью. Для простоты допустим, что имеется всего четыре вида продуктов: П₁, П₂, П₃, П₄; стоимость единицы каждого продукта равна соответственно С₁, С₂, С₃, С₄. Из этих продуктов требуется составить пищевой рацион, который должен содержать: белков - не менее b_i единиц; углеводов - не менее b₂ единиц; жиров - не менее b₃ единиц. Для продуктов П₁, П₂, П₃, П₄ содержание белков, углеводов и жиров (в единицах на единицу продукта) известно и задано в таблице 1, где a_ij (i=1,2,3,4; j=1,2,3) - какие - то определённые числа; первый индекс указывает номер продукта, второй - номер элемента (белки, углеводы, жиры).

Таблица 1

Таблица значений модели

Продукт	Элементы
	белки	углеводы	жиры
П1 П2 П3 П4	A11 A21 A31 A41	A12 A22 A32 A42	A13 A23 A33 A43

Требуется составить такой пищевой рацион (т.е. назначить количества продуктов П₁, П₂, П₃, П₄, входящих в него), чтобы условия по белкам, углеводам и жирам были выполнены и при этом стоимость рациона была минимальна.

Математическую модель. Обозначим x₁, x₂, x₃, x₄ количества продуктов П₁, П₂, П₃, П₄, входящих в рацион. Показатель эффективности, который требуется минимизировать, - стоимость рациона (обозначим её L): она линейно зависит от элементов решения x₁, x₂, x₃, x₄.

Целевая функция:

Система ограничений:

a₁₁x₁+a₂₁x₂+a₃₁x₃+a₄₁x₄?b₁

a₁₂x₁+a₂₂x₂+a₃₂x₃+a₄₂x₄?b₂

a₁₃x₁+a₂₃x₂+a₃₂x₃+a₄₃x₄?b₃

Эти линейные неравенства представляют собой ограничения, накладываемые на элементы решения x₁, x₂, x₃, x₄.

Таким образом, поставленная задача сводится к следующей: найти такие неотрицательные значения переменных x₁, x₂, x₃, x₄, чтобы они удовлетворяли ограничениям - неравенствам и одновременно обращали в минимум линейную функцию этих переменных:

4.2 Задача о планировании производства

Постановка задачи. Предприятие производит изделия трёх видов: U₁, U₂, U₃. По каждому виду изделия предприятию спущен план, по которому оно обязано выпустить не мене b₁ единиц изделия U₁, не мене b₂ единиц изделия U₂ и не мене b₃ единиц изделия U₃. План может быть перевыполнен, но в определённых границах; условия спроса ограничивают количества произведённых единиц каждого типа: не более соответственно ₁, ₂, ₃ единиц. На изготовление изделий идёт какое-то сырьё; всего имеется четыре вида сырья: s₁, s₂, s₃, s₄, причём запасы ограничены числами ₁, ₂, ₃, ₄ единиц каждого вида сырья. Теперь надо узнать какое количество сырья каждого вида идёт на изготовление каждого вида изделий. Обозначим a_ij количество единиц сырья вида s_i (I= 1, 2, 3, 4), потребное на изготовление одной единицы изделия U_j (j= 1, 2, 3). Первый индекс у числа a_ij - вид изделия, второй - вид сырья. Значения a_ij сведены в таблицу2 (матрицу). При реализации одно изделие U₁ приносит предприятию прибыль c₁, U₂ - прибыль c₂, U₃ - прибыль c₃. Требуется так спланировать производство (сколько каких изделий производить), чтобы план был выполнен или перевыполнен (но при отсутствии «затоваривания»), а суммарная прибыль обращалась в максимум.

Таблица 2 Таблица значений модели

Сырьё	Изделия
	U1	U2	U3
S1 S2 S3 S4	a11 a12 a13 a14	a21 a22 a23 a24	a31 a32 a33 a34

Математическая модель. Элементами решения будут x₁, x₂, x₃ - количества единиц изделий U₁, U₂, U₃, которые мы произведём. Обязательность выполнения планового задания запишется в виде трёх ограничений - неравенств: x₁b₁, x₂b₂, x₃b₃.

Отсутствие изделий продукции (затоваривания) даёт нам ещё три ограничения - неравенства: x₁₁, x₂₂, x₃₃.

Целевая функция: L=c₁x₁+c₂x₂+c₃x₃> max.

Система ограничений:

a₁₁x₁+a₂₁x₂+a₃₁x₃₁.

a₁₂x₁+a₂₂x₂+a₃₂x₃₂.

a₁₃x₁+a₂₃x₂+a₃₃x₃₃.

a₁₄x₁+a₂₄x₂+a₃₄x₃₄.

4.3 Задача о загрузки оборудования

Постановка задачи. Ткацкая фабрика располагает двумя видами станков, из них N1 станков типа 1 и N2 станков типа 2. Станки могут производить три вида тканей: T1, T2, T3, но с разной производительностью. Данные a_ij производительности станков в таблице 3 (первый индекс - тип станка, второй - вид ткани).

Каждый метр ткани вида T1 приносит фабрике доход c₁, вида Т2 - доход с₂, Т3 - доход с₃.

Таблица 3 Таблица значений модели

Тип станка	Вид ткани
	T1	T2	T3
1 2	а11 а21	а12 а22	а13 а23

Фабрике предписан план согласно которому она должна производить в месяц не менее b₁ метров ткани Т1, b₂ метров ткани Т2, b₃ метров ткани Т3; количество метров каждого вида ткани не должно превышать соответственно ₁, ₂, ₃ метров. Кроме того, все без исключения станки должны быть загружены. Требуется так распределить загрузку станков производством тканей Т1, Т2, Т3, чтобы суммарный месячный доход был максимален.

Математическая модель. Введём букву x с двумя индексами (первый - тип станка, второй - вид ткани). Всего будет шесть элементов решения: x₁₁ x₁₂ x₁₃ x₂₁ x₂₂ x₂₃ .

Здесь x₁₁ - количество станков типа 1, занятых изготовлением ткани Т1, x₁₂ - количество станков типа 1, занятых изготовлением ткани Т2 и т.д.

Запишем суммарный доход от производства всех видов тканей. Суммарное количество метров ткани Т1, произведённое всеми станками, будет равно a₁₁x₁₁+a₂₁x₂₁ и принесёт доход c₁(a₁₁x₁₁+a₂₁x₂₁).

Целевая функция:

L=c₁ (a₁₁x₁₁+a₂₁x₂₁)+c₂ (a₁₂x₁₂+a₂₂x₂₂)+c₃ (a₁₃x₁₃+a₂₃x₂₃) > max.

Система ограничений:

Обеспечим выполнения плана ограничениями по минимальным параметрам:

a₁₁x₁₁+a₂₁x₂₁b₁,

a₁₂x₁₂+a₂₂x₂₂b₂,

a₁₃x₁₃+a₂₃x₂₃b₃,

После этого ограничим выполнение плана по максимальным параметрам:

a₁₁x₁₁+a₂₁x₂₁₁,

a₁₂x₁₂+a₂₂x₂₂₂,

a₁₃x₁₃+a₂₃x₂₃₃,

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

Суммарное количество станков типа 1, занятых изготовлением всех тканей, должно быть равно N1; типа 2 - N2.

x₁₁+x₁₂+x₁₃=N1,

x₂₁+x₂₂+x₂₃=N2.

4.4 Задача о снабжении сырьём

Постановка задачи. Имеется три промышленных предприятия: П₁, П₂, П₃, требующих снабжения определённым видом сырья. Потребности в сырье каждого предприятия равны соответственно a₁, a₂, a₃ единиц. Имеются пять сырьевых баз, расположенных от предприятий на каких - то расстояниях и связанных с ними путями сообщения с разными тарифами. Единица сырья, получаемая предприятием П_i c базы Б_{j ,} обходится предприятию в с_ij рублей (первый индекс - номер предприятия, второй - номер базы) записаны в таблице 4.Возможности снабжения сырьём с каждой базы ограничены её производственной мощностью: базы Б₁, Б₂, Б₃, Б₄, Б₅ могут дать не более b₁, b₂, b₃, b₄, b₅ единиц сырья. Требуется составить такой план снабжения предприятий сырьём (с какой базы, куда и какое количество сырья везти), чтобы потребности предприятий были обеспечены при минимальных расходах на сырьё.

Таблица 4 Таблица значений модели

Предприятия	Базы
	Б1	Б2	Б3	Б4	Б5
П1 П2 П3	С11 С21 С31	С12 С22 С32	С13 С23 С33	С14 С24 С34	С15 С25 С35

Математическая модель. Обозначим x_ij количества сырья с j - ой базы.

Всего план будет состоять из 15 элементов решения: x₁₁ x₁₂ x₁₃ x₁₄ x₁₅ x₂₁ x₂₂ x₂₃ x₂₄ x₂₅ x₃₁ x₃₂ x₃₃ x₃₄ x_35.

Целевая функция:

Система ограничений:

x₁₁+x₁₂+x₁₃+x₁₄+x₁₅=a₁,

x₂₁+x₂₂+x₂₃+x₂₄+x₂₅=a₂,

x₃₁+x₃₂+x₃₃+x₃₄+x₃₅=a₃,

x₁₁+x₂₁+x₃₁b₁,

x₁₂+x₂₂+x₃₂b₂,

x₁₃+x₂₃+x₃₃b₃,

x₁₄+x₂₄+x₃₄b₄,

x₁₅+x₂₅+x₃₅b₅,

ЗАКЛЮЧЕНИЕ

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

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

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

1. Абрамов Л.М., Капустин В.Ф. Математическое программирование. Л., Изд-Ленингр. ун-та, 2000.

2. Ашманов С.А. Линейное программирование. - М.: Наука, 1981.

3. Банди Б. Основы линейного программирования: Пер. с англ. - М.: Радио и связь, 1989

4. Габасов Р., Кириллова Ф.М. Методы линейного программирования. Ч.1. Общие задачи, Минск, Изд-во БГУ им. В.И. Ленина, 1977.

5. Гасс С.Линейное программирование. - М.: Физматгиз, 1961.

6. Ляшенко И.Н, Карагодова Е.А, Черникова Н.В., Шор Н.З. Линейное и нелинейное программирование. Издательское объединение “Вища школа”, 1975.

7. Солодовников А.С. Введение в линейную алгебру и линейное программирование. М., Изд. “Просвещение”, 1966.

8. Схрейвер А. Теория линейного и целочисленного программирования: В 2-х т. Т.1: Пер с англ. - М.: Мир, 1991.

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