Алгоритм графического метода решения ЗЛП с двумя переменными
1) Построить область допустимых решений.
2) Если область допустимых решений является пустым множеством, то задача не имеет решения вследствие несовместности системы ограничений.
3) Если область допустимых решений является непустым множеством, построить вектор-градиент целевой функции.
4) Произвольную линию уровня, имеющую общие точки с ОДР, перемещаем параллельно самой себе до опорной прямой в направлении вектора-градиента (при решении задачи на 
) или в противоположном направлении (при решении задачи на 
).
5) Если при перемещении линии уровня по ОДР в направлении, соответствующем приближению к экстремуму целевой функции, линия уровня уходит в бесконечность, то задача не имеет решения вследствие неограниченности целевой функции.
6) Если ЗЛП имеет оптимальное решение, то для его нахождения решить совместно уравнения прямых, ограничивающих ОДР и имеющих общие точки с соответствующей опорной прямой. Если целевая функция задачи достигает экстремума в двух вершинах ОДР, то она достигает экстремума также в любой точке, лежащей на отрезке, соединяющем эти две вершины. Задача имеет бесконечное множество оптимальных решений.
7) Вычислить значение целевой функции на оптимальном решении.
Пример 1.6
Решим графически ЗЛП, математическая модель которой составлена в примере 1.3.
;
Вначале построим ОДР задачи (рис. 1.2). Для этого в системе координат 
на плоскости изобразим граничные прямые:
|
|
|
Затем определим, какую полуплоскость определяет соответствующее неравенство, подставив координаты какой-нибудь точки, не лежащей на данной прямой, например (0;0). Ограничения (1.17) означают, что ОДР лежит в I четверти системы координат 
. Соответствующие полуплоскости на рисунке показаны стрелками. Пересечение указанных полуплоскостей и определяет ОДР данной задачи.
Строим вектор-градиент целевой функции 
=(5;4).
Строим произвольную линию уровня, например 
, проходящую через начало координат и перемещаем ее параллельно самой себе в направлении вектора 
по ОДР (рис. 1.2). Последняя точка соприкосновения прямой 
с ОДР и есть оптимальное решение – это точка С.
Точка 
лежит на пересечении прямых 
и 
. Для определения ее координат необходимо решить систему уравнений:
Рис. 1.2
Откуда 
. Таким образом, 
. Подставив значение 
и 
в целевую функцию Z, получаем:
.
Таким образом, для того, чтобы получить максимальную прибыль в размере 56 ден. ед., необходимо запланировать выпуск 8 ед. продукции вида П1 и 4 ед. продукции П2.
Пример 1.7
Графическим методом решить ЗЛП:
Решение
Вначале построим ОДР задачи (рис. 1.3). Для этого в системе координат 
на плоскости изобразим граничные прямые:
|
|
|
Затем определим, какую полуплоскость определяет соответствующее неравенство, подставив координаты какой-нибудь точки, не лежащей на этой прямой. Ограничения 
означают, что ОДР лежит в I четверти системы координат . Соответствующие полуплоскости на рисунке показаны стрелками. Пересечение указанных полуплоскостей и определяет ОДР данной задачи – это открытая многоугольная область ABCD.
Строим вектор-градиент целевой функции 
=(3;6). Берем произвольную линию уровня целевой функции (на рисунке она обозначена пунктирной линией) и перемещаем ее в направлении вектора-градиента до последней точки соприкосновения с ОДР для определения оптимального решения на 
, при этом линия уровня уходит в бесконечность, следовательно, на задача не имеет решения вследствие неограниченности целевой функции. Затем перемещаем линию уровня в направлении, противоположном вектору-градиенту до последней точки соприкосновения с ОДР для определения оптимального решения на 
. Оптимальным решением на 
является точка В, которая лежит на пересечении прямых 
и 
. Для определения ее координат необходимо решить систему уравнений: 
|
|
|
Откуда 
. Таким образом, 
. Подставив значение 
и в целевую функцию Z, получаем:
.
Рис. 1.3
Ответ: 
.
Пример 1.8
Графическим методом решить ЗЛП:
Решение
Вначале построим ОДР задачи (рис. 1.4). Для этого в системе координат 
на плоскости изобразим граничные прямые:
Рис. 1.4
Затем определим, какую полуплоскость определяет соответствующее неравенство, подставив координаты какой-нибудь точки, не лежащей на этой прямой. Ограничение-равенство – это есть сама граничная прямая. Ограничения 
означают, что ОДР лежит в I четверти системы координат 
. Соответствующие полуплоскости на рисунке показаны стрелками. Пересечение указанных полуплоскостей и прямой 
определяет ОДР данной задачи – это отрезок AB.
Строим вектор-градиент целевой функции 
=(–2;–3). Берем произвольную линию уровня целевой функции (на рисунке она обозначена пунктирной линией) и перемещаем ее в направлении вектора-градиента до последней точки соприкосновения с ОДР для определения оптимального решения на 
, это есть точка А. Она лежит на пересечении прямых и 
. Для определения ее координат необходимо решить систему уравнений: 
Откуда 
. Таким образом, 
. Подставив значение 
и 
в целевую функцию Z, получаем:
|
|
|
.
Затем перемещаем линию уровня в направлении, противоположном вектору-градиенту до последней точки соприкосновения с ОДР для определения оптимального решения на 
. Оптимальным решением на является точка В, которая лежит на пересечении прямых и 
. Для определения ее координат необходимо решить систему уравнений: 
Откуда 
. Таким образом, 
. Подставив значение 
и 
в целевую функцию Z, получаем:
.
Ответ: 
, 
; 
, 
.
Пример 1.9
Графическим методом решить ЗЛП:
Решение
Вначале построим ОДР задачи (рис. 1.5). Для этого в системе координат на плоскости изобразим граничные прямые:
Затем определим, какую полуплоскость определяет соответствующее неравенство, подставив координаты какой-нибудь точки, не лежащей на этой прямой. Ограничения 
означают, что ОДР лежит в I четверти системы координат . Соответствующие полуплоскости на рисунке показаны стрелками. Указанные полуплоскости не имеют ни одной общей точки, следовательно, ОДР – пустое множество и задача не имеет решения вследствие несовместности системы ограничений.
Рис. 1.5
Пример 1.10
Графическим методом решить ЗЛП:
Решение
Вначале построим ОДР задачи (рис. 1.6). Для этого в системе координат 
на плоскости изобразим граничные прямые:
Затем определим, какую полуплоскость определяет соответствующее неравенство, подставив координаты какой-нибудь точки, не лежащей на этой прямой. Ограничения означают, что ОДР лежит в I четверти системы координат . Соответствующие полуплоскости на рисунке показаны стрелками. Пересечение указанных полуплоскостей и определяет ОДР данной задачи – это открытая многоугольная область ABCD.
Строим вектор-градиент целевой функции =(0;–3). Берем произвольную линию уровня целевой функции (на рисунке она обозначена пунктирной линией) и перемещаем ее в направлении вектора-градиента до последней точки соприкосновения с ОДР для определения оптимального решения на . Такой точкой является любая точка луча CD. Следовательно, на задача имеет бесконечное множество решений – это луч CD. Для нахождения значения целевой функции на этих решениях, найдем координаты любой точки этого луча. Так, например, возьмем С(4;0) и 
.
Затем перемещаем линию уровня в направлении, противоположном вектору-градиенту, при этом линия уровня уходит в бесконечность, следовательно, на 
задача не имеет решения вследствие неограниченности целевой функции.
Рис. 1.6
Ответ: Оптимальные решения на 
– луч CD, 
.
Задачи
Решить ЗЛП графическим методом (1.3.1 – 1.3.12)
1.3.1
а)
 ;
в)
 ;
д)
;
ж)
;
и)
;
л)
;
н)
 ;
1.3.2
а)
 ;
в)
;
д)
ж)
1.3.3
а)
 ;
в)
 ;
д)
 ;
1.3.4
 ;
1.3.6
 ;
1.3.8
 ;
1.3.10
 ;
1.3.12
 ;
|
б)
 ;
г)
;
е)
;
з)
;
к)
;
м)
;
о)
 ;
б)
 ;
г)
 ;
е)
з)
б)
 ;
г)
 ;
е)
 ;
1.3.5
 ;
1.3.7
 ;
1.3.9
 ;
1.3.11
 ;
1.3.13
 ;
|
1.3.14 – 1.3.16
Решить задачи 1.1.1 – 1.1.3 (соответственно) графическим методом.
1.4. Графический метод решения задач линейного программирования с n переменными
Графическим методом решаются ЗЛП, если в ее канонической форме записи число переменных 
и число линейно независимых уравнений 
связаны соотношением 
.
Алгоритм графического метода решения ЗЛП со многими переменными ( n >2)
1) Записать каноническую форму ЗЛП.
2) Выбрать две свободные переменные.
3) Выразить все остальные переменные через свободные, т.е. решить систему ограничений заданной задачи.
4) Выразить целевую функцию через свободные переменные.
5) Полученную двухмерную задачу решить графическим методом.
6) Найдя координаты оптимального решения двухмерной задачи, определяем остальные координаты оптимального решения исходной задачи.
7) Значение целевой функции на оптимальном плане двухмерной задачи совпадает со значением целевой функции на оптимальном плане исходной задачи.
Пример 1.11
Решим графически ЗЛП, математическая модель которой составлена в примере 1.2.
;
Решение
Перейдем к эквивалентной задаче с двумя переменными.
Математическую модель задачи представим в канонической форме записи:
;
Пусть переменные 
и 
будут свободными, а все остальные переменные базисными. Выразим все базисные переменные через свободные.
Выразим целевую функцию через свободные переменные.
Учитывая условия неотрицательности базовых переменных, получим эквивалентную задачу с двумя переменными:
или 
Полученную двухмерную задачу решим графическим методом.
Построим ОДР задачи (Рис. 1.7). Для этого в системе координат 
на плоскости изобразим граничные прямые:
Затем определим, какую полуплоскость определяет соответствующее неравенство, подставив координаты какой-нибудь точки, не лежащей на данной прямой, например (0;0). Ограничения 
означают, что ОДР лежит в I четверти системы координат 
. Соответствующие полуплоскости на рисунке показаны стрелками. Пересечение указанных полуплоскостей и определяет ОДР данной задачи – это многоугольник ABCDE.
Рис. 1.7
Строим вектор-градиент целевой функции 
=(3;6).
Оптимальное решение достигается в точке E(3;0).
Перейдем к решению исходной задачи. Т.е. найдем значения базисных переменных:
Итак, решение исходной задачи: 
, 
.
Экономический смысл полученного решения задачи:
для того, чтобы затраты были минимальными и составили 52 усл. ден. ед. необходимо, чтобы оборудование А1 выпускало 3 часа продукцию P1, оборудование А2 выпускало 4 часа продукцию P1 и 6 часов продукцию P2.
Преобразовать ЗЛП к эквивалентной двумерной ЗЛП можно и не записывая исходную задачу в канонической форме. Достаточно из ограничений-равенств системы выразить базисные переменные через выбранные две свободные и подставить это выражение всюду, где они встречаются в ограничениях-неравенствах и в целевой функции. Учитывая условия неотрицательности базисных переменных двумерная модель будет иметь то же количество ограничений, что и исходная. Таким образом, графическим методом можно решить лишь ту ЗЛП с n переменными, система ограничений которой имеет не менее n–2 линейно-независимых ограничений-равенств.
Пример 1.12
Решим графически ЗЛП:
;
Решение
Перейдем к эквивалентной задаче с двумя переменными.
Пусть переменные 
и 
будут свободными, а все остальные переменные базисными. Выразим все базисные переменные через свободные. Сделаем это последовательно. Сначала выразим, например, из второго ограничения-равенства базисную переменную 
и подставим это выражение всюду, где она встречается в модели:
;
Раскрыв скобки, приведя подобные и учитывая условие неотрицательности переменной , получим следующую модель от трех переменных, эквивалентную исходной:
;
Затем выразим, например, из первого ограничения-равенства базисную переменную 
и подставим это выражение всюду, где она встречается в модели:
;
Раскрыв скобки, приведя подобные и учитывая условие неотрицательности переменной 
, получим следующую модель от двух переменных, эквивалентную исходной:
или 
Полученную двухмерную задачу решим графическим методом.
Построим ОДР задачи (Рис. 1.8). Для этого в системе координат 
на плоскости изобразим граничные прямые:
Затем определим, какую полуплоскость определяет соответствующее неравенство, подставив координаты какой-нибудь точки, не лежащей на данной прямой, например (0;0). Ограничения 
означают, что ОДР лежит в I четверти системы координат 
. Соответствующие полуплоскости на рисунке показаны стрелками. Пересечение указанных полуплоскостей и определяет ОДР данной задачи – это треугольник ABC.
Вектор-градиент целевой функции =(7,8;12,2). Так как нас интересует направление вектора-градиента, а не его длина, то можно изобразить вектор 
=(3,9;6,1)=0,5 
, который в два раза меньше вектора градиента.
Рис. 1.8
Оптимальное решение достигается в точке В, которая лежит на пересечении прямой 
и оси 
. Для определения ее координат необходимо решить систему уравнений: 
Откуда 
. Таким образом, 
. Подставив значение 
и 
в целевую функцию Z, получаем:
.
Перейдем к решению исходной задачи. Т.е. найдем значения базисных переменных:
,
.
Итак, решение исходной задачи: 
, 
.
Задачи
Решить ЗЛП графическим методом (1.4.1 – 1.4.8)
1.4.1
 ;
1.4.3
 ;
1.4.5
 ;
1.4.7
 ;
| 1.4.2
 ;
1.4.4
 ;
1.4.6
 ;
1.4.8
 ;
|
1.4.9 – 1.4.11
Решить задачи 1.1.4, 1.1.9, 1.1.11 (соответственно) графическим методом.
1.5. Симплексный метод решения задач линейного программирования
Симплексный метод основывается на следующем:
· ОДР ЗЛП является выпуклым множеством с конечным числом угловых точек, т.е. многогранником или многоугольным множеством;
· оптимальным решением ЗЛП является одна из угловых точек ОДР, если оптимальное решение единственно и не более двух угловых точек ОДР, если оптимальных решений бесконечное множество;
· угловые точки ОДР алгебраически представляют некоторые опорные решения системы ограничений задачи (опорные планы).
Данный метод состоит в целенаправленном переборе опорных решений ЗЛП. Он позволяет за конечное число шагов расчета либо найти оптимальное решение, либо установить его отсутствие.
Алгоритм решения ЗЛП симплексным методом
1) Привести ЗЛП к каноническому виду с неотрицательной правой частью.
2) Найти какой-либо начальный опорный план 
. Если опорный план отсутствует, то задача не имеет решения вследствие несовместности системы ограничений.
3) Проверить найденный план на оптимальность, используя оценки заполненной симплексной таблицы.
4) Если план оптимален, то задача решена.
5) Если план оптимален, но не единственен, то можно найти еще один оптимальный план.
6) Если план не оптимален, но имеет место условие неограниченности целевой функции, то задача не имеет решения.
7) Если пункты 4) – 6) алгоритма не выполняются, найти новый опорный план и перейти к пункту 3).
Нахождение начального опорного плана ЗЛП ( 
)
Пусть система ограничений ЗЛП представлена в канонической форме записи с неотрицательной правой частью.
.
Говорят, что ограничение ЗЛП имеет предпочтительный вид, если при неотрицательной правой части ( 
) левая часть ограничения содержит переменную, входящую с коэффициентом, равным единице, а в остальные ограничения-равенства – с коэффициентом, равным нулю.
Например, в системе ограничений:
первое и второе ограничения имеют предпочтительный вид, а третье – нет (предпочтительные переменные подчеркнуты).
Если каждое ограничение системы имеет предпочтительный вид, то система представлена в предпочтительном виде. В этом случае легко найти ее опорное решение. Предпочтительные переменные будут базисными, а остальные – свободными. Все свободные переменные нужно приравнять к нулю, тогда базисные переменные будут равны свободным членам.
Например, в системе ограничений:
предпочтительными (базисными) являются переменные 
, свободными являются переменные 
.
Приравниваем свободные переменные 
к нулю, тогда базисные переменные примут значения: 
, 
, 
.
Получим начальный опорный план 
.
В случае, когда в каноническом виде с неотрицательной правой частью система ограничений ЗЛП не имеет предпочтительного вида, то начальный опорный план можно найти методом искусственного базиса или методом Жордановых исключений.
Нахождение начального опорного плана ЗЛП методом искусственного базиса
В случае, когда ограничение-равенство системы не имеет предпочтительного вида, к его левой части добавляют искусственную переменную 
. В целевую функцию переменные 
вводят с коэффициентом «M» в случае решения задачи на минимум и с коэффициентом «–М» в случае решения задачи на максимум, где М – большое (по сравнению с остальными коэффициентами целевой функции) положительное число. Полученная задача называется М-задачей, соответствующей исходной. Она всегда имеет предпочтительный вид.
Пусть ЗЛП имеет каноническую форму записи с неотрицательной правой частью:
где 
.
Если ни одно из ограничений не имеет предпочтительной переменной, то М-задача запишется так:
Тогда начальный опорный план этой задачи: 
Если некоторое уравнение системы имеет предпочтительный вид, то в него не следует вводить искусственную переменную.
Пример 1.13
Найти начальный опорный план ЗЛП методом искусственного базиса и значение целевой функции на этом плане:
;
Решение
Запишем ЗЛП в каноническом виде с неотрицательной правой частью.
;
Составим М-задачу:
;
Тогда начальный опорный план: 
, значение целевой функции на этом плане: 
.
Пример 1.14
Найти начальный опорный план ЗЛП методом искусственного базиса и значение целевой функции на этом плане:
;
Решение
Запишем ЗЛП в каноническом виде с неотрицательной правой частью.
;
Составим М-задачу:
;
Тогда начальный опорный план: 
, значение целевой функции на этом плане: 
.
Пример 1.15
Найти начальный опорный план ЗЛП методом искусственного базиса и значение целевой функции на этом плане:
;
Решение
Запишем ЗЛП в каноническом виде с неотрицательной правой частью.
;
где 
.
Составим М-задачу:
;
где 
.
Тогда начальный опорный план: 
, значение целевой функции на этом плане: 
.
Нахождение начального опорного плана ЗЛП методом Жордановых исключений
В случае, когда ограничение-равенство системы не имеет предпочтительного вида, его необходимо записать как 0-равенство, т.е. левую часть ограничения переносят в скобках со знаком минус в правую часть, при этом в левой части остается ноль. Если ограничение-равенство системы имеет предпочтительный вид, то предпочтительную (базисную) переменную оставляют в левой части ограничения, а все остальное из левой части переносят в скобках со знаком минус в правую часть. Переменные, которые оказались при этом в правых частях ограничений, являются свободными. Целевая функция должна быть выражена только через свободные переменные и записана в идентичном виде, т.е. от свободного члена отнимают скобку с остальными элементами целевой функции (при этом целевая функция не должна измениться).
Пусть ЗЛП имеет каноническую форму записи с неотрицательной правой частью:
где 
.
Если ни одно из ограничений не имеет предпочтительной переменной, то задача будет записана следующим образом:
где 
.
Для нахождения начального опорного плана методом Жордановых исключений необходимо исходя из вида задачи (1.18 – 1.19) заполнить таблицу Жордана и преобразовывать ее до тех пор (см. шаг Жордановых исключений), пока не будет найден начальный опорный план или пока не убедимся, что опорный план отсутствует и задача не имеет решения вследствие несовместности системы ограничений.
Таблица Жордана содержит 
столбцов, где – число переменных, 
– число предпочтительных (базисных) переменных и 
строки, где 
– число ограничений-равенств. В первом столбце «БП» записываются базисные (предпочтительные) переменные. Если ограничение не имеет предпочтительной переменной, то записывается «0». Второй столбец «1» – столбец свободных членов 
системы ограничений (1.19) а в 
-строке – элемент 
из (1.18). Остальные столбцы таблицы – «СП», в основной части которых находятся элементы 
из системы (1.19). В 
-строке в столбцах «СП» записываются коэффициенты при свободных переменных, стоящие в скобках выражения (1.18). Каждому ограничению-равенству из системы (1.19) соответствует строка основной части таблицы. Целевой функции (1.18) соответствует последняя строка таблицы.
Исходя из вида задачи (1.18 – 1.19) заполним таблицу Жордана (табл. 1.1).
Таблица 1.1
| СП | ||||||
| БП | 1 | 
| … | 
| ... | 
|
| 0 | 
| 
| … | 
| ... | 
|
| ... | ... | ... | … | ... | .... | ... |
| 0 | 
| 
| … | 
| ... | 
|
| ... | ... | ... | … | ... | ... | ... |
| 0 | 
| 
| … | 
| ... | 
|
| 
| 
| … | 
| ... | 
|
Преобразование таблицы называется шагом Жордановых исключений и осуществляется относительно выбранного разрешающего элемента. Разрешающий элемент выбирается среди положительных чисел основной части таблицы (которая выделена, ) по наименьшему отношению свободных членов (элементы столбца «1») к соответствующим положительным элементам столбца, выбранного разрешающим.
Пусть столбец 
будет разрешающим, тогда если 
для 
, то 
– разрешающий элемент.
Шаг Жордановых исключений осуществляется по следующим правилам:
1) Элемент (либо ноль либо переменная) столбца «БП» в строке разрешающего элемента меняется местами с переменной 
.
2) Разрешающий элемент заменяется обратной величиной.
3) Остальные элементы разрешающей строки делятся на разрешающий элемент.
4) Остальные элементы разрешающего столбца делятся на разрешающий элемент и меняют знак на противоположный.
5) Прочие элементы вычисляются по формуле:
.
Или диагональ «прямоугольника», на которой расположен разрешающий элемент 
и преобразуемый элемент назовем главной, а другую диагональ – побочной. Тогда преобразованный элемент 
равен разности произведений элементов, расположенных на главной и побочной диагоналях, деленной на разрешающий элемент.
6) 0-столбец вычеркивается.
Если система ограничений совместна, то через некоторое число шагов все нули в первом столбце «БП» будут замещены переменными 
и в таблице будет найден начальный опорный план. Выпишем его, приравняв свободные переменные к нулю, а базисные переменные (столбец «БП») – к соответствующим свободным членам (столбец «1»).
Если в ходе Жордановых преобразований встретится 0-строка, в которой нет положительных элементов в основной части таблицы, то опорный план отсутствует, и задача не имеет решения вследствие несовместности системы ограничений.
Допустим, после некоторого числа шагов Жордановых преобразований все нули в левом столбце замещены переменными , т.е. получили табл. 1.2.
Таблица 1.2
| СП | ||||||
| БП | 1 | 
| … |
| ... | 
|
| 
| 
| … | 
| ... | 
|
| ... | ... | ... | … | ... | ... | ... |
| 
| 
| … | 
| ... | 
|
| ... | ... | ... | … | ... | ... | ... |
| 
| 
| … | 
| ... | 
|
| 
| 
| … | 
| ... | 
|
Тогда компоненты начального опорного плана 
будут:
БП: 
,…, 
,…, 
,
СП: 
.
Таким образом, начальный опорный план: 
, значение целевой функции на этом плане: 
.
Пример 1.16
Найти начальный опорный план ЗЛП, составленной в примере 1.2 методом Жордановых исключений и значение целевой функции на этом плане.
Решение
В примере 1.2 составлена ЗЛП:
;
Запишем ЗЛП в каноническом виде с неотрицательной правой частью.
;
Введенные дополнительные переменные 
и 
имеют экономический смысл, связанный с содержанием задачи. Здесь 
, – время простоя оборудования А1 и А2 соответственно.
Переменные 
, являются предпочтительными и для заполнения таблицы Жордана перепишем задачу в виде (1.18 – 1.19):
;
Здесь в третьем и в четвертом ограничениях предпочтительные переменные 
и оставлены в левой части.
Заполним таблицу Жордана:
Таблица 1.3
| СП | ||||||
| БП | 1 | 
| 
| 
| 
| отношения |
| 0 | 31 | 5 | 0 | 4 | 0 | 31/5 |
| 0 | 36 | 0 | 3 | 0 | 6 | – |
| 10 | 1 | 1 | 0 | 0 | 10/1 |
| 10 | 0 | 0 | 1 | 1 | – |
|
| 0 | –8 | –7 | –4 | –2 | |
Пусть -столбец будет разрешающим. Для нахождения разрешающей строки составим отношения свободных членов к соответствующим положительным элементам этого столбца. Т.к. в этом столбце только два положительных элемента «5» и «1», то отношения будут 
и 
. Поскольку 
, то элемент «5» и будет разрешающим. Шаг Жордановых исключений относительно найденного разрешающего элемента переводит табл. 1.3 в табл. 1.5. При этом в табл. 1.4 показан процесс вычисления элементов табл. 1.5.
Таблица 1.4
| СП | |||||
| БП | 1 | 0 | 
| 
| 
|
|
| 
| 
| 
| 
| 
|
| 0 | 
| 
| 
| 
| 
|
|
| 
| 
| 
| 
| 
|
| 
|
| 
| 
| 
|
| Z | 
| 
| 
| 
| 
|
Таблица 1.5
| СП | |||||
| БП | 1 | 
|
|
| отношения |
| 6,2 | 0 | 0,8 | 0 | – |
| 0 | 36 | 3 | 0 | 6 | 36/6 |
|
| 3,8 | 1 | –0,8 | 0 | – |
|
| 10 | 0 | 1 | 1 | 10/1 |
| Z | 49,6 | –7 | 2,4 | –2 |
Пусть теперь разрешающим будет 
-столбец. Найдем отношения свободных членов к соответствующим положительным элементам этого столбца. Это 
и 
(табл. 1.5). Т.к. 
, то вторая строка будет разрешающей. Итак, следующий разрешающий элемент будет «6», и шаг Жордановых исключений переводит табл. 1.5 в табл. 1.6.
Таблица 1.6
| СП | |||
| БП | 1 |
|
|
|
| 6,2 | 0 | 0,8 |
|
| 6 | 0,5 | 0 |
|
| 3,8 | 1 | –0,8 |
| 4 | –0,5 | 1 |
| Z | 61,6 | –6 | 2,4 |
Т.к. все нули в столбце «БП» замещены переменными, то в табл.1.6 найден начальный опорный план. Выпишем его, приравняв свободные переменные к нулю, т.е. 
, а базисные переменные – к соответствующим элементам столбца «1», т.е. 
.
Итак, начальный опорный план: 
. Значение целевой функции на этом плане: 
.
Исследование на оптимальность опорного плана при решении ЗЛП на 
Заполним симплексную таблицу (табл. 1.2), исходя из задачи, записанной в виде:
; (1.20)
(1.21)
где 
, а 
– предпочтительные переменные.
Если начальный опорный план был найден методом Жордановых исключений, то воспользуемся таблицей, в которой уже найден начальный опорный план.
Оценками называются элементы симплексной таблицы, расположенные на пересечении последней строки (Z-строки) и столбцов «СП» (элементы 
табл. 1.2).
1) Если все оценки положительные (отрицательные) – найденный в таблице план оптимальный и единственный.
2) Если все оценки неотрицательные (неположительные), т.е. наряду с положительными (отрицательными) оценками присутствуют нулевые, – найденный в таблице план оптимальный, но не единственный.
3) Если есть отрицательные (положительные) оценки, а в соответствующих им столбцах нет положительных элементов, то целевая функция неограниченна и задача не имеет решения.
4) Если есть отрицательные (положительные) оценки и в соответствующих им столбцах есть положительные элементы, то можно перейти к новому опорному плану, более близкому к оптимальному.
Переход к новому опорному плану
1) В табл. 1.2 выбираем разрешающий элемент в столбце с наибольшей по абсолютной величине отрицательной (положительной) оценкой. Пусть столбец будет разрешающим, тогда если 
для 
, то – разрешающий элемент.
2) Перейти к новому плану преобразовав симплексную таблицу по алгоритму шага Жордановых исключений.
Пример 1.17
Решить симплексным методом ЗЛП, составленную в примере 1.2.
Решение
В предыдущем примере 1.16 для этой задачи был найден начальный опорный план. Для проверки его на оптимальность воспользуемся табл. 1.6, в которой он записан. Т.к. среди оценок есть положительные оценки, то найденный опорный план не оптимален. Поскольку единственная положительная оценка находится в столбце 
, то он и будет разрешающим. Составим отношения свободных членов к соответствующим положительным элементам этого столбца (табл. 1.7). По наименьшему отношению выберем разрешающую строку. Т.к. 
, то -строка будет разрешающей. На пересечении разрешающего столбца и разрешающей строки найдем разрешающий элемент «1» (табл. 1.7).
Таблица 1.7
| СП | ||||
| БП | 1 |
|
| отношения |
|
| 6,2 | 0 | 0,8 | 6,2/0,8 |
|
| 6 | 0,5 | 0 | – |
|
| 3,8 | 1 | –0,8 | – |
| 4 | –0,5 | 1 | 4/1 |
| Z | 61,6 | –6 | 2,4 | |
Шаг Жордановых исключений переводит табл. 1.7 в табл. 1.8, в которой будет получен новый опорный план, более близкий к оптимальному.
Таблица 1.8
| СП | |||
| БП | 1 | 
| 
|
| 3 | 0,4 | –0,8 |
| 6 | 0,5 | 0 |
|
| 7 | 0,6 | 0,8 |
| 4 | –0,5 | 1 |
| Z | 52 | –4,8 | –2,4 |
Т.к. все оценки отрицательные, то полученный в табл. 1.8 опорный план оптимален и единственен. Выпишем его, приравняв свободные переменные к нулю, т.е. 
, а базисные переменные – к соответствующим элементам столбца «1», т.е. 
.
Итак, оптимальный план, 
и 
.
Перейдем к решению исходной задачи (имеющей переменные 
): 
и 
.
Пример 1.18
Решить симплексным методом ЗЛП примера 1.14.
Решение
Воспользуемся найденным в примере 1.14 начальным опорным планом.
Для проверки плана на оптимальность заполним симплексную таблицу (табл.1.9), переписав М-задачу в виде (1.20 – 1.21):
Таблица 1.9
| СП | |||||
| БП | 1 | 
| 
|
| отношения |
| 2 | –1 | 4 | –1 | 2/4 |
|
| 8 | 0 | 1 | 2 | 8/1 |
| 6 | 0 | –3 | 4 | – |
| Z | 2М | –М–6 | 4М+4 | –М–1 |
Т.к. среди оценок есть положительные оценки, то найденный опорный план не оптимален. Поскольку единственная положительная оценка находится в столбце , то он и будет разрешающим. Составим отношения свободных членов к соответствующим положительным элементам этого столбца (табл. 1.9). По наименьшему отношению выберем разрешающую строку. Т.к. 
, то -строка будет разрешающей. На пересечении разрешающего столбца и разрешающей строки найдем разрешающий элемент «4» (табл. 1.9). Шаг Жордановых исключений переводит табл. 1.9 в табл. 1.10, в которой будет получен новый опорный план, более близкий к оптимальному.
Таблица 1.10
| СП | ||||
| БП | 1 |
|
| 
|
|
| 
| 
| 
| 
|
|
| 
| 
| 
| 
|
| 
| 
| 
| 
|
| Z | –2 | –5 | 
| 0 |
Полученный в табл. 1.10 опорный план оптимален, но не единственен, т.к. наряду с отрицательными оценками присутствует нулевая оценка. Выпишем его, приравняв свободные переменные к нулю, т.е. 
, а базисные переменные – к соответствующим элементам столбца «1», т.е. 
.
Итак, оптимальный план 
и 
. Перейдем к решению исходной задачи (имеющей переменные 
): 
и .
Пример 1.19
Решить симплексным методом ЗЛП:
Решение
Математическую модель задачи представим в канонической форме с неотрицательной правой частью:
Здесь каждое ограничение системы имеет предпочтительную переменную. Начальный опорный план найдем, приравняв свободные переменные и 
к нулю, а предпочтительные переменные и 
– к правой части соответствующих ограничений. Итак, начальный опорный план: 
и 
.
Для проверки плана на оптимальность заполним симплексную таблицу. Для этого представим каноническую запись в виде (1.20 – 1.21):
Заполним симплексную таблицу:
| СП | ||||
| БП | 1 |
|
| отношения |
|
| 2 | 2 | –1 | 2/2 |
|
| 4 | 1 | 0 | 4/1 |
| 0 | 3 | –1 | |
Т.к. среди оценок есть отрицательная оценка, а в соответствующем столбце нет положительных элементов, то целевая функция неограниченна и задача не имеет решения.
Пример 1.20
Решить симплексным методом ЗЛП:
Решение
Математическую модель задачи представим в канонической форме с неотрицательной правой частью:
Найдем начальный опорный план ЗЛП методом Жордановых исключений. Для заполнения первой таблицы Жордана (табл. 1.11) представим каноническую форму записи в виде (1.18 – 1.19):
Здесь в первом ограничении предпочтительная переменная оставлена в левой части.
Таблица 1.11
| СП | |||||
| БП | 1 |
|
|
| отношения |
|
| 2 | 2 | 1 | 0 | 2/1 |
| 0 | 12 | 3 | 4 | –1 | 12/4 |
| 5 | –1 | –4 | 0 | |
Начальный опорный план будет найден, если в первом столбце таблицы все нули в ходе преобразований таблицы будут заменены переменными.
Пусть -столбец будет разрешающим. Для нахождения разрешающей строки составим отношения свободных членов к соответствующим положительным элементам этого столбца. Т.к. 
, то элемент «1» будет разрешающим. Шаг Жордановых исключений относительно найденного разрешающего элемента переводит табл. 1.11 в табл. 1.12.
Таблица 1.12
| СП | ||||
| БП | 1 |
|
|
|
|
| 2 | 2 | 1 | 0 |
| 0 | 4 | –5 | –4 | –1 |
| 13 | 7 | 4 | 0 |
Т.к. в табл.1.12 есть 0-строка, в которой нет положительных элементов в основной части таблицы, то опорный план отсутствует, и задача не имеет решения вследствие несовместности системы ограничений.
Пример 1.21
Решить симплексным методом ЗЛП:
Решение
Математическую модель задачи представим в канонической форме с неотрицательной правой частью:
где 
.
Найдем начальный опорный план ЗЛП методом Жордановых исключений. Для заполнения первой таблицы Жордана (табл. 1.13) представим каноническую форму записи в виде (1.18 – 1.19):
где .
Здесь во втором ограничении предпочтительная переменная 
оставлена в левой части.
Таблица 1.13
| СП | ||||||
| БП | 1 | 
| 
| 
|
| отношения |
| 0 | 3 | –3 | 3 | –1 | –1 | 3/3 |
|
| 1 | –1 | 1 | –2 | 0 | 1/1 |
| 0 | –12 | 12 | –2 | 0 | |
Т.к. только в -столбце есть положительные элементы в основной части таблицы, то только он может быть разрешающим. Найдем отношения свободных членов к соответствующим положительным элементам этого столбца. Это 
и 
(табл. 1.13). Т.к. 
, то любая строка может быть разрешающей, но для получения начального опорного плана необходимо избавиться от нулей в столбце «БП», следовательно, целесообразно 0-строку взять разрешающей. На пересечении разрешающего столбца и разрешающей строки находим разрешающий элемент «3» и шаг Жордановых исключений переводит табл. 1.13 в табл. 1.14.
Таблица 1.14
| СП | |||||
| БП | 1 | 
| 
|
| |
| 1 | –1 | 
|
| |
|
| 0 | 0 | 
|
| |
|
| –12 | 0 | 2 | 4 | |
В табл. 1.14 найден начальный опорный план: 
и 
. Этот опорный план оптимален, но не единственен, т.к. наряду с положительными оценками присутствует нулевая оценка.
Итак, оптимальный план 
и 
. Перейдем к решению исходной задачи (имеющей переменные 
, где 
): 
и .
Пример 1.22
Решить симплексным методом ЗЛП:
Решение
Математическую модель задачи представим в канонической форме с неотрицательной правой частью:
Найдем начальный опорный план ЗЛП методом Жордановых исключений. Для заполнения первой таблицы Жордана (табл. 1.15) представим каноническую форму записи в виде (1.18 – 1.19):
Здесь предпочтительные переменные 
и 
оставлена в левой части.
Таблица 1.15
| СП | ||||||
| БП | 1 |
|
| 
|
| отношения |
|
| 6 | 3 | 2 | –1 | 0 | 6/3 |
| 0 | 2 | 1 | –4 | 0 | –1 | 2/1 |
|
| 5 | 1 | –1 | 0 | 0 | 5/1 |
|
| 20 | 8 | 5 | –3 | 0 | |
Пусть 
-столбец будет разрешающим. Найдем отношения свободных членов к соответствующим положительным элементам этого столбца. Это 
, 
и 
(табл. 1.15). Т.к. минимальные отношения 
, то любая из этих двух строк ( -строка или 0-строка) может быть разрешающей, но для получения начального опорного плана необходимо избавиться от нулей в столбце «БП», следовательно, целесообразно 0-строку взять разрешающей. На пересечении разрешающего столбца и разрешающей строки находим разрешающий элемент «1» и шаг Жордановых исключений переводит табл. 1.15 в табл. 1.16.
Таблица 1.16
| СП | |||||
| БП | 1 |
| 
|
| отношения |
| 0 | 14 | –1 | 3 | 0/14 |
|
| 2 | –4 | 0 | –1 | – |
|
| 3 | 3 | 0 | 1 | 3/3 |
| 4 | 37 | –3 | 8 | |
В табл. 1.16 найден начальный опорный план: 
и 
. Т.к. среди оценок есть положительные, то найденный план не оптимален. Перейдем к новому плану, более близкому к оптимальному. Выбираем разрешающий элемент в столбце с наибольшей по абсолютной величине положительной оценкой. Это будет -столбец. Найдем отношения свободных членов к соответствующим положительным элементам этого столбца. Это 
и 
(табл. 1.16). Т.к. 
, то элемент «14» будет разрешающим. Шаг Жордановых исключений относительно найденного разрешающего элемента переводит табл. 1.16 в табл. 1.17.
Таблица 1.17
| СП | |||||
| БП | 1 |
|
|
| отношения |
|
| 0 | 
| 
| 
| 0:
|
|
| 2 | 
| 
| 
| – |
| 3 | 
| 
| 
| 3:
|
|
| 4 | 
| 
|
| |
Т.к. среди оценок есть положительная, то найденный план не оптимален. Перейдем к новому плану, более близкому к оптимальному. Выбираем разрешающий элемент в столбце с единственной положительной оценкой. Это будет 
-столбец. По наименьшему отношению выбираем -строку разрешающей. Тогда элемент « » будет разрешающим. Шаг Жордановых исключений относительно найденного разрешающего элемента переводит табл. 1.17 в табл. 1.18.
Таблица 1.18
| СП | ||||
| БП | 1 |
| 
| 
|
|
| 0 | 
| 
| 
|
|
| 2 | 
|
| 
|
|
| 3 | 
|
| 
|
|
| 4 | 
|
|
|
Т.к. все оценки отрицательные, то полученный в табл. 1.18 опорный план оптимален и единственен. Выпишем его, приравняв свободные переменные к нулю, т.е. 
, а базисные переменные – к соответствующим элементам столбца «1», т.е. 
.
Итак, оптимальный план, 
и 
.
Перейдем к решению исходной задачи (имеющей переменные 
): 
и 
.
Задачи
Решить ЗЛП симплексным методом (1.5.1 – 1.5.8)
1.5.1
 ;
1.5.3
 ;
1.5.5
 ;
1.5.7
 ;
| 1.5.2
 ;
1.5.4
 ;
1.5.6
 ;
1.5.8
 ;
|
1.5.9 – 1.5.12
Решить задачи 1.1.5 – 1.1.8 (соответственно) симплексным методом.
1.5.13 – 1.5.16
Решить задачи 1.2.1 – 1.2.4 (соответственно) симплексным методом.
1.5.17 – 1.5.26
Решить задачи 1.3.3 – 1.3.12 (соответственно) симплексным методом.
1.5.27 – 1.5.34
Решить задачи 1.4.1 – 1.4.8 (соответственно) симплексным методом.
1.6. Двойственные задачи линейного программирования
С каждой ЗЛП, называемой прямой или исходной, тесно связана другая ЗЛП, называемая двойственной. При этом указанные задачи будут образовывать пару взаимно двойственных задач. Решая одну из них, можно найти решение и второй задачи.
Пара двойственных ЗЛП в симметричной форме имеет следующий вид:
прямая задача
| двойственная задача
|
Рассмотренная пара взаимно двойственных задач может быть экономически интерпретирована, например, так.
Прямая задача: сколько продукции j-го вида 
надо произвести, чтобы при заданных стоимостях единицы продукции 
, объемах имеющихся ресурсов 
и нормах расходов 
максимизировать выпуск продукции в стоимостном выражении?
Двойственная задача: какова должна быть оценка единицы каждого из ресурсов 
, чтобы при заданных стоимостях единицы продукции , объемах имеющихся ресурсов и нормах расходов минимизировать общую оценку затрат на все ресурсы?
Чтобы из решения прямой задачи получить решение двойственной задачи нужно записать обе задачи в канонической форме:
прямая задача
| двойственная задача
|
Между переменными двойственных задач существует следующее соответствие:
Если в оптимальном плане прямой задачи переменная равна нулю, то соответствующая ей переменная двойственной задачи отлична от нуля. Значения целевых функций двойственных задач совпадают, т.е. 
.
При решении прямой задачи графическим методом для нахождения оптимального плана двойственной задачи необходимо в системе ограничений канонической формы двойственной задачи оставить отличные от нуля переменные и решить ее аналитически.
При решении прямой задачи симплексным методом для нахождения оптимального плана двойственной задачи необходимо воспользоваться симплексной таблицей, в которой записан оптимальный план прямой задачи. Двойственные переменные, соответствующие базисным переменным прямой задачи будут равны нулю, а соответствующие свободным переменным – будут равны абсолютной величине оценок этих столбцов.
Если прямая задача не имеет решения, то и двойственная ей тоже не имеет решения.
Пример 1.23
Составить задачу, двойственную к ЗЛП, рассмотренной в примере 1.3. Дать экономическую интерпретацию прямой и двойственной задач. Из решения прямой задачи (пример 1.6) найти решение двойственной задачи.
Решение
прямая задача
 ;
| двойственная задача
 ;
|
Экономическая интерпретация.
Прямая задача: сколько единиц 
продукции Пj надо произвести, чтобы при заданной прибыли от единицы продукции, объемах имеющихся ресурсов и нормах расходов максимизировать прибыль от всей выпущенной продукции?
Двойственная задача: какова должна быть оценка единицы каждого из ресурсов 
, чтобы при заданной прибыли от единицы продукции, объемах имеющихся ресурсов и нормах расходов минимизировать общую оценку затрат на все ресурсы?
В примере 1.6 было получено решение прямой задачи графическим методом. Это 
, 
.
Для нахождения решения двойственной задачи запишем обе задачи в канонической форме:
прямая задача
 ;
| двойственная задача
;
|
Между переменными двойственных задач существует следующее соответствие:
Определим из канонической формы прямой задачи, какие переменные равны нулю в оптимальном плане и из приведенного соответствия определим отличные от нуля двойственные переменные. Так
,
,
,
,
.
Для нахождения отличных от нуля двойственных переменных 
и 
решим систему уравнений, полученную из системы ограничений канонической формы двойственной задачи:
Откуда 
. Таким образом, 
, или для двойственной задачи в симметричной форме 
. Причем 
.
Оценки единицы каждого из ресурсов определяют дефицитность используемых ресурсов и показывают, насколько увеличится целевая функция при увеличении соответствующего ресурса на единицу.
Так как 
и отличны от нуля, то второй и третий ресурсы (сырье и электроэнергия) являются дефицитными. При этом 
, следовательно, наиболее дефицитным является второй ресурс (сырье). Поскольку 
, то ресурс первого вида (время работы оборудования) является избыточным. При увеличении сырья на 1 кг прибыль от всей выпущенной продукции увеличится на 3 руб., а при увеличении электроэнергии на 1 кВтч. прибыль от всей выпущенной продукции увеличится на 1 руб.
Дата добавления: 2018-09-20; просмотров: 420; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!