Реферат: Линейное программирование: постановка задач и графическое решение

КУРСОВОЙПРОЕКТ ПО ДИСЦИПЛИНЕ

«ЭКОНОМИКО-МАТЕМАТИЧЕСКОЕМОДЕЛИРОВАНИЕ»


Тема.Линейное программирование: постановка задач и графическое решение.


Научныйруководитель:

Чернов

АлександрСтепанович

Исполнитель:

Кудрявцева

ЕленаАлександровна


Г.Мурманск

1998год

 

ПЛАН.

Введение.

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

1.1.  Формулировказадачи.

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

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

2.1.  Областьприменения.

2.2.  Примерызадач, решаемых графическим методом.

2.3.  Обобщениеграфического метода решения задач линейного программирования.

Литература.


Введение.

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

Действительно,путь необходимо исследовать на экстремум линейную функцию Z = С1х1+С2х2+…+СNxN

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

a11x1 + a22x2 +… + a1NХN = b1

          a21x1+ a22x2 +… + a2NХN = b2

         .… .

aМ1x1 + aМ2x2 +… + aМNХN = bМ

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

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


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

1.1. Формулировказадачи.

Данылинейная функция

(1.1)     Z = С1х1+С2х2+…+СNxN

и система линейных ограничений

a11x1 + a22x2 +… + a1NХN = b1

           a21x1 + a22x2 +… + a2NХN = b2

          … .

(1.2)         ai1x1+ ai2x2 +… + aiNХN = bi

          … .

aM1x1 + aM2x2 +… + aMNХN = bM

(1.3)         xj  0 (j = 1, 2,… ,n)

где аij, Ьj и Сj — заданные постоянные величины.

Найтитакие неотрицательные значения х1, х2, ..., хn,которые удовлетворяют системе ограничений (1.2) идоставляют линейной функции (1.1)минимальноезначение.

Общаязадача имеет несколько форм записи.

Векторнаяформа записи. Минимизировать линейную функцию Z = СХпри ограничениях

(1.4)              А1х1 + А2x2 +… + АNxN = Ао, X 0

где С= (с1, с2, ..., сN); Х =(х1, х2, ..., хN); СХ- скалярное произведение; векторы

A1 =     , A2 =         ,..., AN=    , A0=

состоятсоответственно из коэффициентов при неизвестных и свободных членах.

Матричнаяформа записи. Минимизировать линейную функцию, Z = СХ при ограничениях АХ = А0, Х  0, где С = (с1, с2, ..., сN) — матрица-cтрока; А = (аij) — матрица системы;

 

Х =        — матрица-столбец, А0=      матрица-столбец

 

 

Записьс помощью знаков суммирования. Минимизировать линейнуюфункцию Z =   Сjхj приограничениях

 

0пределение1. Планом или допустимым решением задачи линейногопрограммирования называется Х = (х1, х2, ..., хN),удовлетворяющий условиям (1.2) и (1.3).               

0пределение2. План Х = (х1, х2, ..., хN)называется опорным, если векторы А (i = 1,2, ..., N), входящие в разложение (1.4) с положительнымикоэффициентами  х, являются  линейно независимыми.

Таккак векторы А являются N-мерными,то из определения опорного плана следует, что число его положительных компонентне может превышать М.

0пределение3. Опорный план называется невырожденным,  еслион содержит М положительных  компонент, в противном случае опорный планназывается вырожденным.

0пределение4. Оптимальным планом или оптимальным решением задачи линейногопрограммирования называется план, доставляющий наименьшее (наибольшее) значениелинейной функции.

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

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

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

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

(1.5)      Z = С1х1+С2х2+… +СNxN

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

a11x1 + a22x2 +… + a1NХN   b1

           a21x1 + a22x2 +… + a2NХN   b2

(1.6)     … .

           aM1x1 + aM2x2 +… + aMNХN   bM

(1.7)      xj   0 (j = 1, 2,… ,n)

Совокупностьчисел х1, х2, ..., хN,удовлетворяющих ограничениям (1.6) и(1.7), называется решением. Если система неравенств (1.6) при условии (1.7)имеет хотя бы одно решение, она называется совместной, в противном случае — несовместной.

Рассмотрим на плоскости х1Ох2 совместнуюсистему линейных неравенств

a11x1 + a22x2   b1

           a21x1 + a22x2   b2

          … .

           aM1x1 + aM2x2   bM

x1  0, x2  0

Этовсе равно, что в системе (1.6) — (1.7) положить N=2.Каждое неравенство  этой  системы геометрически определяетполуплоскость с граничной прямой

/>ai1x1 + ai2x2= bi ,(i = 1, 2, ..., m).Условия неотрицательности определяют  полуплоскости соответственно  сграничными прямыми х = 0, х = 0. Система совместна, поэтому полуплоскости,как выпуклые множества, пересекаясь, образуют общую часть, которая являетсявыпуклым множеством и представляет собой совокупность точек, координаты каждойиз которых  являются решением данной системы (рис. 1.1).

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

Если всистеме ограничений (1.6) — (1.7) n = 3,то каждое нера-венство геометрически представляет полупространствотрехмерного пространства, граничная плоскость которого ai1x1+ ai2x2 + ai3x3 = bi  ,(i = 1,2, ..., n), а условия неотрицательности – полупрост-ранства с граничными плоскостями соответственно хj = 0 (j = 1,2, 3). Если система ограничений совместна, то эти полупространства, каквыпуклые множества, пересекаясь, образуют в трехмерном пространстве общуючасть, которая  называется многогранником решений. Многогранник решенийможет быть точкой, отрезком, лучом, многоугольником, многогранником,многогранной неограниченной областью. Пусть в системе ограничений (1.6) — (1.7)n 3; тогда каждое неравенство определяет полупространствоn-мерного пространства сграничной гиперплоскостью ai1x1 + ai2x2 + aiNxN= bi (i = 1, 2, ..., m), аусловия неотрицательности – полупространства сграничными гиперплоскостями хj 0 (j = 1, 2, ..., n).

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

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

2.  Графический метод решения

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

2.1.  Область применения.

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

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

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

(2.1)         Z = С1х1+С2х2

при

a11x1 + a22x2   b1

(2.2)         a21x1+ a22x2   b2

          … .

           aM1x1 + aM2x2   bM

(2.3)         х1   0, х2   0

Допустим, что система (2.2) приусловии (2.3)совместна и ее многоугольник решений ограничен. Каждое из неравенств (2.2) и (2.3), какотмечалось выше, определяет полуплоскость с граничными прямыми: ai1x1 + ai2x2+ ai3x3  = bi,(i = 1,2, ..., n), х1=0, х2=0. Линейная функция (2.1) при фиксированных значениях Zявляется уравнением прямой линии: С1х1 + С2х2 = const.Построим многоугольник решений системы ограничений (2.2) и график  линейной функции (2.1) при Z = 0(рис. 2.1).Тогда поставленной задаче линейного прграммирования  можно  дать  следующуюинтерпретацию.  Найти точку многоугольника решений, вкоторой прямая С1х1 + С2х2 = constопорная и функция Z при этом достигаетминимума.          

/> ЗначенияZ = С1х1 + С2х2 возрастают в направлении вектора N =(С1, С2), поэтому прямую Z = 0 передвигаемпараллельно самой себе в направлении вектора Х. Из рис. 2.1следует, что прямая дважды становится опорной по отношению к многоугольникурешений (в точках А и С), причем минимальное значение принимает в точке А.Координаты точки А (х1, х2) находим, решая системууравнений прямых АВ и АЕ.                                

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

/>Случай1. Прямая С1х1 + С2х2 = const,передвигаясь в направлении вектора N или противоположно ему,  постоянно пересекает  многоугольник решений и ни в какойточке  не является  опорной к нему. В этом случае линейнаяфункция не ограничена на многоугольнике решений как сверху, так и снизу (рис.2.2).             

Случай2. Прямая, пере-двигаясь, все же становится опорнойотносительно многоу-гольника решений (рис. 2.2, а – 2.2, в). Тогда  взави-симости от вида  области ли-нейная  функция может  быть ограниченнойсверху и неограниченной снизу (рис.  2.2, а),  ограниченной снизу инеограниченной сверху (рис. 2.2, б), либо ограниченной как снизу, так и сверху(рис. 2.2, в).

/>/>

2.1. Примеры задач,решаемых графическим методом.     

Решим  графическим методом задачи использования сырья и составления рациона.

Задачаиспользования сырья.Для изготовления двух видовпродукции Р1 и Р2 используют три вида сырья: S1, S2, S3. Запасы сырья, количествоединиц сырья, затрачиваемых на изготовление единицы продукци, а так же величинаприбыли, получаемая от реализации единицы продукции, приведены в таблице 2.1.

Таблица 2.1.

Вид сырья Запас сырья Количество единиц сырья, идущих на изготовление единицы продукции

Р1

Р2

S1

20 2 5

S2

40 8 5

S3

30 5 6 Прибыль от единицы продукции, руб. 50 40

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

Решение.

Обозначимчерез х1 количество единиц продукции Р1, а через х2– количество единиц продукции Р2. Тогда, учитывая количество единицсырья, расходуемое на изготовление продукции, а так же запасы сырья, получимсистему ограничений:

2х1+ 5х2   20

8х1+ 5х2   40

5х1+ 6х2   30

которая показывает, чтоколичество сырья, расходуемое на изготовление продукции, не может превыситимеющихся запасов. Если продукция Р1 не выпускается, то х1=0; в противном случае x10. То же самое получаем и для продукции Р2. Таким образом, нанеизвестные х1 и х2 должно быть наложено ограничениенеотрицательности: х1  0, х2  0.

Конечную цель решаемой задачи – получение максимальной прибылиприреализации продукции – выразим как функцию двух переменных х1 и х2.Реализация х1 единиц продукции Р1 и х2 единицпродукции Р2 дает соответственно 50х1 и 40х2руб. прибыли, суммарная прибыль Z = 50х1 + 40х2 (руб.)

Условиямине оговорена неделимость единица продукции, поэтому х1и х2 (план выпуска продукции) могут быть и дробными числами.

Требуется найти такие х1 и х2, при которых функция Zдостинает максимум, т.е. найти максимальное значение линейной функции Z = 50х1 + 40х2 приограничениях

2х1+ 5х2   20

8х1+ 5х2   40

5х1+ 6х2   30

х1  0, х2  0.

Построиммногоугольник решений (рис. 2.3).    

Дляэтого в системе координат х1Ох2 на плоскости  наплоскости изобразим граничные прямые

2х1+ 5х2 = 20 (L1)

8х1+ 5х2 = 40 (L2)

5х1+ 6х2 = 30 (L3)

х1 = 0, х2 = 0.

Взяв какую-нибудь точку, например, начало координат,установим, какую полуплоскость определяет соответствующее неравенство (эти полуплоскостина рис. 2.3 показаны стрелками). Многоугольником решений  данной  задачи является ограниченный пятиугольник ОАВСD.

Дляпостроения прямой 50х1 + 40х2 = 0строим радиус-вектор N =(50;40) = 10(5;4) и через точку Oпроводим прямую, перпендикулярную ему. Построенную прямую Z = 0 перемещаем параллельно  самой себе в направлениивектора N. Из риc. 2.3следует, что опорной  по отношению к многоугольнику решений эта прямаястановится в  точке С, где функция Zпринимает максимальное значение. Точка С лежит на пересечении прямых L1 и L2. Дляопределения ее координат решим систему уравнений                         

/>8x1 + 5х2 = 40

5х1+ 6х2 = 30

 

Оптимальныйплан задачи: х1 = 90/23 = 3,9; х2 = 40/23 =  1,7.Подставляя значения х1 и х2 в линейную функцию, получаем Zmax = 50 3,9 + 40 1,7 = 260,3

Такимобразом, для того чтобы получить максимальную прибыль в размере 260,3 руб.,необходимо запланировать производство 3,9 ед. продукции Р1 и 1,7 ед.продукции Р2.

Задачасоставления рациона. При откорме каждое животное ежедневнодолжно получать не менее 9 ед. питательного вещества S1,не менее 8 ед. вещества S2 и не менее 12 ед. вещества S3. Длясоставления рациона используют два вида корма. Содержание количества елиницпитательных веществ в 1 кг каждого вида корма и стоимость 1 кг корма приведеныв таблице 2.2.

 

 

Таблица 2.2.

Питательные вещества

Количество единиц питательных веществ

в 1 кг корма.

Корм 1 Корм 2

S1

3 1

S2

1 2

S3

1 6 Стоимость 1 кг корма, коп. 4 6

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

Решение.

Длясоставления математической модели обозначим через х1 и х2соответственно количество килограммов корма 1 и 2 в дневном рационе. Принимаяво внимание значения, приведенные в таблице 2.2, и условие, что дневной рационудовлетворяет требуемой питательности только в случае, если количество единицпитательных веществ не меньше предусмотренного, получаем систему ограничений

3х1+  х2   9

 х1+ 2х2   8

 х1+ 6х2   12

 х1  0, х2  0.

Есликорм 1 не используется в рационе, то х1=0; впротивном случае x1 0. Аналогично имеем х2 0. То есть должно выполняться условие неотрицательности переменных: х1 0, х2  0.

Цельданной задачи – добиться минимальных затрат на дневной рацион, поэтому общуюстоимость рациона можно выразить в виде линейной функции Z = 4х1 + 6х2 (коп.)

Требуется найти такие х1 и х2, при которых функцияZ принимает минимальное. Таким образом, необходимо найти минимальноезначение линейной функции Z = 4х1 + 6х2 при ограничениях

3х1+  х2   9

 х1+ 2х2   8

 х1+ 6х2   12

 х1  0, х2  0.

Построиммногоугольник решений (рис. 2.4). Для этого в системе координат х1Ох2на плоскости изобразим граничные прямые

3х1+  х2 = 9  (L1)

 х1+ 2х2 = 8  (L2)

 х1+ 6х2 = 12 (L3)

 х1 = 0, х2 = 0.

Взяв какую-нибудь точку,например, начало координат, установим, какую полуплоскость определяетсоответствующее неравенство (эти полуплоскости на рис. 2.4 показаны стрелками). В результате получим неограниченную многоугольную область сугловыми точками А, В, С, D.

/>

Дляпостроения прямой 4х1 + 6х2 = 0строим радиус-вектор N =(4;6) и через точку O проводим прямую,перпендикулярную ему. Построенную прямую Z = 0перемещаем параллельно  самой себе в направлении вектора N. Из риc. 2.4 следует, она впервые коснется многогранника решений и станет опорной по отношению к нему в угловой точе В. Если прямую перемещатьдальше в направлении вектора N, то значения линейнойфункции на многограннике решений возрастут, значит, в точке В линейнаяфункция Z принимает минимальное значение.

ТочкаВ лежит на пересечении прямых L1 и L2. Для определения ее координат решим системууравнений                         

3x1 +  х2 = 9

 х1+ 2х2 = 8

Имеем:х1 = 2; х2 = 3. Подставляя значения х1 и х2в линейную функцию, получаем Zmin = 4 2+ 6 3 = 26.

Такимобразом, для того, чтобы обеспечить минимум затрат (26 коп. в день), необходимодневной рацион составить из 2 кг корма 1 и 3 кг корма 2.

2.2.  Обобщение графического метода решения задач линейногопрограммирования.

 

Вообще,с помощью графического метода может быть ре-шеназадача линейного программирования,  система ограниче-ний которой содержит n неизвестных и m линейно независи-мыхуравнений, если N и M связанысоотношением N – M = 2.

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

Найтиминимальное значение линейной функции Z = С1х1+С2х2+… +СNxN при ограничениях

a11x1 + a22x2 +… + a1NХN = b1

(2.3)     a21x1+ a22x2 +… + a2NХN = b2

         .… .

aМ1x1 + aМ2x2+… + aМNХN = bМ

xj  0 (j = 1, 2, ..., N)

где все уравнения линейнонезависимы и выполняется cоотношениеN — M = 2.                                        

Используяметод Жордана-Гаусса, производим M исключений,в результате которых базисными неизвестными оказались, например, M первых неизвестных х1, х2, ..., хM, асвободными — два последних: хМ+1, и хN, т.е. система ограничений приняла вид

x1 + a1, М+1xМ+1+ a1NХN = b1

(2.4)     x2+ a2, М+1xМ+1 + a2NХN = b2

         .… .

xМ + aМ, М+1x2+ aМNХN = bМ

xj  0 (j = 1, 2, ..., N)

Спомощью уравнений преобразованной системы выражаем линейную функцию толькочерез свободные неизвестные и, учитывая, что все базисные неизвестные — неотрицательные: хj 0 (j = 1, 2, ..., M),отбрасываем их, переходя к системе ограничений, выраженных в виде неравенств.Таким образом, окончательно получаем следующую задачу.          

Найтиминимальное значение линейной функции Z = СМ+1хМ+1+СNxN при ограничениях

a1, М+1xМ+1 + a1NХN   b1

          a2, М+1xМ+1+ a2NХN   b2

         .… .

aМ, М+1xМ+1 + aМNХN   bМ

xМ+1  0, хN  0

Преобразованнаязадача содержит два неизвестных; решая ее графическим методом, находимоптимальные значения xМ+1 и хN, азатем, подставляя их в (2.4), находим оптимальные значения х1, х2, ..., хM.

Пример.

Графическимметодом найти оптимальный план задачи ли-нейного программирования, при которомлинейная функция Z = 2х1 — х2 + х3 — 3х4 + 4х5 достигает максимального значения приограничениях

х1 — х2 + 3х3 — 18х4 + 2х5 = -4

2х1 — х2 + 4х3 — 21х4 + 4х5 = 2

3х1 — 2х2 + 8х3 — 43х4 + 11х5 = 38

xj  0 (j = 1, 2, ..., 5)

Решение.

Используяметод Жордана-Гаусса, произведем три полных исключения неизвестных х1,х2, х3. В результате приходим к системе

х1 + х4 — 3х5 = 6

х2 + 7х4 + 10х5 = 70

х3 — 4х4 + 5х5 = 20

Откудаx1 = 6 – х4 + 3x5, х2 = 70 – 7х4-10х5,х3 = 20 + 4х4 -5х5.

Подставляяэти значения в функцию и отбрасывая в системе базисные переменные, получаемзадачу, выраженную только через свободные переменные х4 и х5:найти максимальное значение линейной функции Z = 6х4+ 15х5 – 38 при ограничениях

х4 — х5   6

7х4+ 10х5   70

— 4х4+ 5х5   20

х4 0,  х5   0.

/>

Построиммногогранник решений и линейную функцию в системе координат х4Ох5(рис. 2.5). Из рис. 2.5 заключаем, что линейная функция принимаетмаксимальное значение в угловой точке В, которая лежит на пересечении прямых 2и 3. В результате решения системы

  7х4+ 10х5  = 70

-    4х4 +  5х5  = 20

-    

находим: х4 = 2, х5= 28/5. Максимальное значение функции Zmax = -38+ 12 + 84 = 58.

Дляотыскания  оптимального плана исходной задачи подставляем найденные значения х4и х5. Окончательно получаем: х1 = 104/5, х2 =0, х3 = 0, х4 = 2, х5 = 28/5.

ЛИТЕРАТУРА

1.   Математическиеметоды анализа экономики /под ред. А.Я.Боярского. М., Изд-во Моск. Ун-та, 1983

2.   А.И.Ларионов,Т.И.Юрченко “Экономико-математические методы в планировании: Учебник – М.:Высш.школа, 1984

3.   Ашманов С.А.“Линейное программирование”,- М.: 1961

еще рефераты
Еще работы по математике