Литература И. Л. Акулич. Математическое программирование в примерах и задачах

Вид материала

Литература

Содержание Графическое решение задач линейного программирования Прямая называется опорной Исследование устойчивости (дополнительный материал)

Подобный материал:

• Литература, 154.39kb.
• Учебной дисциплины «Выпуклый анализ и математическое программирование» для направления, 34.33kb.
• Аттестационное тестирование в сфере профессионального образования, 72.49kb.
• Программа дисциплины Математическое программирование Семестры, 10.84kb.
• И математическое моделирование, 1392.77kb.
• Учебно-методический комплекс курса по выбору "задачи егэ по информатике" (физико-математический, 704.64kb.
• Программа вступительного экзамена по специальности 05. 13. 18 Математическое моделирование,, 115.33kb.
• Рабочая программа по курсу "Функциональное программирование" Специальность, 144.38kb.
• Программа вступительных экзаменов по специальности 08. 00. 13 «Математические и инструментальные, 40.42kb.
• В примерах и задачах, 3217.34kb.

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


Литература

1. И. Л. Акулич. Математическое программирование в примерах и задачах
   
2. Е. С. Вентцель. Исследование операций: задачи, принципы, методология
   
3. Методические указания по графическому решению задач линейного программирования. Составитель Г. А. Кузнецова. – Иваново, 1989.
   

Примеры (задача о диете, составление плана производства, см. например ссылка скрыта )


Многие задачи сводятся к следующей математической модели:

F(x)  extr, (1)

xG. (2)

Такие задачи называются задачами математического программирования. Неизвестный вектор x называется вектором управляемых переменных. Функция F(x) называется целевой функцией, множество G называется допустимым множеством, а вектор x, удовлетворяющий условию (2), называется допустимым вектором. Допустимый вектор, доставляющий минимум (или максимум) целевой функции называется оптимальным решением задачи (1)–(2), а соответствующее значение целевой функции называется оптимумом.

Если F(x) и функции, задающие множество G, – линейные, то задача (1) (2) называется задачей линейного программирования. В общем виде ЗЛП может быть сформулирована так:

Найти набор (x₁, x₂, …, x_n), такой, что

целевая функция (линейная) должна достигнуть своего минимума (максимума)



при ограничениях в виде линейных равенств и неравенств







на некоторые переменные накладывается условие неотрицательности

.

В 1947 году Данциг предложил симплекс-метод для решения ЗЛП. Мы его не рассматриваем (познакомитесь в курсе исследования операций). Мы же рассмотрим графический метод решения ЗЛП.

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

Задача.

Имеются две линии по выпуску приемников.

	Мощность линии (изд./сут.)	Схем на один приемник (шт.)	Прибыль (долл.)
I линия	60	10	30
II линия	75	8	20

Запас схем на сутки составляет 800 шт. Определить оптимальные суточные объемы производства так, чтобы прибыль была максимальна.

Решение.

Пусть x_i – количество приемников, выпускаемых на i-той линии. Тогда математическая модель данной задачи имеет вид:



Изобразим сначала допустимое множество.

Напомним, что линейное неравенство с двумя переменными ax₁ + bx₂  c задаёт на плоскости полуплоскость. Чтобы изобразить эту полуплоскость, сначала проводим прямую, заданную уравнением ax₁ + bx₂ = c. Чтобы определить, какую именно из двух полуплоскостей определяет заданное неравенство, достаточно подставить в него координаты какой-нибудь одной точки, не лежащей на граничной прямой. Если неравенство удовлетворяется, то искомая полуплоскость – та, в которой лежит выбранная точка, а если не удовлетворяется, – то искомая полуплоскость – та, которой не принадлежит выбранная точка.

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



Рис. 1

На рис. 1 изображено допустимое множество нашей задачи, которое представляет собой многоугольник OABCD. Нетрудно уточнить координаты вершин допустимого множества: O(0, 0), A(0, 75), B(20, 75), C(60, 25), D(60, 0).

Рассмотрим теперь целевую функцию F(x₁, x₂) = d₁x₁ + d₂x₂. Линией уровня этой функции называется множество всех точек (x₁, x₂) плоскости x₁Ox₂, в которых функция принимает одно и то же заданное значение. Зафиксировав некоторое значение d, получаем, что линии уровня соответствует уравнение d₁x₁ + d₂x₂ = d, которое задает на плоскости прямую. При этом, взяв прямые, соответствующие разным значениям d, получим семейство параллельных прямых. Вектор-нормаль к любой прямой этого семейства имеет координаты (d₁, d₂). Можно показать, что при перемещении прямой семейства в направлении, указанном вектором-нормалью, мы получим линию уровня с большим значением целевой функции, а движение в направлении, противоположном вектору-нормали, уменьшает значение целевой функции.

Прямая называется опорной для множества G, если она имеет хотя бы одну общую точку с множеством G, а множество G лежит целиком по одну сторону относительной этой прямой. Чтобы найти графически решение ЗЛП, нужно найти опорную прямую (линию уровня) с соответствующим (максимальным или минимальным) значением функции.

Проведём произвольную линию уровня целевой функции так, чтобы она пересекала допустимое множество (см. на рис. 1 красные пунктирные линии). В нашей задаче нужно максимизировать значение целевой функции, поэтому будем сдвигать линию уровня в направлении вектора-нормали до тех пор, пока прямая не станет опорной для многоугольника OABCD. Линия уровня, соответствующая оптимальному решению проходит через точку C(60, 25). Значит, оптимальным решением нашей задачи являются x₁ = 60, x₂ = 25, а максимальное значение целевой функции F(x₁, x₂) = 3060 + 2025 = 2300.

Ответ: следует производить 60 приемников на линии I и 25 приемников на линии II, прибыль при этом равна 2300 долл.


Исследование устойчивости (дополнительный материал)

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



Рис. 2



Рис. 3



Рис. 4



Рис. 5




Рис. 6

Если известно, что прибыль от первого приемника может измениться на  ₁, то рассмотрим изменение прибыли второго при фиксированном c₁ = 30  ₁. Вектор (c₁, c₂) может изменяться от (30  ₁, 0) до

(10, 8) = (30  ₁, 0,8·(30  ₁)) =

= (30  ₁, 24  0,8 ₁),

т. е. c₂ изменяется от 0 до 24  ,8 ₁.

Если известно, что прибыль от второго приемника может измениться на  ₂, то рассмотрим изменение прибыли второго при фиксированном c₂ = 20  ₂. (c₁, c₂) может изменяться от

(10, 8) = (·(20  ₂), 20  ₂) =

= (25  1,25 ₂, 20  ₂)

до (, 20  ₂), т. е. c₁ изменяется от (25  1,25 ₂) до .