Как найти линию уровня целевой функции - Исправление недочетов и поиск решений вместе с Examum.ru

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

_{Пусть

дана задача:}

_{Х

= (х}₁_;

х₂_),_max_Z₌_c₁_x₁₊_c₂_x₂_,

Дадим
геометрическую интерпретацию этой
задачи:

а)
построим плоскость Х₁ОХ₂.
На этой плоскости каждое из линейных
ограничений-неравенств задает некоторую
полуплоскость. Полуплоскость
–
выпуклое
множество, а пересечение выпуклых
множеств
–
есть также выпуклое множество, значит
область допустимых решений
–
есть выпуклое множество.

При
построении области допустимых решений
(ОДР) возможны следующие ситуации (рис.
3 – 8).

а	б
Рис. 3	Рис. 4
ОДР – выпуклый многоугольник	ОДР – неограниченная выпуклая многоугольная область
М в	г
Рис. 5 ОДР – единственная точка	Рис. 6 ОДР – прямая линия

Рис.
7

ОДР
–
пустое множество

Рис.
8

б)
перейдем к геометрической интерпретации
целевой функции. Пусть
ОДР –
не пустое множество, например, многоугольник
А₁А₂А₃А₄А₅А₆.(рис.
8).

Выберем
произвольное значение целевой функции:
Z = Z_о
= > c₁х₁
+ + с₂х₂
= Z_о
–
это
уравнение прямой линии (обычно берут
Z_о
= 0), ее называют линией уровня целевой
функции. Чтобы установить направление
возрастания (убывания) целевой функции,
найдем ее частные производные

;

_.

Вектор

₌_g_ra_d

z_–_{показывает направление наискорейшего}
_{возрастания

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

всегда
перпендикулярен к линиям уровня

Правило
решения задачи линейного программирования:

1)
строим область допустимых решений;

2)
строим

;

3)
проводим
произвольную линию уровня Z = Z_о
(для контроля убеждаемся, что прямая z
= z_o
_┴
);

4)
при
решении задачи на mах перемещаем линию
уровня Z = Z_o
параллельно самой себе в направлении
вектора

до тех пор пока она не коснулась области
ДР в ее угловой точке (до т. А₄),
пока она не станет опорной. В случае
решения задачи на min линию уровня Z = Z_o
перемещают в антиградиентном направлении
(до т. А₁);

5)
определяем
оптимальный план

*
= (х₁*;
х₂*),
то есть координаты угловой точки касания
и экстремальное значение целевой функции
Z*=Z(x*
).

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

1)
оптимальный план единственный:
опорная линия и ОДР имеют одну общую
точку (этот случай уже рассмотрен);

Рис.
9

2)
оптимальных планов большое множество:
в разрешающем положении
опорная линия уровня
совпадает со стороной ОДР (рис. 9);

Рис.
10

3)
целевая
функция не ограничена, линия уровня,
сколько бы ее не продолжали, не может
занять опорного положения (рис. 10);

Рис.
11

4)
ОДР – состоит из единственной точки,
где целевая функция достигает
одновременно и max и min
(рис. 11);

5)
задача
не имеет решений, т. к. ОДР

Пример
4.
Задача
использования сырья: найти max
Z = 50х₁
+ 40х₂,
если

Решение.

Обозначим

Тогда:

1.
Построим
ОДР (рис. 12): для этого в системе координат
Х₁ОХ₂
изобразим граничные прямые

L₁:
2x₁
+ 5x₂
= 20, (0; 4) (10; 0);

L₂:
8x₁
+ 5х₂
= 40, (0; (5; 0) (ОДР –
многоугольник АВСДО);

L₃:
5x₁
+ 6х₂
= 30, (0; 5) (6; 0).

=
(50; 40) => удобно
строить не вектор

,
а


,
где

.
Строим

_,(5;
4).

3.
Строим
линию уровня:

Рис.
12

= 50x₁
+ 40x₂
= 0 => x₁=
–

= –
0,8x₂,
(0, 0), (–
4,
5)

и
перемещаем ее в направлении

.
Эта прямая станет опорной в точке С.
Функция Z принимает max значение в этой
точке. Найдем точку С как точку пересечения
прямых L₂
и L₃:

=
48 – 25 = 23;

= 240 – 150 = 90;

= 240 –
200 = 40; оптимальный план:

,

Z
max
= 50 · 3,9 + 40 · 1,7 ≈ 260,3. Таким образом, чтобы
получить max прибыль в размере 260,3 руб.
надо запланировать производство 3,9
единиц продукции Р₁
и 1,7 единиц продукции Р₂.

Пример
5.
Задача
составления рациона: найти min Z = 4х₁
+ 6х₂

_если

Решение.

1.
Строим ОДР 
для этого в системе координат X₁
ОХ₂ изобразим граничные прямые
(рис. 13):

L₁:
3x₁
+ x₂
= 9, (0; 9) (3; 0);

L₂:
x₁
+ 2х₂
= 8, (0; 4) (8; 0);

L₃:
x₁
+ 6х₂
= 12, (0; 2) (12; 0).

= (4; 6).

3.
Z_o
= 4x₁
+ 6x₂—
линия уровня.

Если
4x₁
+ 6x₂
= 0,

Рис.
15.

х₁
= –

х₂,
(6; –
4)
(0; 0).

Рис.
13

4.
Линия
уровня
станет опорной в точке В, найдем ее,
решив систему:




(·)
В (2, 3).

Оптимальный
план (2,3) 
Z_min
= 4 ∙ 2 + 6 ∙ 3 = 26.

Итак,
чтобы
обеспечить min затраты в день 26 руб.
необходимо дневной рацион составить
из 2 кг корма 1 и 3 кг корма 2.

Замечание.
С помощью графического метода может
быть решена задача линейного
программирования, система ограничений
которой содержит m-линейно
независимых уравнений и если n
– m = 2.

Пример
6.

Графическим
методом найти оптимальный план задачи
линейного программирования, при котором
целевая функция Z = 2х₁
– х₂
+ х₃
– 3х₄
+ 4х₅
достигает max значения при ограничениях:

то
есть
n
= 5, m
= 3 и n
–
m
= 2

Решение.

Решим систему методом полного исключения:



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

и

и
Z
= 12 –
2x₄
+ 6x₅
– 70 + 7x₄
+ 10x₅
+ 20 + 4x₄
–
5x₅
–
3x₄
+ 4x₅
= –
38
+ 6x₄
+ 15x₅.

Итак,
найти max Z = –
38
+ 6х₄
+ 15х₅,
если

–

4x
+
5x

+x
=
20

7x
+
10x

+ x

= 70

x
–
3x

+ x

= 6

x

(j
= 1, 2, 3, 4, 5).

Отбрасывая
в системе уравнений базисные переменные,
приходим к системе неравенств:

3.
Решаем полученную задачу графическим
методом.

а)
Построим ОДР в плоскости Х₄ОХ₅
(рис. 14).

Рис.
14

L₁:
–
4x₄
+ 5x₅
= 20, (0; 4) (–
5;
0),

L₂:
7x₄
+ 10х₅
= 70, (0; 7) (10; 0),

L₃:
x₄
–
3х₅
= 6, (0; –
2)
(6; 0);

б)

= (6; 15) 


= (2; 5),

в)
Z_o
= –
38

6x₄
+ 15x₅
= 0,

(0;
0) (5; –
2).

г)
Целевая функция принимает max значение
в точке В, найдем ее

_

max
Z = –
38
+ 12 + 84 = 58.

д)
Для отыскания
оптимального плана подставим значения
х₄
и х₅
в x₁,
х₂,
х₃,
получим

:
х₁
=

;
х₂
= 0; х₃
= 0; х₄
= 2; х₅
=

;

Ответ:

= (
;
0; 0; 2;

),
max
Z
= 58.

Источник

Введение в графический метод
- Алгоритм графического метода решении задач линейного программирования
  - Пример задачи №1
- Графический метод решения задач линейного программирования
  - I. Одномерное пространство переменных
  - II. Двумерное пространство переменных
  - Особые случаи
- Алгоритм графического метода решения задач линейного программирования с двумя переменными
  - Пример задачи №2
  - Пример задачи №3
  - Пример задачи №4
  - Пример задачи №5
  - III. Трёхмерное пространство переменных

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример задачи №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. Двумерное пространство переменных

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

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

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

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

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

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

Замечание.

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

• Прямая

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

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

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

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

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

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

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

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

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

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

Решение:

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

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

Прямая

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

Т. о. имеем:

Тогда

Ответ:

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

Найти план

при котором:

Решение:

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

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

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

Вычисляем

Ответ:

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

Найти план

при котором

Решение:

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

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

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

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

Найти план

при котором

Решение:

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

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

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

Уравнение

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

Плоскость

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

линейного программирования к другой

1. Приведение к
канонической задаче линейного программирования

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

Пример
1.1. Привести задачу к канонической
форме.

Решение.
Неравенств в задаче три, поэтому вводятся три вспомогательные неотрицательные
переменные , , . К левой части 1-го неравенства
нужно добавить вспомогательную переменную ,
а из левой части 2-го и 3-го неравенств вычесть соответствующие вспомогательные
переменные и .
Получим каноническую задачу

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

Пример 1.2.
Привести каноническую задачу ЛП к стандартной форме

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

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

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

1.4. Графический метод решения задач

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

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

Рассмотрим
задачу:

(1.9)

(1.10)

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

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

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

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

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

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

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

,
(1.11)

где c – сonst.

Все линии уровня
параллельны между собой.

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

Область D имеет не более двух опорных прямых
(см. рис.1.2,а,б).

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

Вектор градиента целевой функции

является
вектором нормали любой прямой

(линии уровня целевой функции).

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

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

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

1. Строим многоугольник решений системы ограничений.

2. Строим некоторую линию
уровня для выбранного значения с () и нормаль линии
уровня .

3. Перемещаем линию уровня в задаче на
максимум в направлении вектора нормали, в задаче на минимум — в противоположном направлении до положения опорной прямой.

4. Находим точки пересечения опорной прямой и многоугольника
решений системы ограничений.

Задача может
иметь единственное решение (рис. 1.3, а, точка A), бесконечное множество решений (рис. 1.3, б, точки отрезка AB) или не иметь ни одного (рис. 1.3,
в).

Пример 1.3.
Решить графически задачу ЛП.

Решение.
Строим многоугольник решений системы
ограничений. Проводим прямую (1). Выбираем
полуплоскость, определяемую неравенством .
Для этого возьмем точку (0;0) и подставим ее координаты в левую часть
неравенства. Получим верное неравенство ,
следовательно, точка (0;0) лежит в полуплоскости решений. Аналогично строим прямые
(2), (3),
(4) и выбираем полуплоскости. В
результате получим многоугольник OABC (рис. 1.4). Строим одну из линий уровня, например , и вектор нормали к ней .

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

Решением задачи является
точка C – точка пересечения прямых и (рис.
1.4). Находим ее координаты, решая систему:

Источник

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

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

Будем рассматривать решение этой задачи на плоскости. Каждое неравенство системы функциональных ограничений геометрически определяет полуплоскость с граничной прямой а_пх, + + a_j2х₂ = b_n i = 1, т. Условия неотрицательности определяют полуплоскости с граничными прямыми х_<= 0, х₂ = 0 соответственно. Если система совместна, то полуплоскости, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек; координаты каждой из этих точек являются решением данной системы. Совокупность этих точек называют многоугольником решений. Он может быть точкой, отрезком, лучом, ограниченным и неограниченным многоугольником.

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

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

Определим, какую часть плоскости описывает неравенство 2х_<+ Зх₂ 0, j = 1, п). Координаты любой точки, принадлежащей области определения, являются допустимым решением задачи.

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

Этот вектор показывает направление наискорейшего изменения целевой функции. Прямая c_[x_l + с₂х₂ = f(x₀), перпендикулярная вектору-градиенту, является линией уровня целевой функции (рис. 2.2.2). В любой точке линии уровня целевая функция принимает одно и то же значение. Приравняем целевую функцию постоянной величине а. Меняя значение а, получим семейство параллельных прямых, каждая из которых является линией уровня целевой функции.

Рис. 2.2.2. Вектор-градиент и линии уровня

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

Графический метод решения ЗЛП состоит из четырех этапов:

1. Строится область допустимых решений (ОДР) ЗЛП.

2. Строится вектор-градиент целевой функции (ЦФ) с началом в точке х₀ (0; 0): V = (с,, с₂).

3. Линия уровня CjXj + с₂х₂ = а (а — постоянная величина) — прямая, перпендикулярная вектору-градиенту V, — передвигается в направлении вектора-градиента в случае максимизации целевой функции f(x_v х₂) до тех пор, пока не покинет пределов ОДР. При минимизации /(*,, х₂) линия уровня перемещается в направлении, противоположном вектору-градиенту. Крайняя точка (или точки) ОДР при этом движении и является точкой максимума (минимума) f(x_pjc₂).

Если прямая, соответствующая линии уровня, при своем движении не покидает ОДР, то минимума (максимума) функции f(xр х₂) не существует.

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

4. Определяются координаты точки максимума (минимума). Для этого достаточно решить систему уравнений прямых, дающих в пересечении точку максимума (минимума). Значение f(x_<, х₂), найденное в полученной точке, является максимальным (минимальным) значением целевой функции.

Возможные ситуации графического решения ЗЛП представлены в табл. 2.2.1.

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

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

Введение

Задача линейного программирования (ЗЛП) состоит в определении значений упорядоченной совокупности переменных x_j, j = 1(1)n при которых линейная целевая функция достигает экстремального значения и при этом выполняются (удовлетворяются) все ограничения (они также линейные) в форме равенств или неравенств. Требуется найти план Х = , который обеспечивает получение целевой функцией с экстремальным значением. Идеи моделей линейного планирования (программирования) впервые были высказаны и опубликованы советским математиком Л. В. Канторовичем в 1939 году в работе «математические методы организации и планирования производства». В 1975 году Л. В. Канторович и Т. Купманс получили Нобелевскую премию по экономическим наукам с формулировкой «за их вклад в теорию оптимального распределения ресурсов». В 1947 г. очень близкие идеи высказаны американским математиком Дж. Данцигом. А еще позднее стали массово появляться работы, посвященные проблемам выбора оптимальных решений в силу их исключительной важности. Признание приоритета за Л. В. Канторовичем не оспаривалось практически никогда, а после присуждения Нобелевской премии тем более.

Общая постановка задачи

Задача линейного программирования (ЗЛП) состоит в определении значений упорядоченной совокупности переменных x_j, j = 1(1)n при которых линейная целевая функция достигает экстремального значения и при этом выполняются (удовлетворяются) все ограничения в форме равенств или неравенств. Требуется найти план Х = , который обеспечивает получение целевой функцией экстремального значения

а) Если система ограничений ЗЛП обладает хотя бы одним решением, она называется совместной в противном случае несовместной; б) Допустимое множество решений ЗЛП не пусто, если система ограничений совместна; в) Множество допустимых решений ЗЛП (если оно не пусто) в общем случае является многогранным множеством. Линейная функция Q(X ) называется функцией цели, целевой функцией (ЦФ), множество планов <X > удовлетворяющих системе ограничений (2) – (5), - множеством допустимых решений (альтернатив) и обозначается символом R, X є Ω Допустимый план X є Ω, доставляющий целевой функции (1) экстремальное значение, называется оптимальным. Задача в форме (1) – (5) представляет общую задачу линейного программирования.

Cтандартная форма задачи

Если все ограничения задачи заданы в виде строгих равенств и на переменные величины наложено условие неотрицатаельности x_j ≥0, j = 1(1)n, то такую формулировку называют стандартной:

Экстремумы функций в общем случае связаны простыми соотношениями

Переход от общей задачи к стандартной

Для удобства применения методов решения выполняют преобразование исходной общей задачи. Ограничения неравенства преобразуют в равенства. Вводятся дополнительные переменные по числу неравенств, т. е. формулируют расширенную задачу x_n+1 ≥0, x_n+2 ≥0, . , x_n+k ≥0. Неравенства a_i1x₁+a_i2x₂+. +a_inx_n ≥b_i введением переменной x_n+1≥0 преобразуются в равенства a_i1x₁+a_i2x₂+. +a_inx_n + a_i(n+1)x_n+1=b_i. В ЦФ вновь введённые переменные имеют коэффициенты равные нулю c_n+1=c_n+2=. =c_n+k =0.

а) Если в исходной общей задаче на некоторые переменные x_j , j = 1(1)n, не наложено условие их неотрицательности, то каждую такую переменную представляют в виде разности положительных новых переменных x’_j — x»_j , где x’_j≥0 и x»_j≥0 , j>r . Способ устранения отрицательных переменных прост, но при этом размерность (число неотрицательных переменных) задачи возрастает. б) Имеется другой более сложный путь. Каждую x_j ≯ 0 выражают явно через другие, для которых условие x_j ≥0 выполняется. Затем найденные выражения подставляют в ограничения, чтобы исключить их из рассмотрения. При этом размерность задачи даже уменьшается.

Каноническая форма задачи

Удобство этой формы ЗЛП состоит в том, что она позволяет предельно просто получить первое допустимое решение. Для этой формы должны быть выполнены условия:

правые части в ограничениях – неотрицательны b_i ≥ 0, i = 1(1)m;

каждое уравнение содержит переменную x_j ≥0 с коэффициентом при ней равным “1” в этом уравнении и с коэффициентом “0” во всех других уравнениях; эти переменные называют дополнительными или искусственными;

в ЦФ эти переменные входят с коэффициентом “0”;

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

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

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

Геометрическая интерпретация ЗЛП

Будем рассматривать пример ЗЛП в производстве двух видов продукции на предприятии, использующем при этом четыре виды сырья (см. ранее эту задачу). Этот пример удобен для геометрической интерпретации тем, что пространство решений является двумерным (т. е. плоскость) и все элементы ЗЛП допускают наглядное представление (изображение) в трёхмерном пространстве. Начнём с рассмотрения системы неравенств (ограничений ЗЛП). Заметим, что каждое i-е неравенство в ограничениях ЗЛП определяет полуплоскость в системе координат х₁Ох₂ с граничной прямой a_i1x₁ + a_i2x₂ = b_i , i = 1(1)m.

Рисунок 1 — Примеры областей, рписывающих ограничения, задачи линейного программирования

Выпишем их и присвоим им имена

Область, формируемая полуплоскостями, может быть получена в виде замкнутого или разомкнутого (неограниченного) многогранника. Путём непосредственного построения границ (прямых) и выявления области пересечения полупространств выясним, является ли многогранное множество ограниченным и не пусто ли оно (рис.). Имеем на плоскости х₁ О х₂ многоугольник А Ո В Ո C Ո D Ո E Ո F . Он является выпуклым (всегда ли?), его граница образована отрезками прямых.

Целевая функция. Что можно сказать о линейной форме (ЦФ)? Это функция двух переменных x₁ и x2, её образ в трёхмерном пространстве – плоскость, проходящая через начало координат. Найдём частные производные ЦФ по х_j

Так как частная производная по переменной х_j представляет наибольшую скорость изменения функции Q в направлении этой оси, то вектор C = — это вектор наибольшего изменения ЦФ, вектор градиентного направления. Если значения Q зафиксировать Q =Q₁ = const , то уравнение ЦФ превращается в уравнение прямой c₁x₁ + c₂x₂= Q₁= const плоскости х₁О х₂

В трёхмерном пространстве это плоскость параллельная х₁О х₂ на высоте Q₁, в каждой точке которой значение ЦФ постоянно и равно Q₁. . На плоскости Q этой прямой соответствует линия параллельная плоскости х₁О х₂, которую называют линией уровня (плотницкий уровень) функции c₁x₁ + c₂x₂ . Изменяя Q, получим семейство линий уровня параллельных друг другу. Требованию задачи – поиску экстремума Q соответствует смещение точки по поверхности функции Q в направлении вектора C = от начала координат.

Ограничения ЗЛП не позволяют аргументам ЦФ Q(x1, x2) выходить за пределы многоугольной допустимой области. Другими словами, надо найти точку на плоскости Q наиболее удалённую от плоскости х₁О х₂ и проекция которой на х₁О х₂ лежит в области допустимых решений. Координаты x*₁, x*₂ найденной точки и определяют оптимальный план ЗЛП. Покажем, что семейство линий уровня (изолиний) перпендикулярно C , т. е. перпендикулярно прямой х₂ =с₂х₁/c₁. Из векторного анализа известно, что все линии уровня ЦФ Q перпендикулярны вектору градиенту ЦФ, вычисленному в некоторой точке

Таким образом, перемещаясь вдоль вектора C или по прямой х₂ =с₂х₁/c₁, легко построить линию уровня (она перпендикулярна х₂ = с₂х₁/c₁ ) и вычислить значение ЦФ Q для этой линии. Экстремум Q, очевидно, будет достигаться в положении касания линией уровня (её проекцией) границы множества допустимых решений. Такое касание может быть трёх типов: в вершине, по ребру, по грани многогранника. Этим типам касания соответствуют: единственное решение в вершине и бесконечное множество решений в других случаях. Область допустимых решений. Рассмотрим случаи ограниченной и неограниченной области допустимых решений. В последнем случае поиск экстремума Q может приводить к отсутствию решения, так как extr Q → ±∞ или существует опорная прямая линия, касающаяся неограниченного многогранника, и тогда решение существует.

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

Рисунок В — Область допустимых решений ЗЛП

Мы можем записать уравнение границы области D заданной неравенствами:

Основные понятия и теоремы линейной алгебры Важным понятием линейной алгебры является понятие линейного векторного пространства. Определение 2.1. Упорядоченная совокупность n действительных чисел называется n-мерным вектором. Определение 2.2. Совокупность всевозможных n-мерных векторов после введения в нее операций сложения и умножения на действительное число называется n-мерным линейным векторным пространством. Частными случаями линейных пространств являются прямая, плоскость, трехмерное пространство. Определение 2.3. Система векторов X₁, X₂, . X_n называется линейно зависимой, если существуют такие числа λ₁, λ₂, …, λ_n, не равные нулю одновременно, при которых имеет место равенство: λ₁X₁+ λ₂X₂ …+ λ_n X_n=0 , где все λ_i ≥0 и λ₁+ λ₂+ …+ λ_n =1. Если же это равенство возможно лишь в случае, когда все λ_i = 0 (i = 1(1)n) , то система векторов называется линейно независимой. Определение 2.4. Базисом n-мерного векторного пространства называется любая совокупность n линейно независимых векторов этого пространства. В двумерном пространстве за базис могут быть взяты любые два неколлинеарных вектора, в частности, е₁ = (1,0), е₂ = (0, 1). В трехмерном пространстве – любые три некомпланарных вектора, например, е₁ = (1,0,0), е₂ = (0,1,0), е₃ = (0,0,1).

Выпуклой линейной комбинацией точек X₁, X₂, . X_n называется линейная комбинация вида: X= λ₁X₁+ λ₂X₂ …+ λ_n X_n где все λ_i ≥0 и λ₁+ λ₂+ …+ λ_n =1. В частности, когда имеются две точки X₁ и X₂, то их выпуклая комбинация λX₁+(1- λ)X₂, λ ∈[0,1] представляет собой точку на отрезке, соединяющем эти точки.

Теорема 1. Любой вектор n-мерного векторного пространства можно представить, как линейную комбинацию векторов базиса, притом единственным образом. Определение 2.5. Максимальное число линейно независимых векторов линейного пространства называется размерностью линейного пространства. Линейное пространство обычно обозначают, R_n где n – его размерность. Выпуклой оболочкой точек называется множество всевозможных выпуклых комбинаций этих точек. Множество называется выпуклым, если вместе с двумя любыми его точками оно содержит и их произвольную выпуклую линейную комбинацию. С геометрической точки зрения это означает, что выпуклое множество содержит вместе с любыми двумя своими точками и соединяющий их отрезок. Выпуклое множество совпадает со своей выпуклой оболочкой. Примерами выпуклых множеств являются прямолинейный отрезок, квадрат, круг, прямая, полуплоскость, куб, шар, полупространство и другие. Угловыми точками выпуклого множества называются точки, не являющиеся выпуклой линейной комбинацией двух произвольных точек множества. Например, угловыми точками треугольника являются его вершины, угловыми точками круга – точки окружности. Таким образом, выпуклое множество может иметь конечное или бесконечное число угловых точек, но может не иметь их совсем. Например, прямая, плоскость, полуплоскость, пространство, полупространство угловых точек не имеют. Одним из основных понятий теории линейного программирования является понятие выпуклого многогранника в n-мерном пространстве, частными случаями которого являются при n = 1 отрезок на прямой, при n = 2 выпуклый многоугольник на плоскости. Выпуклым многоугольником называется выпуклое замкнутое ограниченное множество точек на плоскости, имеющее конечное число угловых точек, называемых вершинами. Прямолинейные отрезки, соединяющие две вершины и образующие границу, называются сторонами многоугольника.

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

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

Теорема 2.2. Выпуклый n-мерный многогранник является выпуклой линейной комбинацией своих угловых точек.

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

Элементы выпуклых множеств

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

Определение 2. е — о к р е с т н о с т ь ю точки х называется множество всех точек, расстояние которых до точки х меньше е.

Определение 3. Точка х₁ называется внутренней точкой множества M, если существует такая — окрестность данной точки, все точки которой принадлежат множеству M.

Определение 4. Точка х₂ называется в н е ш н е й т о ч к о й м н о ж е с т в а M, если существует такая — окрестность данной точки, все точки которой не принадлежат множеству М.

Определение 5. Точка х₃ называется г р а н и ч н о й т о ч к о й м н о ж е с т в а M, если в любой её — окрестности существуют точки как принадлежащие множеству M, так и не принадлежащие этому множеству.

Определение 6. Множество М называется з а м к н у т ы м, если оно содержит все свои граничные точки. х 2— незамкнутое множество, Пример. х 2 — замкнутое множество.

Определение 7. Множество М называется в ы п у к л ы м, если вместе с любыми двумя точками, принадлежащими данному множеству, оно содержит и отрезок их соединяющий. В общей форме ЗЛП каждый символ R1, R2, …, Rm означает один из знаков: = или ≠. В такой форме задачи линейного программирования часть переменных может быть подчинена условию неотрицательности (x_i ≥ 0), часть – условию неположительности (x_j ≤ 0), а какие-то переменные, возможно, могут принимать любые значения.

Общий алгоритм симплексного метода ЗЛП

Пусть система невырожденна и совместна, т.е. r_A = r_B = r = m

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

Алгоритм решения

1) Формируем исходный план при свободных переменных; x_j =0, j = m+1(1)n, x_j = β_ф, ф = 1(1)m при β_ф > 0 план x o допустим Q(x) =x_o.

2) Проверяем этот план на оптимальность, используя значения γ_j коэффициентов ЦФ в последней строке таблицы. Могут быть два случая:

а) все γ_j ≤0, j = m+1(1)n , при этом увеличение никакой переменной (из свободных) не приведёт к уменьшению ЦФ Q, т. е. план x o улучшить нельзя, и он уже оптимален, таким образом, условием оптимальности плана является – отсутствие в таблице γ_j >0.

б) некоторые γ_j > 0. В этом случае увеличение значений соответствующих свободных переменных x_j (γ_j > 0) будет минимизировать Q, так как

Чтобы Q уменьшалось, такие переменные следует вводить (последовательно) в базис, но, чтобы размерность пространства не изменялась из базиса должны выводиться переменные в число свободных (по одной) формируем множество индексов Г = < j | γ_j >0>. Какая переменная должна первой вводиться в базис? Вообще последовательно перебирая (вершины симплекса) решение отыскивается при произвольном выборе, но для определённости выбираем новую базисную переменную с индексом v = argmax <x_j>, где j ∈ Г. Теперь определим переменную (базисную), которая будет выводиться из базиса.

В системе уравнений

Начинаем увеличивать х_v до тех пор, пока некоторый х_ф станет отрицательным. Первый же х_ф ≤ 0 будет выводиться из базиса. Определение. Столбец с индексом v и строка с индексом ф = i называются направляющими.

3) Проверка существования решения (ограниченность ЗЛП). В выражениях, связывающих х, ∝, β, х_ф = β_ф -∝_фvх_v, ф=1(1)m, могут быть все ∝_фv 0. Пусть ЦФ ограничена и некоторые ∝_фv > 0. Сформируем множество индексов S = < ф | ∝_фv >0>. Из базиса необходимо выводить переменную с индексом i, так как она первая обращается в нуль, i = argmin(β_ф/∝_фv), где ф∈S, таким образом, базисная переменная x_i выводится из базиса.

Определение. Коэффициент ∝_фv=∝_iv , стоящий на пересечении направляющих строки и столбца называется направляющим (разрешающим, генеральным) элементом таблицы.

4) Формируем новые множества:

Дальнейшие действия алгоритма:

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

заполняем новую симплексную таблицу;

делаем все свободные переменные х_j = 0 и находим опорный план;

Опорный план (вектор) такой Х’ = ; Q(Х’ ) ≤ Q₀ ;

если план не оптимален, то определяем направляющий столбец;

проверяем существует ли оптимальный план;

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

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

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

Рисунок С — Структурная схема алгоритма симплекс-метода

При решении задач линейного программирования вычисляются ранги у матрицы ограничений и расширенной матрицы ранги должны быть равны r=m.

Матрица и её ранг. Система mn чисел, расположенных в форме прямоугольной таблицы из m строк и n столбцов, называется матрицей.

Определение. Рангом матрицы [A] называется наибольший порядок, который могут иметь её миноры, не обращающиеся в нуль. Для определения ранга матрицы следует рассмотреть все её миноры порядка р (где р – меньшее из чисел m, n, если m ≠ n или р = m = n); если хотя бы один из них ≠ 0, то ранг [A] равен р; если же все они равны (= 0), то следует рассмотреть все миноры порядка р – 1 и т. д. Практически поступают наоборот: переходят от миноров меньшего порядка к минорам большего порядка, в соответствии со следующим правилом. Если найден минор k-го порядка D_k, отличный от нуля, то остается вычислить только те миноры (k + 1) -го порядка, которые представляют собой «окаймление» D_k, например,

Определение. Минором k-го порядка матрицы [A] (k ≤ m, k ≤ n) называется определитель D, составленный (с сохранением порядка) из k 2 элементов матрицы, лежащих на пересечении некоторых её k столбцов и k строк См. схему выше минор D из 3-х строк и 3-х столбцов. Обозначается матрица символами:

Матрица А и ее миноры с различным окаймлением

Приведем пример вычисления ранга матрицы.

С выполнением каждого шага связаны процедуры:

1. Получение опорного плана; 2. устанавливается, является ли данный опорный план оптимальным; 3. если нет, то существует ли оптимальный план вообще, или задача является неограниченной; 4. если оптимальный план существует, то, как перейти на следующем шаге, к новому опорному плану с меньшим значением ЦФ.

Алгоритм СМ применяется к ЗЛП после её приведения к канонической форме, т.е. отыскивается минимум целевой функции min Q(X) на множестве векторов Х .

Система ограничений совместна r_A = r_B и detA ≠ 0 невырожденная, т.е. ранг r =m матрицы A_{[m, n]} и расширенной матрицы системы равен m. Имеется множество решений. Для решения системы произвольным (n — m) переменным могут быть приданы любые, в частности, нулевые значения. Эти переменные называются свободными. Обычно их индексируют x_e, e =(m+1)(1)n. Остальные переменные (их называют базисными), однозначно определяются из решения системы

(здесь x_e, e =(m+1)(1)n). Матрица этой системы неособенная и, следовательно, система имеет единственное решение x_j , j =1(1)m.

Исходный опорный план ЗЛП – вектор, содержащий значения всех переменных задачи как базисных, так и свободных, т.е. этот вектор Х , удовлетворяет ограничениям, но не обеспечивает, как правило, экстремума ЦФ. Общее число опорных планов очевидно равно числу сочетаний из n по m. Оптимальный план можно выявить, перебрав их все. Такой путь громоздок и неприемлем уже при n, m ≈ 10 ÷15.

Алгоритм СМ тоже перебирает опорные планы, но не все, а направленно, т.е. на каждом шаге ЦФ уменьшается. Число шагов имеет тот же порядок, что и число уравнений в ограничениях.

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

Определение. Системой линейных уравнений называют систему следующего вида. Ранг матрицы определяется через миноры r = – 5.

Решение системы уравнений. Решаем относительно переменных x и y, полагаем z = 1. Получаем единственное решение х = –2/5, y = 3/5, z =1. Все другие решения получаются из этого линейно-независимого фундаментального решения: х = –2k/5; y = 3k/5; z = k или х = 2k , y = 3k, z = 5k. Подобные системы возникают при описании ограничений ЗЛП. Существенную роль при решении ЗЛП играют определители подобных систем (Δ = 0, Δ ≠ 0). При однородной системе определитель должен быть равен нулю.

Определение. Симплекс – выпуклый многоугольник в n-мерном пространстве с n + 1 вершинами, не лежащими в одной гиперплоскости. Симплексы выделены в отдельный класс потому, что в n-мерном пространстве n точек всегда лежат в одной гиперплоскости. Другими словами, симплекс – это простейший многоугольник, содержащий некоторый объем n-мерного пространства. В обычном (трехмерном) пространстве симплекс – это тетраэдр; трехмерный объем совпадает с объемом тела. На плоскости симплекс – это треугольник, двумерный объем – площадь; на прямой – симплекс – отрезок, объем – длина отрезка.

Определение. Гиперпространство, гиперплоскость. Гиперпространство многомерного (n-мерного) пространства – это его подпространство размерности (n – 1). Главное свойство гиперпространства – то, что оно «самое большое» подпространство. Иначе говоря, если к базису выбранного гиперпространства добавить еще один линейно независимый вектор, то можно получить базис всего пространства.

Например, для трехмерного пространства гиперпространством является плоскость (любая), проходящая через начало координат. Для двумерного пространства – гиперпространство – это прямая линия, проходящая через нуль.

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

Гиперплоскость определяется линейной формой: а₁х₁ + а₂х₂ + … + а_nx_n = k, где коэффициенты (а₁, а₂, …, а_n) представляют собой координаты вектора А.

Гиперплоскость делит пространство (соответствующей размерности) на два полупространства. Все точки каждого из них определяются неравенствами. Например, в случае прямой линии на плоскости: а₁х₁ + а₂х₂ ≥_Z, или а₁х₁ + а₂х₂ >Z _, а₁х₁ + а₂х₂ Литература

Ваулин А. Е. Методы цифровой обработки данных.– СПб.: ВИККИ им. А. Ф. Можайского, 1993.– 106 с.

Гэри М., Джонсон Д. Вычислительные машины и трудно решаемые задачи. М.: Мир, 1982.

Корбут А.А., Финкельштейн Ю. Ю. Дискретное программирование М. Наука. Гл. ред. физ.-мат. лит. 1969.

Макаров И. М. и др. Теория выбора и принятия решений.– М.: Наука, 1982.– 328 с.

Пфанцагль И. Теория измерений. – М.: Наука, 1988.–384 с.

Таха Х. А. Введение в исследование операций. 7-е изд. М.: Изд. дом «Вильямс», 2005.

Фишберн П. С. Теория полезности для принятия решений. – М.: Наука,1978. –352 с.

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

Описание метода

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

Рассмотрим задачу линейного программирования с двумя переменными и :
(1.1) ;
(1.2)
Здесь , есть произвольные числа. Задача может быть как на нахождение максимума (max), так и на нахождение минимума (min). В системе ограничений могут присутствовать как знаки , так и знаки .

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

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

Так, первое неравенство
(1.2.1)
определяет полуплоскость, ограниченную прямой . С одной стороны от этой прямой , а с другой стороны . На самой прямой . Чтобы узнать, с какой стороны выполняется неравенство (1.2.1), мы выбираем произвольную точку, не лежащую на прямой. Далее подставляем координаты этой точки в (1.2.1). Если неравенство выполняется, то полуплоскость содержит выбранную точку. Если неравенство не выполняется, то полуплоскость расположена с другой стороны (не содержит выбранную точку). Заштриховываем полуплоскость, для которой выполняется неравенство (1.2.1).

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

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

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

Если хотя бы одно неравенство не выполняется, то выбираем другую точку. И так далее, пока не будет найдены одна точка, координаты которой удовлетворяют системе (1.2).

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

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

Теперь мы можем искать экстремум целевой функции
(1.1) .

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

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

Если ОДР неограниченна, то может возникнуть случай, когда такую прямую провести нельзя. То есть как бы мы ни удаляли прямую от линии уровня (3) в сторону возрастания (убывания) , то прямая всегда будет проходить через ОДР. В этом случае может быть сколь угодно большим (малым). Поэтому максимального (минимального) значения нет. Задача решений не имеет.

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

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

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

Фирма выпускает платья двух моделей А и В. При этом используется ткань трех видов. На изготовление одного платья модели А требуется 2 м ткани первого вида, 1 м ткани второго вида, 2 м ткани третьего вида. На изготовление одного платья модели В требуется 3 м ткани первого вида, 1 м ткани второго вида, 2 м ткани третьего вида. Запасы ткани первого вида составляют 21 м, второго вида — 10 м, третьего вида — 16 м. Выпуск одного изделия типа А приносит доход 400 ден. ед., одного изделия типа В — 300 ден. ед.

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

Пусть переменные и означают количество произведенных платьев моделей А и В, соответственно. Тогда количество израсходованной ткани первого вида составит:
(м)
Количество израсходованной ткани второго вида составит:
(м)
Количество израсходованной ткани третьего вида составит:
(м)
Поскольку произведенное количество платьев не может быть отрицательным, то
и .
Доход от произведенных платьев составит:
(ден. ед.)

Тогда экономико-математическая модель задачи имеет вид:

Решаем графическим методом.
Проводим оси координат и .

Строим прямую .
При .
При .
Проводим прямую через точки (0; 7) и (10,5; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (0; 10) и (10; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (0; и (8; 0).

Прямые и являются осями координат.

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

Заштриховываем область, чтобы точка (2; 2) попала в заштрихованную часть. Получаем четырехугольник OABC.

Строим произвольную линию уровня целевой функции, например,
(П1.1) .
При .
При .
Проводим прямую через точки (0; 4) и (3; 0).

Далее замечаем, что поскольку коэффициенты при и целевой функции положительны (400 и 300), то она возрастает при увеличении и . Проводим прямую, параллельную прямой (П1.1), максимально удаленную от нее в сторону возрастания , и проходящую хотя бы через одну точку четырехугольника OABC. Такая прямая проходит через точку C. Из построения определяем ее координаты.
.

.
То есть, для получения наибольшего дохода, необходимо изготовить 8 платьев модели А. Доход при этом составит 3200 ден. ед.

Пример 2

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

Решаем графическим методом.
Проводим оси координат и .

Строим прямую .
При .
При .
Проводим прямую через точки (0; 6) и (6; 0).

Строим прямую .
Отсюда .
При .
При .
Проводим прямую через точки (3; 0) и (7; 2).

Строим прямую .
Строим прямую (ось абсцисс).

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

Заштриховываем область по границам построенных прямых, чтобы точка (4; 1) попала в заштрихованную часть. Получаем треугольник ABC.

Строим произвольную линию уровня целевой функции, например,
.
При .
При .
Проводим прямую линию уровня через точки (0; 6) и (4; 0).
Поскольку целевая функция увеличивается при увеличении и , то проводим прямую, параллельную линии уровня и максимально удаленную от нее в сторону возрастания , и проходящую хотя бы через одну точку треугольника АВC. Такая прямая проходит через точку C. Из построения определяем ее координаты.
.

Пример отсутствия решения

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

Решаем задачу графическим методом.
Проводим оси координат и .

Строим прямую .
При .
При .
Проводим прямую через точки (0; и (2,667; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (0; 3) и (6; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (3; 0) и (6; 3).

Прямые и являются осями координат.

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

Заштриховываем область, чтобы точка (3; 3) попала в заштрихованную часть. Получаем неограниченную область, ограниченную ломаной ABCDE.

Строим произвольную линию уровня целевой функции, например,
(П3.1) .
При .
При .
Проводим прямую через точки (0; 7) и (7; 0).
Поскольку коэффициенты при и положительны, то возрастает при увеличении и .

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

Ищем минимум. Проводим прямую, параллельную прямой (П3.1) и максимально удаленную от нее в сторону убывания , и проходящую хотя бы через одну точку области ABCDE. Такая прямая проходит через точку C. Из построения определяем ее координаты.
.
Минимальное значение целевой функции:

Максимального значения не существует.
Минимальное значение
.

Автор: Олег Одинцов . Опубликовано: 08-08-2016

источники:

http://habr.com/ru/post/565068/

http://1cov-edu.ru/lineynoe-programmirovanie/graficheskiy-metod/

Источник

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

Условие

Сначала запишем условие производственной задачи из предыдущей главы:

Ресурс	Изделие A	Изделие B	Сколько ресурса на складах
R1	1	3	15
R2	2	1	20
R3	3	2	35
Прибыль	5	10

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

$$begin{array}{l}
left{ {begin{array}{*{20}{c}}
{{x_A} + 3{x_B} le 15}\
{2{x_A} + {x_B} le 20}\
{3{x_A} + 2{x_B} le 35}
end{array}} right.\
{x_A},{x_B} ge 0\
F({x_A},{x_B}) = 5{x_A} + 10{x_B} to max
end{array}$$

Понравилось? Добавьте в закладки

Строим область допустимых решений

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

$$left{ {begin{array}{*{20}{c}}
{{x_A} + 3{x_B} = 15}\
{2{x_A} + {x_B} = 20}\
{3{x_A} + 2{x_B} = 35}\
{{x_A} = 0}\
{{x_B} = 0}
end{array}} right.$$

Мы получили пять уравнений с двумя переменными, следовательно, мы можем построить
их графики. Например, мы можем направить ось с переменной $x_A$ вправо (где обычно у нас
ось абсцисс) и ось с переменной $x_B$ вверх (где обычно у нас ось ординат). Для построения
графиков нужно лишь выразить из этих уравнений $x_B$. Сделаем это:

$$left{ {begin{array}{*{20}{c}}
{3{x_B} = 15 — {x_A}}\
{{x_B} = 20 — 2{x_A}}\
{2{x_B} = 35 — 3{x_A}}\
{{x_A} = 0}\
{{x_B} = 0}
end{array}} right.$$

$$left{ {begin{array}{*{20}{c}}
{{x_B} = 5 — frac{1}{3}{x_A}}\
{{x_B} = 20 — 2{x_A}}\
{{x_B} = 17,5 — 1,5{x_A}}\
{{x_A} = 0}\
{{x_B} = 0}
end{array}} right.$$

Прежде чем строить графики, разберемся с последними двумя уравнениями, $x_A=0$ и
$x_B=0$. Эти уравнения выражают сами оси — абсцисс и ординат. А так как в исходных
ограничениях были неравенства $x_Ageq0$ и $x_Bgeq0$, то точка нашего решения должна
быть правее и выше, чем эти оси — то есть, находиться в первой четверти. Поэтому эти
две линии можно не строить, а просто учитывать, что решение в первой четверти.

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

Каждая из этих линий разбивает область допустимых решений на две — одна находится
правее и выше каждой из этих линий, вторая — левее и ниже. Какая из них нужна нам?
Та, которая левее и ниже. Во-первых, в исходных неравенствах у нас был знак «меньше
или равно», а левее и ниже как раз более маленькие значения переменных. А во-вторых,
как мы говорили в предыдущем пункте, решение (0,0) вполне удовлетворяет условию задачи,
хоть и не является оптимальным. А точка (0,0) — начало координат — расположена как
раз левее и ниже каждой из прямых.

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

Эта область, во-первых, расположена в первой четверти, как и должно быть, во-вторых,
левее и ниже прямых $x_B=5-frac{1}{3}x_A$ и $x_B=20-2x_A$. Прямая $x_B=17,5-1,5x_A$
оказалась не участвующей в решении, так иногда бывает, это не страшно.

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

Основной способ

Рассмотрим первый из них. Для него
нужно нарисовать линию нулевого дохода, то есть, линию, при которой целевая функция
равна нулю: $5x_A+10x_B=0$. Если упростить данное выражение, получим $x_B=-0,5x_A$.
Построим эту функцию красным цветом, и уберем подписи. Она будет расположена не в первой
четверти, это нормально.

Эта линия состоит из точек, каждая из которых является решением, применяя которое, мы
получим нулевой доход. Однако с тем условием, что $x_A,x_Bgeq0$, такое решение мы получаем
всего одно — в точке (0,0) — остальные точки лежат во второй и четвертой четверти.

Что будет, если эту линию поднимать выше (параллельным переносом)? Мы получим линии,
которые будут давать больший, чем 0 доход. Получается, чем выше мы поднимем данную линию,
тем лучше. Однако совсем до бесконечности поднимать ее не получится, ведь она должна
хотя бы касаться разрешенной области, обозначенной серым цветом (сейчас она касается только
в точке (0,0)). Попробуем провести (пока на глаз) линии, параллельные данной, через
оставшиеся три точки многоугольника:

Мы нарисовали еще две линии, параллельные линии нулевого дохода, но расположенные выше.
Средняя из них проходит через две точки нашего многоугольника с решениями, а самая высокая —
через еще одну точку многоугольника. Кроме того, она вообще пересекает наш многоугольник
в одной-единственной точке. И еще выше данную линию поднять нельзя — она вообще перестанет
пересекать наш многоугольник. Следовательно, эта линия и есть «линия максимального дохода»,
а наше решение находится, как раз, в той точке, в которой эта линия пересекает нашу область
допустимых решений — в точке пересечения линий $x_B=5-frac{1}{3}x_A$ и $x_B=20-2x_A$.
Найдем координаты данной точки. Для этого приравняем эти два значения для $x_B$:

$$5-frac{1}{3}x_A=20-2x_A$$
$$-frac{1}{3}x_A+2x_A=20-5$$
$$frac{5}{3}x_A=15$$
$$5x_A=45$$
$$x_A=9$$
$$x_B=20-2cdot9=20-18=2$$

Итак, наше решение находится в точке (9,2). Это означает, что необходимо производить
9 единиц изделия A и 2 единицы изделия B. При этом мы получим прибыль

$$F(x_A,x_B)=5cdot9+10cdot2=45+20=65$$

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

Другой способ

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

Найдем координаты каждой из них. Координаты точки O мы знаем — (0,0). Координаты
точки B мы нашли выше (по первому способу) — (9,2). Точка A — это точка на прямой
$x_B=5-frac{1}{3}x_A$, причем $x_A=0$. Следовательно $x_B=5$. То есть, ее координаты
(0,5). Точка C — это точка на прямой $x_B=20-2x_A$, причем $x_B=0$. То есть,
$20-2x_A=0$, $2x_A=20$, $x_A=10$. Следовательно, ее координаты (10,0).

Теперь найдем значение целевой функции в каждой из данных точек:

$$F(O)=F(0,0)=5cdot0+10cdot0=0+0=0$$
$$F(A)=F(0,5)=5cdot0+10cdot5=0+50=50$$
$$F(B)=F(9,2)=5cdot9+10cdot2=45+20=65$$
$$F(C)=F(10,0)=5cdot10+10cdot0=50+0=50$$

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

А если товаров больше?

Как говорилось в предыдущем разделе, графическим способом можно решать только задачу
для двух производимых товаров. Это потому, что если товаров будет больше двух, то и
переменных будет больше двух, например, три — $x_A, x_B, x_C$. И тогда придется строить
трехмерный график, в котором запросто можно запутаться. А если переменных больше трех,
то график не построить вообще. Однако специально для этих случаев был разработан еще
один метод решения задач линейного программирования, и, в частности, производственной
задачи — симплекс-метод, который мы рассмотрим в следующей главе.

Далее: 2.1.1. Симплексный способ решения

Полезное по теме

Примеры решений задач ЛП графическим способом
Решенные контрольные по линейному программированию
Заказать свою работу по ЛП

Источник