 |
Лекция 4: симплекс-метод для решения задач линейного программирования.
|
|
|
|
1. Понятие симплекс-метода
2. Методика решения задач симплекс-методом.
С увеличением числа неизвестных геометрический метод решения ЗЛП становится затруднительным при трех переменных и невозможным при большем числе переменных.
Поэтому был разработан универсальный метод решения ЗЛП – симплекс-метод, позволяющий решать ЗЛП в канонической форме.
Изложим суть симплекс-метода на примере задач с 5 неизвестными.
Пусть ЗЛП приведена к виду
(4.1)
при ограничениях:
, (4.2)
где 
,
(4.3)
Про систему ограничений (4.2) говорят, что она имеет допустимый вид, если одни неизвестные (
) выражаются через остальные (
), причем свободные члены этих выражений неотрицательны ().
Неизвестные 
и 
называются базисными, а неизвестные – свободными.
Возможны два принципиальных случая:
1. Все коэффициенты при свободных неизвестных в выражении для F неположительны: 
и 
. Тогда для всякого неотрицательного решения системы уравнений (4.2) имеем 
и 
, а потому
или 
.
Следовательно, базисное решение 
является оптимальными, т. е. задача решена.
2. Имеется свободное неизвестное, коэффициент при котором в выражении для F положителен, а все коэффициенты при этом неизвестном в уравнениях (4.2) – неотрицательны.
Для определенности положим 
. Исходя из базисного решения, станем наращивать значение 
, не меняя 
. Тогда значения базисных неизвестных будут оставаться неотрицательными:
,
а значение 
будет неограниченно возрастать, т.е. 
и задача решения не имеет.
Решения ЗЛП редуцируются к одному из случаев 1 или 2 путем перехода к новому базису, в котором целевая функция не уменьшит своего значения для базисного решения, а новая система ограничений должна иметь допустимый вид. Преобразование базиса и перестройку целевой функции и системы ограничений называют шагом в решении ЗЛП. Таким образом, сделав нужное число шагов, решают ЗЛП (4.1) – (4.3).
|
|
|
Применим симплекс-метод к первой задаче, рассмотренной в Лекции 3.
I. Основная задача в примере 1 имеет вид
Сначала приведем ее к каноническому виду, вводя балансовые неизвестные 
, 
и 
:
(4.4)
(4.5)
Теперь приведем (4.4) к допустимому виду – неизвестные 
, 
и выразим через и 
, при этом свободные члены в правых частях полученных уравнений неотрицательны:
(4.6)
Здесь , и – базисные неизвестные, а и – свободные неизвестные.
Шаг 1: положим в (4.6) 
и , тогда 
, 
, 
. Получим неотрицательное решение 
системы уравнений (4.6). Его называют базисным решением. Для него 
.
Шаг 2: положим в (4.6) , а начнем наращивать так, чтобы , и оставались неотрицательными, т. е.
.
Решая эти неравенства, найдем наименьшее значение 
. Тогда 
. Объявив и свободными неизвестными, приведем (4.6) к допустимому виду:
(4.7)
Получим неотрицательное решение 
системы уравнений (4.7). Для него
(4.8)
примет значение 
.
Сделаем выводы.
Во-первых, значение F по сравнению с 1-ым шагом увеличилось.
Во-вторых, в (4.8) коэффициент при отрицательный и для дальнейшего увеличения значения F надо положить и наращивать .
Шаг 3: положим в (4.7) , а начнем наращивать так, чтобы , и оставались неотрицательными, т. е.
.
Откуда находим наименьшее значение 
. Тогда 
. Объявив и свободными неизвестными, приведем (5.7) к допустимому виду:
(4.9)
Получили неотрицательное решение 
системы уравнений (4.9). Для него
(4.10)
примет значение 
.
Сделаем выводы.
Во-первых, значение F по сравнению со 2-ым шагом увеличилось.
Во-вторых, в (4.10) оба коэффициента при свободных неизвестных отрицательны и дальнейшее увеличение значения F невозможно:
при 
. Задача решена. Учитывая экономический смысл неизвестных, приходим к выводу: предприятие получит наибольшую прибыль 1104 единиц при изготовлении 36 единиц товара 
и 6 единиц товара 
, при этом остатки ресурсов 
и 
равны нулю
|
|
|
(), а остаток ресурса 
равен 12 единицам.
Замечание. Просматривая шаги решенной ЗЛП, убеждаемся, что были последовательно перебраны вершины многоугольника решений 
(см. рис. 3.7 в Лекции 3): шаг 1 – вершина 
, шаг 2 – вершина 
, шаг 3 – вершина 
, которая доставляет максимум целевой функции F.
Если решается ЗЛП, в которой требуется найти минимум целевой функции, то задачу либо сводят к рассмотренной выше задаче с целевой функцией 
, либо с помощью шагов приводят к одному из двух принципиальных случаев:
1. Все коэффициенты при свободных неизвестных в выражении для F (4.1) неотрицательны: 
и 
. Тогда базисное решение является решением задачи.
2. Имеется свободное неизвестное, коэффициент при котором в выражении для F (4.1) отрицателен, а все коэффициенты при этом неизвестном в уравнениях (4.2) – неотрицательны. Тогда задача решения не имеет.
Применим симплекс-метод ко второй задаче, рассмотренной в Лекции 2.
II. Основная задача в примере 2 имеет вид
Сначала приведем ее к каноническому виду, вводя балансовые неизвестные , и :
(4.11)
(4.12)
Приведем ограничения (4.11) к допустимому виду. Как показано выше, в качестве базисных неизвестных следует выбирать такие неизвестные, каждая из которых входит только в одно из уравнений системы ограничений (4.11), при этом нет таких уравнений системы, в которые не входит ни одна из этих неизвестных, и каждая базисная неизвестная имеет тот же знак, что и свободный член.
Нетрудно видеть, что , и не могут быть базисными неизвестными. Действительно,
(4.13)
и знаки , и противоположны знакам свободных членов.
Для выделения базисных неизвестных из системы ограничений (4.11) необходима ее перестройка.
Полагая в (4.13) (или ) найдем из условий неотрицательности , и :
.
наибольшее значение 
. Тогда и систему (4.13) запишем в виде
(4.14)
Получили систему ограничений, имеющую допустимый вид: , и – базисные неизвестные, и – свободные неизвестные. Перейдем к процедуре шагов.
Шаг 1: положим в (4.14) и , тогда получим базисное решение 
, для которого целевая функция
(4.15)
примет значение 
.
В (4.15) коэффициент при положительный и для дальнейшего уменьшения значения f надо положить и наращивать .
|
|
|
Шаг 2: положим в (4.14) , а начнем наращивать так, чтобы , и оставались неотрицательными, т. е.
.
Откуда находим 
. Тогда . Объявив и свободными неизвестными, приведем (4.14) к допустимому виду:
(4.16)
Из (4.16) получим базисное решение 
. Для него
(4.17)
примет значение 
.
В (4.17) коэффициенты при свободных неизвестных положительны и дальнейшее уменьшение значения f невозможно: 
при . Задача решена.
Учитывая экономический смысл неизвестных, приходим к выводу.
Ежесуточная диета, обеспечивающая необходимое количество питательных веществ, состоит из 
единиц продукта 
, 
единиц продукта 
и ее минимальная стоимость 
единиц. При этом потребности организма в питательных веществах A и B отвечают требуемым минимальным объемам 
единиц и 
единиц соответственно (т.к. и 
), а потребности в питательном веществе С больше требуемого минимального объема 
единиц на 
единиц.
В заключение рассмотрим вопрос: всегда ли после конечного числа шагов симплекс-метод закончится либо нахождением оптимального решения, либо установлением того факта, что задача не имеет решения.
Ответ утвердительный и содержится в следующей теореме.
Теорема. Если существует оптимальное решение ЗЛП, то существует и базисное оптимальное решение. Последнее всегда может быть получено с помощью симплекс-метода.
|
|
|
