ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕУЧРЕЖДЕНИЕ
«ПРИДНЕСТРОВСКИЙГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. Т.Г. ШЕВЧЕНКО»
РЫБНИЦКИЙФИЛИАЛ
КАФЕДРА«ФИЗИКИ, МАТЕМАТИКИ И ИНФОРМАТИКИ»
Курсоваяработа
по дисциплине
«Исследованиеопераций»
на тему:
“Решения задач линейногопрограммирования геометрическим методом”
Выполнила:
студентка III курса
специальности“Информатика с доп. спец. английский язык”
Нистор А.Г.
Проверила:
преподавательПанченко Т.А.
г. Рыбница
2008 г.
ОГЛАВЛЕНИЕ
Введение. 3
I.ТЕОРЕТИЧЕСКИЙ РАЗДЕЛ… 4
1.1 Линейноепрограммирование. 4
1.2 Формулировка задачи. 5
1.3 Основныепонятия линейной алгебры и выпуклого анализа, применяемые в теорииматематического программирования. 7
1.4 Математические основы решения задачи линейного программированияграфическим способом. 9
1.4.1 Математический аппарат. 9
1.4.2 Геометрическая интерпретация задачи линейного программирования. 11
1.4.3 Этапы решения графического метода задач линейного программирования 13
II.ПРАКТИЧЕСКИЙ РАЗДЕЛ… 18
Задача № 1. 18
Задача № 2. 21
Задача № 3. 24
Задача № 4. 27
Задача № 5. 30
Заключение. 33
Списоклитературы… 34
ВВЕДЕНИЕ
Линейное программирование — это наукао методах исследования и
отыскания наибольших и наименьшихзначений линейной функции, на неизвестные которой наложены линейныеограничения. Таким образом, задачи линейного программирования относятся кзадачам на условный экстремум функции. Казалось бы, что для исследованиялинейной функции многих переменных на условный экстремум достаточно применитьхорошо разработанные методы математического анализа, однако невозможность ихиспользования можно довольно просто проиллюстрировать.
Для решения задач линейногопрограммирования потребовалось создание специальных методов. В данной курсовойработе будет рассмотрен геометрический метод решения задач линейногопрограммирования. Геометрический метод применяется в основном при решении задачдвумерного пространства и только некоторых задач трехмерного пространства, таккак довольно трудно построить многогранник решений, который образуется врезультате пересечения полупространств. Задачу пространства размерности больше трехизобразить графически вообще невозможно.
Таким образом,целью данной курсовой работы является: освоить навыки использования геометрическогометода для решения задач линейного программирования. Для этого были поставленыследующие задачи:
1) Изучить теоретические сведения, необходимые длярешения задач линейного программирования геометрическим методом.
2) Разобрать алгоритм решения ЗЛП геометрическим методом.
3) Решить поставленные задачи, используя рассмотренныйметод решения задач линейного программирования.
I. ТЕОРЕТИЧЕСКИЙРАЗДЕЛ 1.1 Линейное программирование
Линейное программирование —математическая дисциплина, посвященная теории и методам решения задач обэкстремумах линейных функций на множествах n-мерного векторного пространства,задаваемых системами линейных уравнений и неравенств.
Линейное программирование являетсячастным случаем математического программирования. Одновременно оно — основанескольких методов решения задач целочисленного и нелинейного программирования.
Многие свойства задач линейногопрограммирования можно интерпретировать также как свойства многогранников итаким образом геометрически формулировать и доказывать их.
Термин «программирование» нужнопонимать в смысле «планирования». Он был предложен в середине 1940-х годовДжорджем Данцигом, одним из основателей линейного программирования, еще дотого, как компьютеры были использованы для решения линейных задач оптимизации.
Математическая формулировка задачи линейногопрограммирования
/>
Нужно максимизировать
/>
при условиях при i = 0, 1, 2,..., m .
Иногда на xi также накладывается некоторый наборограничений в виде равенств, но от них можно избавиться, последовательновыражая одну переменную через другие и подставляя ее во всех остальных равенствахи неравенствах (а также в функции f).
Такую задачуназывают «основной» или «стандартной» в линейномпрограммировании. 1.2 Формулировка задачи
Даны линейнаяфункция Z=С1х1+С2х2+...+СNxN(1.1)
и системалинейных ограничений
a11x1 + a22x2 +… + a1NХN = b1
a21x1+ a22x2 +… + a2NХN = b2
….… .
ai1x1+ ai2x2 +… + aiNХN = bi(1.2)… .
aM1x1+ aM2x2 +… + aMNХN = bM
xj 0(j = 1, 2,… ,n) (1.3)
где аij, bj и Сj — заданныепостоянные величины.
Найти такиенеотрицательные значения х1, х2, ..., хn, которыеудовлетворяют системе ограничений (1.2) и доставляют линейной функции (1.1) минимальноезначение.
Общая задачаимеет несколько форм записи.
Векторная формазаписи. Минимизировать линейную функцию Z = СХ при ограничениях А1х1+ А2x2 +… + АNxN = Ао,X0 (1.4)
где С = (с1,с2, ..., сN); Х = (х1, х2,..., хN); СХ — скалярное произведение; векторы A1 = A2 = ,..., AN состоятсоответственно из коэффициентов при неизвестных и свободных членах.
Матричная формазаписи. Минимизировать линейную функцию, Z = СХ приограничениях АХ = А0Х0, где С = (с1, с2,..., сN) — матрица-cтрока; А = (аij) — матрицасистемы; Х =(xij)- матрица-столбец, А0= (аi) матрица-столбец
Запись спомощью знаков суммирования. Минимизировать линейную функцию 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.3 Основные понятия линейной алгебры и выпуклого анализа,применяемые в теории математического программирования
Кратко напомним некоторые фундаментальныеопределения и теоремы линейной алгебры и выпуклого анализа, которые широкоприменяются при решении проблем как линейного, так и нелинейногопрограммирования.
Фундаментальным понятием линейнойалгебры является линейное (вещественное) пространство. Под ним подразумеваетсямножество некоторых элементов (именуемых векторами или точками), для которыхзаданы операции сложения и умножения на вещественное число (скаляр), причемэлементы, являющиеся результатом выполнения операций, также в соответствии с определениемдолжны принадлежать исходному пространству.
Частными случаями линейныхпространств являются вещественная прямая, плоскость, геометрическое трехмерноепространство.
Вектор λ1a1 + λ2a2 + …+ λmam называется линейной комбинацией векторов а1а2,..., аmс коэффициентами λ1, λ2, λm,
Система векторов линейногопространства а1 а2,..., аm называется линейно зависимой, если существуют такиечисла λ1, λ2, λmне равные одновременно нулю, что их линейная комбинация λ1a1 + λ2a2 + …+ λmam равняется нулевому вектору (вектору, все компоненты которогоравны нулю). В противном случае систему а1, а2,..., аm называют линейно независимой, т. е.линейная комбинация данных векторов может быть равна нулевому вектору толькопри нулевых коэффициентах λ1, λ2, …, λm
Максимально возможное количествовекторов, которые могут образовывать линейно независимую систему в данномлинейном пространстве, называют размерностью пространства, а любую системулинейно независимых векторов в количестве, равном размерности, — базисомпространства.
Линейное пространство обычнообозначают как Rn, гдеn — его размерность.
Любое подмножество данного линейногопространства, которое само обладает свойствами линейного пространства,называется линейным подпространством. Множество Н, получаемое сдвигом некотороголинейного подпространства L € Rn на вектор a € Rn: H=L+a, называетсяаффинным множеством (пространством). Если фундаментальным свойством любоголинейного пространства или подпространства является принадлежность ему нулевоговектора, то для аффинного множества это не всегда так. На плоскости примеромподпространства является прямая, проходящая через начало координат, а аффинногомножества — любая прямая на плоскости. Характеристическим свойством аффинногомножества является принадлежность ему любой прямой, соединяющей две любые еготочки. Размерность аффинного множества совпадает с размерностью того линейногоподпространства, сдвигом которого оно получено.
Если рассматривается некотороелинейное пространство Rn, то принадлежащие ему аффинные множества размерности 1 называютсяпрямыми, а размерности (n-1)—гиперплоскостями.Так, обычная плоскость является гиперплоскостью для трехмерного геометрическогопространства R3, а прямая — гиперплоскостью для плоскости R2.Всякая гиперплоскость делит линейное пространство на два полупространства.
Множество V векторов (точек)линейного пространства Rnназывается выпуклым, если оно содержит отрезок прямой, соединяющей две еголюбые точки, или, другими словами, из того, что a €V и b€V, следует, что х = (1- λ) х а+ λх b € V, где 0 ≤ λ ≤ 1.
Линейная комбинация /> векторов а1, а2…аm называется выпуклой, если λi ≥0, i €1:m и />
Множество, содержащее все возможныевыпуклые комбинации точек некоторого множества М, называют выпуклой оболочкойданного множества. Можно показать, что выпуклая оболочка множества М являетсянаименьшим выпуклым множеством, содержащим М.
Выпуклая оболочка конечного множестваточек называется выпуклым многогранником, а непустое пересечение конечногочисла замкнутых полупространств — многогранным выпуклым множеством. В отличиеот выпуклого многогранника последнее может быть неограниченным.
Точка v выпуклого множества V называется его угловой (крайней)точкой, если она не является внутренней точкой ни для какого отрезка, концыкоторого принадлежат множеству V. Угловые точки выпуклого многогранникаявляются его вершинами, а сам он — выпуклой оболочкой своих вершин.
Множество К называется конусом свершиной в точке x0, если x0 € К, и из того, что некоторая точка х принадлежит К ( х € К), следует, что в К содержится и луч, начинающийся в х0и проходящийчерез х, т. е.
/>
или
/>
Выпуклая оболочка конечного множествалучей, исходящих из одной точки, называется многогранным выпуклым конусом свершиной в данной точке. 1.4 Математические основы решениязадачи линейного программирования графическим способом 1.4.1Математический аппарат
Для пониманиявсего дальнейшего полезно знать и представлять себе геометрическуюинтерпретацию задач линейногопрограммирования, которую можно дать для случаев n = 2 и n = 3.
Наиболеенаглядна эта интерпретация для случая n = 2, т.е. для случая двух переменных x1 и x2. Пусть нам задана задача линейного программирования встандартной форме
/>1.5)
/>
Возьмём наплоскости декартову систему координат и каждой паре чисел (x1,x2)поставим в соответствие точку наэтой плоскости.
/>
Обратимпрежде всего внимание на ограничения x1 ≥0 иx2 ≥ 0. Они из всей плоскости вырезают лишь еёпервую четверть (см. рис. 1). Рассмотрим теперь, какие области соответствуютнеравенствам вида a1 x1 + a2 x2 ≤ b.Сначала рассмотрим область, соответствующую равенству a1 x1 + a2 x2 = b. Как Вы, конечно, знаете, это прямая линия. Строить её прощевсего по двум точкам.
Пусть b ≠ 0. Если взять x1 = 0, то получится x2 = b/a2. Если взять x2 = 0, то получится x1 = b/a1. Таким образом, на прямой лежат две точки (0, b/a2) и (b/a1, 0). Дальше через эти две точки можно по линейкепровести прямую линию (рисунок 2).
/>
Если же b=0, то на прямой лежитточка (0,0). Чтобы найти другую точку, можно взять любое отличное от нулязначение x1 и вычислить соответствующее ему значение x2.
Этапостроенная прямая разбивает всю плоскость на две полуплоскости. В одной еёчасти a1x1 + a2x2 b. Узнать, в какой полуплоскости, какой знак имеет место прощевсего посмотрев, какому неравенству удовлетворяет какая-то точка плоскости,например, начало координат, т.е. точка (0,0). 1.4.2Геометрическая интерпретация задачи линейного программирования
Рассмотрим задачу ЛП встандартной форме записи:
maxf(X) = с1х1+ с2х2 +… + спхп (*)
при ограничениях
(**) а11х1+ а12х2 + … + а1nхn≤b1
а21х1+ а22х2 + … + а2nхn≤b2
……………………………..
(***) аm1х1 + аm2х2 + … + аmnхn≤bm
хj≥ 0, j= 1, 2, …, n.
Рассмотрим эту задачу наплоскости, т.е. при п = 2. Пусть система неравенств (**), (***) совместна(имеет хотя бы одно решение):
а11х1+ а12х2 ≤b1
а21х1+ а22х2 ≤b2
…………..
аm1х1 + аm2х2 ≤bm
x1≥ 0; х2≥ 0.
/>Каждое неравенство этой системы геометрически определяетполуплоскость с граничной прямой аi1х1 + аi2х2 ≤bii= 1, m. Условиянеотрицательности определяют полуплоскости соответственно с граничными прямыми x1= 0; х2 = 0.. Система совместна,поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общуючасть, которая является выпуклым множеством и представляет собой совокупностьточек, координаты каждой из которых составляют решение данной системы.Совокупность этих точек называют многоугольником решений. Это может быть точка,отрезок, луч, замкнутый многоугольник, неограниченная многоугольная область.
Если в системеограничений (**) — (***) n = 3, то каждое неравенство геометрически представляетполупространство трехмерного пространства, граничная плоскость которого аi1х1 + аi2х2 + аi3х1 ≤bi, а условия неотрицательности — полупространства с граничнымиплоскостями соответственно xi= 0 (i= 1, 2, 3). Если системаограничений совместна, то эти полупространства, как выпуклые множества,пересекаясь, образуют в трехмерном пространстве общую часть, которая называетсямногогранником решений.
/>/>Пусть в системе (**) — (***) п > 3,тогда каждое неравенство определяет полупространство n-мерного пространства сграничной гиперплоскостью аi1х1 + аi2х2 + … + аinхn≤bi i= 1, т, а условиянеотрицательности — полупространства с граничными гиперплоскостями xj= 0, j= 1, n.
Если системаограничений совместна, то по аналогии с трехмерным пространством она образуетобщую часть n-мерного пространства, называемую многогранникомрешений, так как координаты каждой его точки являются решением.
Таким образом,геометрически задача линейного программирования представляет собой отысканиетакой точки многогранника решений, координаты которой доставляют линейнойфункции минимальное значение, причем допустимыми решениями служат все точкимногогранника решений. 1.4.3Этапы решения графического метода задач линейного программирования
Графический метод основан на геометрической интерпретациизадачи линейного программирования и применяется в основном при решении задачдвумерного пространства и только некоторых задач трехмерного пространства, таккак довольно трудно построить многогранник решений, который образуется врезультате пересечения полупространств. Задачу пространства размерности большетрех изобразить графически вообще невозможно.
Пусть задача линейного программирования задана в двумерном пространстве,т. е. ограничения содержат две переменные.
Если в ЗЛП ограничениязаданы в виде неравенств с двумя переменными, она может быть решена графически.Графический метод решения ЗЛП состоит из следующих этапов.
Этап 1.
Сначала на координатнойплоскости x1Ox2 строится допустимая многоугольная область(область допустимых решений, область определения), соответствующаяограничениям:
/>1.6)
Не приводя строгихдоказательств, укажем те случаи, которые тут могут получится.
1. Основнойслучай — получающаяся область имеет вид ограниченного выпуклого многоугольника (рис. 1а).
2. Неосновнойслучай получается неограниченный выпуклый многоугольник, имеющий вид,подобный изображенному на рис. 1б. Подобная ситуация, например, получится, еслив рассмотренном выше примере убрать ограничение х1 + х 2 ≤3. Оставшаяся часть будет неограниченным выпуклым многоугольником.
Рис. 1
б)
а) />
Наконец, возможен случай,когда неравенства (1.6) противоречат друг другу, и допустимая областьвообще пуста.
Рассмотрим теорию на конкретном примере:
Найтидопустимую область задачи линейного программирования, определяемуюограничениями