Симплекс-метод для решения задач линейного программирования.
С увеличением числа неизвестных геометрический метод решения ЗЛП становится затруднительным при трех переменных и невозможным при большем числе переменных.
Поэтому был разработан универсальный метод решения ЗЛП – симплекс-метод, позволяющий решать ЗЛП в канонической форме.
Изложим суть симплекс-метода на примере задач с 5 неизвестными.
Пусть ЗЛП приведена к виду
(20)
при ограничениях:
, (21)
где ,
(22)
Про систему ограничений (21) говорят, что она имеет допустимый вид, если одни неизвестные ( ) выражаются через остальные ( ), причем свободные члены этих выражений неотрицательны ( ).
Неизвестные и называются базисными, а неизвестные – свободными.
Возможны два принципиальных случая:
1Å Все коэффициенты при свободных неизвестных в выражении для F неположительны: и . Тогда для всякого неотрицательного решения системы уравнений (21) имеем и , а потому
или .
Следовательно, базисное решение является оптимальными, т. е. задача решена.
2Å Имеется свободное неизвестное, коэффициент при котором в выражении для F положителен, а все коэффициенты при этом неизвестном в уравнениях (21) – неотрицательны.
Для определенности положим . Исходя из базисного решения, станем наращивать значение , не меняя . Тогда значения базисных неизвестных будут оставаться неотрицательными:
,
а значение будет неограниченно возрастать, т.е. и задача решения не имеет.
Решения ЗЛП редуцируются к одному из случаев 1Å или 2Å путем перехода к новому базису, в котором целевая функция не уменьшит своего значения для базисного решения, а новая система ограничений должна иметь допустимый вид. Преобразование базиса и перестройку целевой функции и системы ограничений называют шагом в решении ЗЛП. Таким образом, сделав нужное число шагов, решают ЗЛП (20) – (22).
Применим симплекс-метод к первой задаче.
I. Основная задача в примере 1 имеет вид
Сначала приведем ее к каноническому виду, вводя балансовые неизвестные , и :
(23)
(24)
Теперь приведем (23) к допустимому виду – неизвестные , и выразим через и , при этом свободные члены в правых частях полученных уравнений неотрицательны:
(25)
Здесь , и – базисные неизвестные, а и – свободные неизвестные.
Шаг 1: положим в (25) и , тогда , , . Получим неотрицательное решение системы уравнений (25). Его называют базисным решением. Для него .
Шаг 2: положим в (25) , а начнем наращивать так, чтобы , и оставались неотрицательными, т. е.
.
Решая эти неравенства, найдем наименьшее значение . Тогда . Объявив и свободными неизвестными, приведем (25) к допустимому виду:
(26)
Получим неотрицательное решение системы уравнений (26). Для него
(27)
примет значение .
Сделаем выводы.
Во-первых, значение F по сравнению с 1-ым шагом увеличилось.
Во-вторых, в (27) коэффициент при отрицательный и для дальнейшего увеличения значения F надо положить и наращивать .
Шаг 3: положим в (26) , а начнем наращивать так, чтобы , и оставались неотрицательными, т. е.
.
Откуда находим наименьшее значение . Тогда . Объявив и свободными неизвестными, приведем (27) к допустимому виду:
(28)
Получили неотрицательное решение системы уравнений (28). Для него
(29)
примет значение .
Сделаем выводы.
Во-первых, значение F по сравнению со 2-ым шагом увеличилось.
Во-вторых, в (29) оба коэффициента при свободных неизвестных отрицательны и дальнейшее увеличение значения F невозможно:
при . Задача решена. Учитывая экономический смысл неизвестных, приходим к выводу: предприятие получит наибольшую прибыль 1104 единиц при изготовлении 36 единиц товара и 6 единиц товара , при этом остатки ресурсов и равны нулю ( ), а остаток ресурса равен 12 единицам.
Если решается ЗЛП, в которой требуется найти минимум целевой функции, то задачу либо сводят к рассмотренной выше задаче с целевой функцией , либо с помощью шагов приводят к одному из двух принципиальных случаев:
1Å Все коэффициенты при свободных неизвестных в выражении для F неотрицательны: и . Тогда базисное решение является решением задачи.
2Å Имеется свободное неизвестное, коэффициент при котором в выражении для F (20) отрицателен, а все коэффициенты при этом неизвестном в уравнениях (21) – неотрицательны. Тогда задача решения не имеет.
Применим симплекс-метод ко второй задаче, Основная задача в примере 2 имеет вид
Сначала приведем ее к каноническому виду, вводя балансовые неизвестные , и :
(30)
(31)
Приведем ограничения (30) к допустимому виду. Как показано выше, в качестве базисных неизвестных следует выбирать такие неизвестные, каждая из которых входит только в одно из уравнений системы ограничений (31), при этом нет таких уравнений системы, в которые не входит ни одна из этих неизвестных, и каждая базисная неизвестная имеет тот же знак, что и свободный член.
Нетрудно видеть, что , и не могут быть базисными неизвестными. Действительно,
(32)
и знаки , и противоположны знакам свободных членов.
Для выделения базисных неизвестных из системы ограничений (30) необходима ее перестройка.
Полагая в (32) (или ) найдем из условий неотрицательности , и :
.
наибольшее значение . Тогда и систему (32) запишем в виде
(33)
Получили систему ограничений, имеющую допустимый вид: , и – базисные неизвестные, и – свободные неизвестные. Перейдем к процедуре шагов.
Шаг 1: положим в (33) и , тогда получим базисное решение , для которого целевая функция
(34)
примет значение .
В (5.15) коэффициент при положительный и для дальнейшего уменьшения значения f надо положить и наращивать .
Шаг 2: положим в (33) , а начнем наращивать так, чтобы , и оставались неотрицательными, т. е.
.
Откуда находим . Тогда . Объявив и свободными неизвестными, приведем (33) к допустимому виду:
(35)
Из (35) получим базисное решение . Для него
(36)
примет значение .
В (36) коэффициенты при свободных неизвестных положительны и дальнейшее уменьшение значения f невозможно: при . Задача решена.
Учитывая экономический смысл неизвестных, приходим к выводу.
Ежесуточная диета, обеспечивающая необходимое количество питательных веществ, состоит из единиц продукта , единиц продукта и ее минимальная стоимость единиц. При этом потребности организма в питательных веществах A и B отвечают требуемым минимальным объемам единиц и единиц соответственно (т.к. и ), а потребности в питательном веществе С больше требуемого минимального объема единиц на единиц.
В заключение рассмотрим вопрос: всегда ли после конечного числа шагов симплекс-метод закончится либо нахождением оптимального решения, либо установлением того факта, что задача не имеет решения.
Ответ утвердительный и содержится в следующей теореме.
Теорема. Если существует оптимальное решение ЗЛП, то существует и базисное оптимальное решение. Последнее всегда может быть получено с помощью симплекс-метода.
Дата добавления: 2015-02-03; просмотров: 1128;