ПОЗНАВАТЕЛЬНОЕ

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

Отёска стен и прирубка косяков - Когда на доме не достаёт окон и дверей, красивое высокое крыльцо ещё только в воображении, приходится подниматься с улицы в дом по трапу.

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

Построение области допустимых решений задачи

Методические указания для лабораторных занятий

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

Направление подготовки 080200 Менеджмент

Профиль подготовки (бакалавриат)

Производственный менеджмент

Квалификация (степень) выпускника

Бакалавр

Уфа 2012

УДК 519.86

ББК 65.23

Л 12

Составитель: к.э.н., доцент Шатова В.С.

Рассмотрена и одобрена на заседании кафедры статистики и информационных систем в экономике «___»_______________2012 г. (протокол №___)

Зав.кафедрой статистики и ИСЭ к.э.н., доцент Аблеева А.М.

Рассмотрена и одобрена на заседании методической комиссии экономического факультета «___»_______________2012 г. (протокол №___)

Председатель методической комиссии экономического факультета

д.э.н.,, профессор Рафикова Н.Т.

ОГЛАВЛЕНИЕ

Введение

1 Цель и задачи…………………………………………………………… 4

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

графическим методом……… ………….………………………………4

2.1 Построение области допустимых решений задачи……..……… 5

2.2 Построение целевой функции…………………………………. . 6

2.3 Нахождение оптимального решения……………………………..7

3 Вопросы для самоконтроля…………………………………………….…8

4 Задания для самостоятельной работы………………………….………9

Библиографический список………………………………………………12

ВВЕДЕНИЕ

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

ЦЕЛЬ И ЗАДАЧИ

Цель: Освоить методику решения задач линейного программирования графическим методом.

Задачи: 1. Усвоить правила построения графического решения задачи линейного программирования.

2. Научиться определять область допустимых решений ЗЛП.

3. Научиться различать и оценивать зависимость между областью определения задачи и ее решением.

4. Решать задачи графическим методом с различными исходами.

5. Проводить анализ полученного решения.

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

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

Z = Х₁ - 3Х₂ => min (1)

10X₁ + 3X₂ > 30

-X₁ + X₂ < 3

X₁ - X₂ < 4 (2)

X₁ + X₂ < 10

X₁ > 0, X₂ > 0 (3)

Последовательность решения задачи.

Построение области допустимых решений задачи

Для этого:

- отобразить в прямоугольной системе координатусловия неотрицательности переменных (3). В двумерном пространстве уравнению соответствует прямая, а неравенству – полуплоскость, лежащая по одну сторону от прямой. Построим прямые Х₁ = 0, Х₂ = 0, которые лежаи на границах полуплоскостей и совпадают с осями координат. Полуплоскости Х₁ > 0, X₂ > 0 лежат соответственно справа от оси ОХ₂ и выше оси ОХ_1. Множество точек, удовлетворяющих одновременно неравенствам Х₁ > 0 и X₂ > 0, представляет собой пересечение построенных полуплоскостей вместе с граничными прямыми и совпадают с точками первой четверти;

- построить ограничения задачи (2). Для этого построить по порядку прямые (рис.1):

10X₁ + 3X₂ = 30 (1)

-X₁ + X₂ = 3 (2)

X₁ - X₂ = 4 (3)

X₁ + X₂ = 10 (4)

Рис.1. Графическое решение задачи

- установить,с какой стороны от этих прямых лежат полуплоскости, точки которых удовлетворяют строгим неравенствам:

10X₁ + 3X₂ > 30 (1)

-X₁ + X₂ < 3 (2)

X₁ - X₂ < 4 (3)

X₁ + X₂ < 10 (4)

Сторона, в которой располагается полуплоскость от прямой, указывается стрелкой. Убедиться в том, с какой стороны от прямой лежит полуплоскость, точки которой удовлетворяют заданному неравенству, можно путем подстановки координат точек одной или другой полуплоскости в неравенство. Когда прямая, ограничивающая полуплоскость, не проходит через начало координат, удобнее всего подставлять точку с координатами (0, 0). Если координаты точки удовлетворяют неравенству, то эта точка лежит в полуплоскости, соответствующей данному неравенству. В противном случае неравенству будет соответствовать другая полуплоскость;

- определить область определения задачи. Она будет представлять собой пересечение всех построенных полуплоскостей. В данном случае – это пятиугольник АВСDЕ. Каждая точка этого многоугольника, включая и точки, лежащие на его границах, будет удовлетворять ограничениям задачи.

2.2 Построение целевой функции

Для этого присвоить целевой функции Z значение нуль и построить прямую

Z = Х₁ - 3Х₂ = 0.

Эта прямая, проходящая через начало координат, строится следующим образом. Легко заметить, что в левой части данного уравнения стоит скалярное произведение двух векторов:

N = (с₁, с₂) = (1, -3) и Х = (х₁, х₂).

Скалярное произведение равно нулю когда векторы перпендикулярны.

Построим вектор N – вектор нормали. Он проходит через начало координат и точку (1, -3). Перпендикулярно ему через начало координат проведем прямую. Это и будет прямая целевой функции Z = 0.

Вектор N всегда показывает направление возрастания (максимизации) значения целевой функции, а противоположный ему вектор (- N ) – направление убывания (минимизации) значения целевой функции.

Передвигая прямую Z = 0 по области допустимых решений параллельно самой себе в направление вектора N, значения целевой функции будут возрастать. Передвижение ее в направлении вектора ( - N ) дает убывание целевой функции.

Передвижение на графике прямой Z = 0 равносильно изменению значения b в уравнении Х₁ - 3Х₂ = b. Каждому значению b соответствует прямая. Полученные прямые параллельны между собой и называются линиями уровня. Особенность линии уровня состоит в том, что целевая функция принимает на ней одинаковые значения, т.е. подставив координаты любой точки линии уровня в целевую функцию, ее значение изменяться не будет.