Как найти многоугольник решений

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

(3.1)

(3.2)

Геометрический метод
не является общим методом решения задач
ЛП. Он выполняет лишь вспомогательную
роль и позволяет наглядно представить
себе свойства задачи ЛП и ее решение
симплекс-методом.

Пару неизвестных
и
рассмотрим как координаты точек плоскости
в которой определена декартова система
координат с осями и .
Множество пар значений ,
удовлетворяющих системе (3.2) называется
множеством допустимых решений
задачи ЛП.

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

будет отвечать некоторая область.

Определим вид этой области.

Каждое из неравенств
системы (3.2) заменим на прямую ,.
Это будет граничная прямая,
делящая плоскость на две части (на две
полуплоскости).

Для того чтобы выяснить
какая полуплоскость нам нужна необходимо
взять любую точку M из любой полуплоскости
(не на граничной прямой) и подставляем
координаты точки в неравенство. Если
неравенство верно, то полуплоскость,
которой принадлежит точка М,
является искомой. Если неравенство
оказалось неверным, то следует выбрать
противоположную полуплоскость.

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

Множество называется
выпуклым, если с
любыми двумя точками a
и b,
принадлежащими множеству оно содержит
и отрезок ,
их соединяющий.

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

Рассмотрим поведение
целевой функции (3.1) .

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

Вектор называется
целевым вектором
или вектором направлений.

Вектор показывает
направление наибольшего возрастания
(убывания) целевой функции.

Теорема. Если
основная задача ЛП имеет решение, то
max
(min)
значение целевая функция задачи принимает
в одной из вершин многоугольника
(многогранника) решений. Если max
(min)
значение целевая функция задачи принимает
более чем в одной вершине, то она принимает
его на прямой (или на отрезке).

Этапы решения задачи ЛП геометрическим
методом:

1. Построить граничные прямые,
   соответствующие данным
   ограничениям-неравенствам из системы
   (3.2).

2. Найти полуплоскости, определяемые
   каждым из ограничений системы (3.2).

3. Найти многоугольник решений.

4. Построить вектор
   .

5. Построить прямую
   ,
   проходящую через многоугольник решений.

6. Передвинуть прямую
   в направлении вектора.

7. Определить координаты точки максимума
   функции и вычислить значение целевой
   функции в этой точке.

Пример 3.1. Для
изготовления двух видов изделий I и II
используются три вида сырья. На
производство единицы изделия I требуется
затратить сырья первого вида 13 кг, сырья
второго вида – 32 кг, сырья третьего вида
– 58 кг. На производство единицы изделия
II требуется затратить сырья первого
вида 24 кг, сырья второго вида – 32 кг,
сырья третьего вида – 29 кг. Производство
обеспечено сырьем первого вида в
количестве 312 кг, сырьем второго вида –
480 кг, сырьем третьего вида – 696 кг.
Прибыль от реализации единицы готового
изделия I вида составляет 4 усл. ед, а
изделия II вида – 3 усл. ед.

Требуется составить план производства
изделий I и II, обеспечивающий максимальную
прибыль от их реализации, если заранее
планируется изготовление не менее 10
единиц изделий I и II.

Решение: Для удобства
оформим данные задачи в таблице.

Вид сырья	Кол-во затрачиваемого сырья (кг) на единицу изделия	Общее кол-во сырья (кг)
I	II
1	13	24	312
2	32	32	480
3	58	29	696
Прибыль (усл. ед)	4	3

Составим математическую модель задачи.

1. Введем переменные задачи:

х₁
– количество изделий вида I, планируемых
к выпуску;

x₂
– количество изделий вида II, планируемых
к выпуску.

2. Составим систему ограничений:

3. Зададим целевую функцию:

F(X)
= 4x₁
+ 3x₂
→ max

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

Для этого в прямоугольной
декартовой системе координат построим
прямую l₁:
13x₁+24x₂=312,
соответствующую ограничению (1). Для
этого найдем координаты двух точек,
принадлежащих данной прямой. Полагаем
x₁=0,
тогда x₂
= 13, возьмем x₂
= 0, получаем x₁=24.
Получили координаты точек В
(24, 0) и С
(0, 13).

Определим, какая из
двух полуплоскостей, на которые эта
прямая делит всю координатную плоскость,
является областью решений неравенства
(1). Для этого подставим, например,
координаты точки О
(0; 0), не лежащей на прямой l₁,
в данное ограничение:

13·0 + 24·0 ≤ 312. Получаем
0 ≤ 312, следовательно точка О
лежит в полуплоскости решений. Укажем
данную полуплоскость штриховкой (рис.1).

рис. 1

Аналогично строим
прямую l₂:
32x₁+32x₂
= 480, соответствующую ограничению (2) ,
находим полуплоскость решений. Отметим
штриховкой общую часть полуплоскостей
решений (рис. 2).

рис. 2

Строим прямую l₃:
58x₁
+ 29x₂
= 696, соответствующую ограничению (3),
находим полуплоскость решений. Штриховкой
обозначим общую часть полуплоскостей
решений (рис. 3).

рис. 3

Построим прямую l₄:
x₁+x₂
= 10. Определим, какая из двух полуплоскостей,
на которые эта прямая делит всю
координатную плоскость, является
областью решений неравенства (4). Для
этого подставим, например, координаты
точки О (0; 0), не лежащей на прямой l4, в
данное ограничение.

Получаем 0 ≥ 10,
следовательно точка О
не принадлежит полуплоскости решений.
Штрихуем ту часть плоскости относительно
прямой, где не лежит точка О.

Далее находим общую часть полуплоскостей
решений, учитывая при этом условия
неотрицательности переменных. Полученную
область допустимых решений отметим
штриховкой (рис. 4).

рис. 4

Построим нормаль
линий уровня
и одну из линий, например 4x₁
+ 3x₂
= 0.

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

рис. 5

Видим, что последней
точкой данного прямоугольника будет
точка G.
В данной точке значение функции будет
наибольшим.

Для нахождения
координат точки G
= l₂
∩ l₃
необходимо решить систему уравнений

Получим G(9,
6).

Находим F(G)
= 4·9 + 3·6 = 54.

Ответ: Для получения максимальной
прибыли 54 усл. ед, необходимо производить
9 изделий вида I и 6 изделий вида II.

Пример 3.2. Фирма по
производству строительных материалов
ООО «Вазелло» выпускает два вида
стройматериалов: жидкое стекло и
пенопласт. Трудозатраты на производство
1 т. стекла – 20 ч, пенопласта – 10 ч. В
кооперативе работают 10 рабочих по 40 ч.
в неделю. Оборудование позволяет
производить не более 15 т. стекла и 30 т.
пенопласта в неделю. Прибыль от реализации
1 т. жидкого стекла 50 тыс. руб.; 1 т.
пенопласта – 40 тыс. руб. Сколько
стройматериалов каждого вида следует
выпускать кооперативу для получения
максимальной прибыли?

Решение: Составим
математическую модель задачи.

1. Введем переменные задачи:

х₁
– объем производства жидкого стекла в
неделю;

x₂
– объем производства пенопласта в
неделю.

2. Составим систему ограничений:

3. Зададим целевую функцию:

F(X)
= 50x₁
+ 40x₂
→ max

Построим прямые
соответствующие данным неравенствам.

Получаем область
допустимых решений — пятиугольник AFGED
(рис. 6).

рис. 6

Построим вектор
.
Затем линию уровня перемещаем в
направлении нормали до последней точки
многоугольника решений.

В нашем случае, касание
линии уровня, перед выходом из области
допустимых решений, произойдет в точке
G
= l₁
∩ l₃.
В данной точке значение функции будет
наибольшим.

Найдем координаты
точки G. Решив систему
находимx₁=5,
x₂=30,
F(X)
= 1450.

Ответ: производство 5 т. жидкого стекла
и 30 т. пенопласта в неделю, обеспечивает
ООО «Вазелло» максимальную прибыль,
равную 1450000 рублей.

Пример 3.3.
(о составлении рациона).

Фармацевтическая фирма «Ozark» ежедневно
производит 800 фунтов некой пищевой
добавки – смеси кукурузной и соевой
муки, состав которой представлен в
следующей таблице.

Мука	Белок	Клетчатка	Стоимость (в долл. за фунт)
(в фунтах на фунт муки)
кукурузная	0,09	0,02	0,30
соевая	0,60	0,06	0,90

Диетологи требуют,
чтобы в пищевой добавке было не менее
30% белка и не более 5% клетчатки. Фирма
«Ozark» хочет определить рецептуру смеси
минимальной стоимости с учетом требований
диетологов.

Решение. Составим
математическую модель задачи.

1. Введем переменные задачи:

х₁
– количество (в фунтах) кукурузной муки,
используемой в производстве пищевой
добавки;

x₂
– количество
(в фунтах) кукурузной муки, используемой
в производстве пищевой добавки.

2. Составим систему ограничений.

Ограничение
описывает то условие, что фирма должна
выпускать не менее 800 фунтов в день.

Рассмотрим ограничение,
связанное с количеством белка в пищевой
добавке. Нам известно, что общее количество
белка (фунтов) должно составлять не менее 30%
от общего объема смеси ().
Отсюда получаем следующее неравенство:.

Аналогично строится ограничение для
клетчатки:

.

Окончательно система ограничений примет
следующий вид:

3. Зададим целевую функцию:

F(X) = 0,3x₁
+ 0,9x₂
→ min.

Построим прямые

соответствующие
данным неравенствам.

Получаем следующую область допустимых
решений (рис. 7).

рис. 7

Для удобства построения
построим вектор, коллинеарный вектору
.

Затем линию уровня
перемещаем в противоположном направлении
нормали. В нашем случае, касание прямой,
перед выходом из области допустимых
решений, произойдет в точке С
= l₁
∩ l₂
. В данной точке значение функции будет
наименьшим (рис 8).

рис. 8

Найдем координаты
точки С.

Решив систему
находим

.

Ответ: при 407,6 фунтах кукурузной муки
и 329,4 фунтах соевой муки минимальная
стоимость производимой ежедневно
пищевой добавки составляет 437,6 долл.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

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

Если что-то непонятно — вы всегда можете написать мне в WhatsApp и я вам помогу!

Введение в графический метод

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

Возможно эта страница вам будет полезна:

Задача линейного программирования в стандартной форме с двумя переменными имеет вид:

Эти задачи допускают простое геометрическое истолкование.

Рассмотрим вначале геометрическое истолкование системы ограничений задачи. Каждую совокупность значений переменных можно изобразить точкой на плоскости, если ввести систему координат и по одной оси откладывать , а по другой . Выясним, что геометрически означает совокупность решений одного отдельно взятого неравенства:

Рассмотрим прямую на плоскости с уравнением:

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

При решении двумерных задач линейного программирования возможны следующие ситуации (ОДР — область допустимых решений):

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

Отметим, что при нахождении решения задачи (5.1)-(5.3) могут встретиться случаи, изображенные на рис. 5.2- 5.5. Рис.5.2 характеризует такой случай, когда целевая функция принимает максимальное значение в единственной точке . Из рис. 5.3 видно, что максимальное значение целевая функция принимает в любой точке отрезка . На рис.5.4 изображен случай, когда целевая функция неограничена сверху на множестве допустимых решений, а на рис.5.5 — случай, когда система ограничений задачи несовместна, т. е. если система неравенств (5.1) при условии (5.2) не имеет решений.

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

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

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

1. Построить область допустимых решений.
2. Если область допустимых решений является пустым множеством, то задача не имеет решения ввиду несовместности системы ограничений.
3. Если область допустимых решений является непустым множеством, построить нормаль линий уровня и одну из линий уровня, имеющую общие точки с этой областью.
4. Линию уровня переместить до опорной прямой в задаче на максимум в направлении нормали, в задаче на минимум — в противоположном направлении.
5. Если при перемещении линии уровня по области допустимых решений в направлении, соответствующем приближению к экстремуму целевой функции, линия уровня уходит в бесконечность, то задача не имеет решения ввиду неограниченности целевой функции.
6. Если задача линейного программирования имеет оптимальное решение, то для его нахождения решить совместно уравнения прямых, ограничивающих область допустимых решений и имеющих общие точки с соответствующей опорной прямой. Если целевая функция задачи достигает экстремума в двух угловых точках, то задача имеет бесконечное множество решений. Оптимальным решением является любая выпуклая линейная комбинация этих точек. После нахождения оптимальных решений вычислить значение целевой функции на этих решениях.

Пример задачи №1

Пусть имеется два станка , на каждом из которых можно производить два вида продукции . Станок производит единицу продукции за 1 час, а единицу продукции — за 2 часа. Станок затрачивает на единицу продукции — 2 часа, а на единицу продукции — 1 час. Станок может работать в сутки не более 10 ч., а станок — не более 8 ч. Стоимость единицы продукции составляет руб., а стоимость единицы продукции — руб. Требуется определить такие объемы выпуска продукции и на станок, чтобы выручка от реализации производственной продукции была максимальной.

Решение:

Для наглядности сведем условие задачи в таблицу 5.1.

Составим математическую модель задачи. Обозначим через и количества продукции и , которые планируется произвести на каждом отдельном станке. Стоимость произведенной продукции . Мы должны назначить и так, чтобы величина была максимальной.

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

Аналогично можно получить неравенство для станка . Кроме того, величины и не могут быть отрицательными:

по смыслу задачи. Такие задачи кратко записываются следующим образом:

Итак, математическая модель задачи: найти такой план выпуска продукции , удовлетворяющий системе (5.4) и условию (5.5), при котором функция (5.6) принимает максимальное значение.

Решения, удовлетворяющие системе ограничений (5.4) и требованиям неотрицательности (5.5), являются допустимыми, а решения, удовлетворяющие одновременно и требованию (5.6) — оптимальными.

Рассмотрим геометрическое истолкование задачи:

Возьмем и .

Математическая модель задачи:

Построение области допустимых решений целевой функции :

1.Построим прямоугольную систему координат. Так как, и неотрицательны, то можно ограничиться рассмотрением первого квадранта.

Рассмотрим первое ограничение:

Рассмотрим второе ограничение:

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

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

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

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

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

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

Множество решений системы ограничений задачи ЛП образует область допустимых решений (ОДР).

Графический метод решения задач ЛП основывается на возможности графического изображения ОДР и нахождении среди них оптимального решения. Этот метод применяется для задач ЛП с одной, двумя или тремя переменными, для которых система ограничений стандартна (состоит из неравенств), и задач со многими переменными, для которых система ограничений содержит переменных и или линейно независимых уравнений.

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

I. Одномерное пространство переменных

Решение системы ограничений есть пересечение лучей, что определяет интервал решений (ОДР): точку, отрезок, луч или всю числовую прямую.

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

В случае неограниченности ОДР задача ЛП может и не иметь оптимума.

II. Двумерное пространство переменных

Областью решений линейного неравенства

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

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

многоугольник решений (ОДР).

Линией уровня называется прямая, на которой целевая функция задачи принимает постоянное значение. Уравнение

задаёт семейство линий уровня исследуемой целевой функции — параллельные прямые с нормальным вектором , который определяет направление роста функции , т. к. является её градиентом.

Замечание.

Т. о., если линию уровня перемещать параллельно самой себе в направлении вектора нормали, то значение целевой функции будет увеличиваться; если линию уровня перемещать параллельно самой себе в направлении противоположном вектору нормали, то значение целевой функции будет уменьшаться. Поскольку требуется найти оптимальное решение, при котором целевая функция стремится к максимуму или минимуму, то необходимо перемещать линию уровня до положения касания с ОДР (положения опорной прямой).

• Прямая

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

Значение есть экстремальное значение исследуемой целевой функции.

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

Замечание. Если заданы ограничения неотрицательности переменных, то все построения проводятся в первой четверти.

Особые случаи

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

1. Находим область допустимых решений из системы ограничений. Если ОДР является пустым множеством, то задача ЛП неразрешима (не имеет решения) в виду несовместности системы ограничений.
2. Если область допустимых решений является непустым множеством, строим направляющий вектор прямой и параллельно ему проводим линию уровня .
3. Строим вектор нормали перпендикулярно прямой .
4. Линию уровня перемещаем до положения опорной прямой в направлении вектора для задач на максимум или в направлении, противоположном для задач на минимум. Т. е. перемещение проводится до тех пор, пока линия уровня не коснется области допустимых решений. Общая точка (точки) будет точкой экстремума (оптимума) целевой функции в ОДР.
5. Находим координаты точки экстремума и значение целевой функции в ней, т. е. оптимум задачи ЛП.

Пример задачи №2

Найти , при котором функция достигает экстремума:

если имеются ограничения:

Решение:

Система ограничений определяет граничные прямые:

С учётом исходной системы неравенств строим ОДР.

Прямая

имеет вектор нормали (5;4) и направляющий вектор (-4;5). Опорное положение максимума линия уровня функции занимает в точке (направление роста вектора нормали); в точке — опорное положение минимального значения линия уровня функции.

Т. о. имеем:

Тогда

Ответ:

Пример задачи №3

Найти план

при котором:

Решение:

Строим ОДР, проводим линии уровня :

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

Общее решение (выпуклая линейная комбинация точек отрезка ) имеет вид:

Вычисляем

Ответ:

Пример задачи №4

Найти план

при котором

Решение:

Строим ОДР, проводим линию уровня :

и вектор = (3;7). В данной задаче необходимо найти максимум целевой функции, поэтому линию уровня фиксируем в направлении нормального вектора. В виду того, что в направлении вектора нормали ОДР не ограничена, линия уровня уходит в бесконечность, т. е. max

Таким образом, задача ЛП не имеет решения в виду неограниченности целевой функции.

Пример задачи №5

Найти план

при котором

Решение:

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

III. Трёхмерное пространство переменных

Решение системы ограничений — многогранник решений (ОДР) — пересечение полупространств с граничными плоскостями

Уравнение

задаёт семейство поверхностей уровня функции , т.е. параллельных плоскостей с нормальным вектором , который определяет направление роста целевой функции , т. к. является её градиентом.

Плоскость

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

Графический метод в виду большой размерности реальных практических задач ЛП достаточно редко применяется, однако он позволяет уяснить одно из основных свойств ЛП- если в задаче ЛП существует оптимальное решение, то, по крайней мере, одна из вершин допустимой области определяет собой оптимальное решение.

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

Основной случай: система ограничений содержит переменных и линейно независимых уравнения:

Расширенную матрицу системы с помощью элементарных преобразований строк можно привести к виду:

Тогда соответствующая система уравнений примет вид:

Выражая базисные неизвестные и учитывая их неотрицательность, получим систему неравенств с неизвестными :

Подставляя полученные выражения для базисных неизвестных в целевую функцию, получим:

Преобразованная задача ЛП содержит только два неизвестных. Следовательно, возможен графический способ её решения на плоскости.

Найденное решение подставляют в систему (*) и получают искомый оптимальный план

При этом оптимум:

Пример. Решить задачу ЛП:

Решение. Метод применим,так как . Методом Жордана-Гаусса приведём систему уравнений ограничений задачи к равносильной путём выделения базисных и свободных переменных. Одновременно исключим базисные переменные из целевой функции.

Используя последнюю часть табл., запишем задачу ЛП в преобразованном виде:

Отбросим в уравнениях-ограничениях неотрицательные базисные переменные , и заменим знаки равенства знаками неравенства .

Получим вспомогательную задачу ЛП с двумя переменными:

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

Находим оптимальное решение вспомогательной задачи :

Вычисляем минимальное значение целевой функции

Находим оптимальное решение исходной задачи:

Т. о., получаем:

Возможно эти страницы вам будут полезны:

1. Решение задач по математическому программированиюПримеры решения задач по математическому программированиюЗаказать работу по математическому программированиюПомощь по математическому программированиюЗадачи математического программированияЗадача линейного программированияРешение задач по линейному программированиюМетоды решения задач линейного программированияГрафическое решение задач линейного программированияЗаказать работу по линейному программированиюПомощь по линейному программированиюКонтрольная работа по линейному программированиюЛинейное программирование в ExcelКурсовая работа по линейному программированию

Содержание:

Исследование различных процессов, в том числе и экономических, обычно начинается с их моделирования, т.е. отражения реального процесса через математические соотношения. При этом составляются уравнения или неравенства, которые связывают различные показатели (переменные) исследуемого процесса, образуя систему ограничений. В этих процессах выделяются такие переменные, меняя которые можно получить оптимальное значение основного показателя данной системы (прибыль, доход, затраты и т.д.). Соответствующие методы, позволяющие решать указанные задачи, объединяются под общим названием «математическое программирование» или математические методы исследования операций.

Математическое программирование включает в себя такие разделы математики, как линейное, нелинейное и динамическое программирование. Сюда же относят и стохастическое программирование, теорию игр, теорию массового обслуживания, теорию управления запасами и некоторые другие.

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

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

Построение математической модели экономической задачи включает следующие этапы:

1. выбор переменных задачи;
2. составление системы ограничений;
3. выбор целевой функции.

Переменными задачи называются величины

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

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

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

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

Данная запись означает следующее: найти экстремум целевой функции задачи и соответствующие ему переменные X = (). при условии, что эти переменные удовлетворяют системе ограничений и условиям неотрицательности.

Допустимым решением (планом) задачи линейного программирования называется любойX = (). удовлетворяющий системе ограничений и условиям неотрицательности. Множество допустимых решений (планов) задачи образует область допустимых решений.

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

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

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

Используя знак суммирования эту задачу можно записать следующим образом:

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

В данном случае введены векторы:

Здесь С — X — скалярное произведение векторов С и X.

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

где:

Здесь А — матрица коэффициентов системы уравнений, X -матрица-столбец переменных задачи; — матрица-столбец правых частей системы ограничений.

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

Приведение общей задачи линейного программирования к канонической форме

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

прибавляется величина такая, что переводит неравенство в равенство , где:

Неотрицательная переменная называется дополнительной переменной.

Основания для возможности такого преобразования дает следующая теорема.

Теорема. Каждому решению неравенства соответствует единственное решение уравнения: и неравенства и, наоборот, каждому решению уравнения: и неравенства соответствует единственное решение неравенства:

Доказательство. Пусть — решение неравенства. Тогда:

Если в уравнение вместо переменных подставить значения , получится:

Таким образом, решение удовлетворяет уравнению: и неравенству .

Доказана первая часть теоремы.

Пусть удовлетворяет уравнению и неравенству , т.е. . Отбрасывая в левой части равенства неотрицательную величину , получим:

т.е. удовлетворяет неравенству: что и требовалось доказать.

Если в левую часть неравенств системы ограничений вида

добавить переменную , то получится система ограничений — уравнений В случае, если система неравенств-ограничений имеет вид , то из левой части неравенств-ограничений нужно вычесть соответствующую неотрицательную дополнительную переменную

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

Дополнительные переменные вводятся в целевую функцию с нулевыми коэффициентами и поэтому не влияют на ее значения.

В реальных практических задачах дополнительные неизвестные имеют определенный смысл. Например, если левая часть ограничений задачи отражает расход ресурсов на производство продукции в объемах , а правые части — наличие производственных ресурсов, то числовые значения дополнительных неизвестных и означают объем неиспользованных ресурсов i-го вида.

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

Множества допустимых решений

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

Выпуклой линейной комбинацией произвольных точек Евклидова пространства называется сумма — произвольные неотрицательные числа, сумма которых равна 1.

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

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

Граничные точки множества образуют его границу. Множество называется замкнутым, если оно содержит все свои граничные точки.

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

Пересечение двух или более выпуклых множеств будет выпуклым множеством, так как оно отвечает определению выпуклого множества.

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

Так, угловые точки треугольника — его вершины, круга — точки окружности, ее ограничивающие, а прямая, полуплоскость, плоскость, полупространство, пространство не имеют угловых точек.

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

Теорема. Любая тонка многоугольника является выпуклой линейной комбинацией его угловых точек.

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

Уравнение целевой функции при фиксированных значениях самой функции является уравнением прямой линии (плоскости, гиперплоскости и т.д.). Прямая, уравнение которой получено из целевой функции при равенстве ее постоянной величине, называется линией уровня.

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

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

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

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

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

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

Базисным решением системы называется частное решение, в котором неосновные переменные имеют нулевые значения. Любая система уравнений имеет конечное число базисных решений, равное , где n — число неизвестных, r- ранг системы векторов условий. Базисные решения, координаты которых удовлетворяют условию неотрицательности, являются опорными.

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

Число отличных от нуля координат опорного решения не может превосходить ранга r системы векторов условий (т.е. числа линейно независимых уравнений системы ограничений).

Если число отличных от нуля координат опорного решения равно m, то такое решение называется невырожденным, в противном случае, если число отличных от нуля координат опорного решения меньше т, такое решение называется вырожденным.

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

Теорема. Любое опорное решение является угловой точкой области допустимых решений.

Теорема. Любая угловая точка области допустимых решений является опорным решением.

Пример:

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

Предприятие изготавливает изделия двух видов А и В. Для производства изделий оно располагает сырьевыми ресурсами трех видов С, D и Е в объемах 600, 480 и 240 единиц соответственно. Нормы расхода ресурсов на единицу продукции каждого вида известны и представлены в табл. 14.1

Прибыль от реализации изделия А составляет 40 млн. руб., а изделия В — 50 млн.руб. Требуется найти объемы производства изделий А и В, обеспечивающие максимальную прибыль.

Построим математическую модель задачи, для чего обозначим — объемы производства изделий А и В соответственно.

Тогда прибыль предприятия от реализации изделий А и изделий В составит:

Ограничения по ресурсам будут иметь вид:

Естественно, объемы производства должны быть неотрицательными

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

Каждое из записанных уравнений представляет собой прямую на плоскости, причем 4-я и 5-я прямые являются координатными осями.

Чтобы построить первую прямую, найдем точки ее пересечения с осями координат: а при .

Далее нас интересует, по какую сторону от прямой будет находиться полуплоскость, соответствующая первому неравенству. Чтобы определить искомую полуплоскость, возьмем точку O(0,0) подставив ее координаты в неравенство, видим, что оно удовлетворяется. Так как точка O(0,0) лежит левее первой прямой, то и полуплоскость будет находиться левее прямой

. На рис 14 , расположение полуплоскости относительно первой прямой отмечено стрелками.

Аналогично построены 2-я и 3-я прямые и найдены полуплоскости, соответствующие 2-му и 3-му неравенству. Точки, удовлетворяющие ограничениям , находятся в первом квадранте. Множество точек, удовлетворяющих всем ограничениям одновременно, является ОДР системы ограничений. Такой областью на графике (рис. 14.1) является многоугольник ОАВС.

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

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

имеет координаты

Рис. 14.1

Изобразим вектор на графике и построим прямую функции перпендикулярно вектору на рис. 14.1. Перемещая прямую функции параллельно самой себе в направлении вектора, видим, что последней точкой многоугольника решений, которую пересечет прямая функции, является угловая точка В. Следовательно, в точке В функция достигает максимального значения. Координаты точки В находим, решая систему уравнений, прямые которых пересекаются в данной точке.

Решив эту систему, получаем, что

Следовательно, если предприятие изготовит изделия в найденных объемах, то получит максимальную прибыль, равную:

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

1. Строится область допустимых решений;
2. Строится вектор нормали к линии уровня с точкой приложении в начале координат;
3. Перпендикулярно вектору нормали проводится одна из линий уровня, проходящая через начало координат;
4. Линия уровня перемещается до положения опорной прямой. На этой прямой и будут находиться максимум или минимум функции.

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

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

На рисунке 14.4 изображен случай, когда система ограничений образует неограниченное сверху множество. Функция Z в данном случае стремится к бесконечности, так как прямую функции можно передвигать в направлении вектора градиента как угодно далеко, а на рисунке 14.5 представлен случай несовместной системы ограничений.

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

Среди универсальных методов решения задач линейного программирования наиболее распространен симплексный метод (или симплекс-метод), разработанный американским ученым Дж.Данцигом. Суть этого метода заключается в том, что вначале получают допустимый вариант, удовлетворяющий всем ограничениям, но необязательно оптимальный (так называемое начальное опорное решение); оптимальность достигается последовательным улучшением исходного варианта за определенное число этапов (итераций). Нахождение начального опорного решения и переход к следующему опорному решению проводятся на основе применения рассмотренного выше метода Жордана-Гаусса для системы линейных уравнений в канонической форме, в которой должна быть предварительно записана исходная задача линейного программирования; направление перехода от одного опорного решения к другому выбирается при этом на основе критерия оптимальности (целевой функции) исходной задачи.

Симплекс-метод основан на следующих свойствах задачи линейного программирования:

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

Рассмотрим две разновидности симплексного метода: симплекс-метод с естественным базисом и симплекс-метод с искусственным базисом (или М-метод).

• Заказать решение задач по высшей математике

Симплекс-метод с естественным базисом

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

Для определенности предположим, что первые m векторов матрицы системы составляют единичную матрицу. Тогда очевиден первоначальный опорный план:

Проверка на оптимальность опорного плана проходит с помощью критерия оптимальности, переход к другому опорному плану — с помощью преобразований Жордана-Гаусса и с использованием критерия оптимальности.

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

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

Теорема 1. Если для некоторого вектора, не входящего в базис, выполняется условие:

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

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

Теорема 2. Если для всех векторов выполняется условие то полученный план является оптимальным.

На основании признака оптимальности в базис вводится вектор Ак, давший минимальную отрицательную величину симплекс-разности:

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

Строка называется направляющей, столбец и элемент — направляющими (последний называют также разрешающим элементом).

Элементы вводимой строки, соответствующей направляющей строке, в новой симплекс-таблице вычисляются по формулам:

а элементы любой другой i-й строки пересчитываются по формулам:

Значения базисных переменных нового опорного плана (показатели графы «план») рассчитываются по формулам:

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

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

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

Симплексный метод с искусственным базисом (М-метод)

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

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

В полученной задаче первоначальный опорный план очевиден. При применении к этой задаче симплекс-метода оценки А, теперь будут зависеть от числа М. Для сравнения оценок нужно помнить, что М — достаточно большое положительное число, поэтому из базиса будут выводиться в первую очередь искусственные переменные.

В процессе решения M-задачи следует вычеркивать в симплекс-таблице искусственные векторы по мере их выхода из базиса. Если все искусственные векторы вышли из базиса, то получаем исходную задачу. Если оптимальное решение М-задачи содержит искусственные векторы или М-задача неразрешима, то исходная задача также неразрешима.

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

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

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

Любую задачу линейного программирования можно записать в виде:

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

Модель двойственной задачи имеет вид:

Переменные двойственной задачи называют объективно обусловленными оценками или двойственными оценками.

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

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

1. Целевая функция исходной задачи формулируется на максимум, а целевая функция двойственной задачи — на минимум, при этом в задаче на максимум все неравенства в функциональных ограничениях имеют вид <, а в задаче на минимум — вид
2. Матрица , составленная из коэффициентов при неизвестных в системе ограничении исходной задачи, и аналогичная матрица , в двойственной задаче получаются друг из друга транспонированием;
3. Число переменных в двойственной задаче равно числу функциональных ограничений исходной задачи, а число ограничений в системе двойственной задачи — числу переменных в исходной задаче;
4. Коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе ограничений исходной задачи, а правыми частями в ограничениях двойственной задачи — коэффициенты при неизвестных в целевой функции исходной задачи;
5. Каждому ограничению одной задачи соответствует переменная другой задачи: номер переменной совпадает с номером ограничения; при этом ограничению, записанному в виде неравенства <, соответствует переменная, связанная условием неотрицательности.

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

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

где:

Рассмотрим пример, показывающий, как в реальной экономической ситуации появляются взаимно двойственные задачи линейного программирования.

На некотором предприятии после выполнения годового плана возник вопрос: как поступить с остатками сырья? Из оставшегося сырья можно наладить производство продукции и реализовать его или продать сырье.

Предположим, что имеется два вида сырья , остатки которого составляют соответственно 35 и 20 единиц. Из этого сырья можно наладить производство трех видов товаров:

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

Прибыль, которую получит предприятие от реализации товара, составит:

В интересах предприятия эту прибыль максимизировать.

Это прямая задача.

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

Справедливое требование со стороны продающего предприятия состоит в следующем: если взять сырье, идущее на производство единицы товара то выручка от его продажи должна быть не меньше, чем прибыль от реализации готового изделия (в противном случае нет смысла продавать сырье — целесообразнее изготовить товар и получить прибыль от его реализации).

Это требование можно представить в виде системы неравенств:

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

Что касается покупателя, то он заинтересован в минимизации расходов на покупку сырья, т.е. величины

Теоремы двойственности

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

Возможны следующие случаи:

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

Первая теорема двойственности.

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

1. В прямой и двойственной задачах имеются оптимальные решения, при этом значения целевых функций на оптимальных решениях совпадают:
2. В прямой задаче допустимое множество не пусто, а целевая функция на этом множестве не ограничена сверху. При этом у двойственной задачи будет пустое допустимое множество.
3. В двойственной задаче допустимое множество не пусто, а целевая функция на этом множестве не ограничена снизу. При этом у прямой задачи допустимое множество оказывается пустым;
4. Обе из рассматриваемых задач имеют пустые допустимые множества.

Вторая теорема двойственностн (теорема о дополняющей нежесткости):

Пусть — допустимое решение прямой задачи, а допустимое решение двойственной задачи.

Для того, чтобы они были оптимальными решениями соответствующих взаимодвойственных задач, необходимо и достаточно, чтобы выполнялись следующие соотношения:

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

Теорема об оценках:

Значения переменных в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов системы ограничений — неравенств прямой задачи на величину :

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

Экономический смысл первой теоремы двойственности следующий. План производства X и набор ресурсов Y оказываются оптимальными тогда и только тогда, когда прибыль от реализации продукции, определенная при известных заранее ценах продукции , равна затратам на ресурсы по «внутренним» (определяемым только из решения задачи) ценам ресурсов Для всех других планов прибыль от продукции всегда меньше или равна стоимости затраченных ресурсов , т.е. ценность выпущенной продукции не превосходит суммарной оценки затраченных ресурсов. Значит, величина Z(X)~ F(Y) характеризует производственные потери в зависимости от рассмотренной производственной программы и выбранных оценок ресурсов.