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

Курсовая работа

По дисциплине «МАТЕМАТИЧЕСКИЕ МЕТОДЫ»

Вариант 3.

                                                                                         Выполнил:

студент группы ПО-3-3

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

             «Программное обеспечение

   вычислительной техники и

автоматизированных систем»

Горбунов Дмитрий Валерьевич

 

Проверил:

                                                                                   Шихина В. А.

 

 

Краснодар, 2006

СОДЕРЖАНИЕ

 

Введение … … … … … … … … … … … … … … … … … … … … … … … … …. 2 Графический метод решения задач … … … … … … … … … … … … … … … … 3

Теория двойственности … … … … … … … … … … … … … … … … … … …... 6

Симплексный метод … … … … … … … … … … … … … … … … … … … … ….. 10

Транспортная задача … … … … … … … … … … … … … … … … … … … … …. 13

Список использованной литературы … … … … … … … … … … … … … … … … 24

ВВЕДЕНИЕ

Исследование операций — научная дисциплина, занимающая­ся разработкой и практическим применением методов наибо­лее эффективного управления различными организационными системами.

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

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

• построение экономических и математических моделей для
задач принятия решения в сложных ситуациях или в условиях
неопределенности;

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

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

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

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

Z(X) = c₁x₁ + c₂x₂ → max (min)

a₁₁x₁ + a₁₂x₂ ≤ (≥) b₁,

a₂₁x₁ + a₂₂x₂  ≤ (≥) b₂,

……………………………..

a_m1x₁ + a_m2x₂ ≤ (≥) b_m

x₁≥0, x₂≥0

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

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

Областью решений линейного неравенства a_i1x₁ + a_i2x₂ ≤b_i является одна из двух полуплоскостей, на которые прямая a_i1x₁ + a_i2x₂ = 0, соответствующая данному неравенству, делит всю координатную плоскость. Для того, чтобы определить, какая из полуплоскостей является областью решений, достаточно координаты какой-либо точки, не лежащей на прямой, подставить в неравенство: если оно удовлетворяется, то областью решений является полуплоскость, содержащая эту точку, если не удовлетворяется – то полуплоскость, не содержащая данную точку.

Для нахождения среди допустимых решений оптимального используют линии уровня и опорные прямые. Линией уровня называется прямая, на которой целевая функция задачи принимает постоянное значение. Уравнение линии уровня имеет вид c₁x₁ + c₂x₂ = L, где L = const. Все линии уровня параллельны между собой. Опорной прямой называется линия уровня, которая имеет хотя бы одну общую точку с областью допустимых решений и по отношению к которой эта область находиться в одной из полуплоскостей. Важное свойство линии уровня: при параллельном смещении линии в одну сторону уровень возрастает, а в другую сторону – убывает.

 

I Задание: Решить графическим методом задачу с двумя переменными.

 

 

 

    Z(x)=2х₁+3х₂ → max

 

 -6х₁+х₂ ≥ 3

 -5х₁+9х₂ ≤ 45

   х₁-3х₂ ≤ 3

 

     х₁ ≥ 0, х₂ ≥ 0

 

Найдем точки пересечения прямых с осями координат:

 

I. -6х₁+х₂=3

     1)х₁=0            2)х₂=0

     х₂=3                х₁= -1/2

 

II. -5х₁+9х₂=45

     1)х₁=0            2)х₂=0

      х₂=5               х₁= -9

 

III. х₁-3х₂=3

     1)х₁=0            2)х₂=0

      х₂= -1             х₁=3

 

 

Построим область решения данной системы:

 

 

Найдем вектор направленности целевой функции

 

 

Z(х)=2х₁+3х₂=0

1)х₁=0                2)х₁=3

х₂=0                    х₂= -2

 

Z(х)=2х₁+3х₂=6

1)х₁=0                2)х₂=0

х₂=2                    х₁=3

 

Ответ: Целевая функция принимает максимальное

значение в точке (0;0),   при х₁=0 и х₂=0.