![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
(5.9)
Получили неотрицательное решение системы уравнений (5.9). Для него
(5.10)
примет значение .
Сделаем выводы.
Во-первых, значение F по сравнению со 2-ым шагом увеличилось.
Во-вторых, в (5.10) оба коэффициента при свободных неизвестных отрицательны и дальнейшее увеличение значения F невозможно:
при . Задача решена. Учитывая экономический смысл неизвестных, приходим к выводу: предприятие получит наибольшую прибыль 1104 единиц при изготовлении 36 единиц товара
и 6 единиц товара
, при этом остатки ресурсов
и
равны нулю
, а остаток ресурса
равен 12 единицам.
Замечание. Просматривая шаги решенной ЗЛП, убеждаемся, что были последовательно перебраны вершины многоугольника решений (см. рис. 4.7 в Лекции 4): шаг 1 – вершина
, шаг 2 – вершина
, шаг 3 – вершина
, которая доставляет максимум целевой функции F.
Если решается ЗЛП, в которой требуется найти минимум целевой функции, то задачу либо сводят к рассмотренной выше задаче с целевой функцией , либо с помощью шагов приводят к одному из двух принципиальных случаев:
1Å Все коэффициенты при свободных неизвестных в выражении для F (5.1) неотрицательны: и
. Тогда базисное решение
является решением задачи.
2Å Имеется свободное неизвестное, коэффициент при котором в выражении для F (5.1) отрицателен, а все коэффициенты при этом неизвестном в уравнениях (5.2) – неотрицательны. Тогда задача решения не имеет.
Применим симплекс-метод ко второй задаче, рассмотренной в Лекции 3.
II. Основная задача в примере 2 имеет вид
Сначала приведем ее к каноническому виду, вводя балансовые неизвестные ,
и
:
(5.11)
(5.12)
Приведем ограничения (5.11) к допустимому виду. Как показано выше, в качестве базисных неизвестных следует выбирать такие неизвестные, каждая из которых входит только в одно из уравнений системы ограничений (5.11), при этом нет таких уравнений системы, в которые не входит ни одна из этих неизвестных, и каждая базисная неизвестная имеет тот же знак, что и свободный член.
Нетрудно видеть, что ,
и
не могут быть базисными неизвестными. Действительно,
(5.13)
и знаки ,
и
противоположны знакам свободных членов.
Для выделения базисных неизвестных из системы ограничений (5.11) необходима ее перестройка.
Полагая в (5.13) (или
) найдем из условий неотрицательности
,
и
:
.
наибольшее значение . Тогда
и систему (5.13) запишем в виде
(6.14)
Получили систему ограничений, имеющую допустимый вид: ,
и
– базисные неизвестные,
и
– свободные неизвестные. Перейдем к процедуре шагов.
Шаг 1: положим в (5.14) и
, тогда получим базисное решение
, для которого целевая функция
(5.15)
примет значение .
В (5.15) коэффициент при положительный и для дальнейшего уменьшения значения f надо положить
и наращивать
.
Шаг 2: положим в (5.14) , а
начнем наращивать так, чтобы
,
и
оставались неотрицательными, т. е.
.
Откуда находим . Тогда
. Объявив
и
свободными неизвестными, приведем (5.14) к допустимому виду:
(5.16)
Из (5.16) получим базисное решение . Для него
(5.17)
примет значение .
В (5.17) коэффициенты при свободных неизвестных положительны и дальнейшее уменьшение значения f невозможно: при
. Задача решена.
Учитывая экономический смысл неизвестных, приходим к выводу.
Ежесуточная диета, обеспечивающая необходимое количество питательных веществ, состоит из единиц продукта
,
единиц продукта
и ее минимальная стоимость
единиц. При этом потребности организма в питательных веществах A и B отвечают требуемым минимальным объемам
единиц и
единиц соответственно (т. к.
и
), а потребности в питательном веществе С больше требуемого минимального объема
единиц на
единиц.
В заключение рассмотрим вопрос: всегда ли после конечного числа шагов симплекс-метод закончится либо нахождением оптимального решения, либо установлением того факта, что задача не имеет решения.
Ответ утвердительный и содержится в следующей теореме.
Теорема. Если существует оптимальное решение ЗЛП, то существует и базисное оптимальное решение. Последнее всегда может быть получено с помощью симплекс-метода.
Симплекс-таблицы для решения задач линейного программирования. Метод искусственного базиса (М-метод)
Описанный в предыдущей Лекции 5 процесс решения ЗЛП симплекс-методом довольно трудоемкий и требует выполнения однообразных преобразований. Причем с возрастанием числа неизвестных растет и число шагов.
Оказывается, эти преобразования можно записать в виде последовательности однотипно заполненных таблиц, называемых симплекс-таблицами.
Изложим способ составления и преобразования таких таблиц на примерах первой и второй основных задач из Лекции 5.
I. Первая основная задача.
Для заполнения первой симплекс-таблицы необходимо переписать целевую функцию F и систему ограничений (5.4) в виде:
(6.1)
Заполним таблицу 6.1
Таблица 6.1
Базисные неизвестные | Свободные члены | ![]() | ![]() | ![]() | ![]() | ![]() |
![]() | ![]() | |||||
![]() | ||||||
![]() | ||||||
F | –25 | –34 |
В выражении для F выясняем, имеются ли в последней строке таблицы, кроме столбца «свободные члены», отрицательные числа. Если таковых нет, то задача решена. Если же есть, то выполняем преобразование: в столбце имеем
(из двух отрицательных чисел –25 и –34 выбирают меньшее по модулю), над этим элементом ищем положительные числа. Если таковых нет, то задача не имеет решения. В нашем случае над –25 есть три положительных числа: 1; 1 и 1.
Найдем
.
Элемент, стоящий на пересечении строки () и столбца (
), называем разрешающим. В нашем случае он равен 1. (Если разрешающий элемент равен числу
, то всю строку делят на разрешающий элемент m, чтобы получить 1). Неизвестная
вводится в базис, а неизвестная
выводится из него.
Заполняем вторую симплекс-таблицу. Строка () из первой таблицы становится в ней строкой (
). Далее преобразуем строки (
), (
) и (F) первой таблицы так, чтобы их элементы, стоящие в столбце (
), обратились в 0. С этой целью
1) вычтем элементы строки () из соответствующих элементов строки (
), и запишем полученные результаты в строку (
) второй таблицы;
2) вычтем элементы строки () из соответствующих элементов строки (
), и запишем полученные результаты в строку (
) второй таблицы;
3) умножим элементы строки () на 25, сложим с соответствующими элементами строки (F), и запишем полученные результаты в строку (F) второй таблицы.
В результате получим следующую симплекс-таблицу 6.2
Таблица 6.2
Базисные неизвестные | Свободные члены | ![]() | ![]() | ![]() | ![]() | ![]() |
![]() | ||||||
![]() | ![]() | –1 | ||||
![]() | –1 | |||||
F | –9 |
В строке (F) есть отрицательное число –9. Поэтому продолжим поиск оптимального решения. Над –9 есть три положительных числа: 1; 1 и 3.
Найдем
.
Элемент, стоящий на пересечении строки () и столбца (
) разрешающий и равен 1. Неизвестная
вводится в базис, а неизвестная
выводится из него.
Заполняем третью симплекс-таблицу. Строка () из второй таблицы становится в ней строкой (
). Далее преобразуем строки (
), (
) и (F) второй таблицы так, чтобы их элементы, стоящие в столбце (
), обратились в 0. С этой целью
1) вычтем элементы строки () из соответствующих элементов строки (
), и запишем полученные результаты в строку (
) третьей таблицы;
2) умножим элементы строки () на 3, вычтем из соответствующих элементов строки (
), и запишем полученные результаты в строку (
) третьей таблицы;
3) умножим элементы строки () на 9, сложим с соответствующими элементами строки (F), и запишем полученные результаты в строку (F) третьей таблицы.
В результате получим следующую симплекс-таблицу 6.3
Таблица 6.3
Базисные неизвестные | Свободные члены | ![]() | ![]() | ![]() | ![]() | ![]() |
![]() | –1 | |||||
![]() | –1 | |||||
![]() | –3 | |||||
F |
В строке (F) нет отрицательных чисел, кроме столбца «свободные члены». Получили оптимальное решение:
при ,
,
,
.
Замечание. Симплекс-таблицы удобнее «пристыковывать» друг к другу по вертикали, что позволяет не писать многократно заглавную строку.
II. Вторая основная задача.
Для заполнения первой симплекс-таблицы перепишем целевую функцию f (5.15) и систему ограничений (5.14), имеющую допустимый вид, следующим образом:
(6.2)
Заполним таблицу 6.4
Таблица 6.4
Базисные неизвестные | Свободные члены | ![]() | ![]() | ![]() | ![]() | ![]() |
![]() | –1 | |||||
![]() | ![]() | –3 | ||||
![]() | –8 | |||||
f | –16 | |||||
![]() | 1,125 | –0,375 | 0,125 | |||
![]() | 2,625 | 0,125 | –0,375 |
Окончание таблицы 6.4
![]() | 3,625 | –2,875 | 0,625 | |||
f | –5 | –1 |
Выясняем, имеются ли в последней строке таблицы, (f) кроме столбца «свободные члены», положительные числа. Если таковых нет, то задача решена. Если же есть, то выполняем преобразование: в столбце имеем
. Над этим элементом ищем положительные числа. Если таковых нет, то задача не имеет решения. В нашем случае над 40 есть три положительных числа: 3; 8 и 23.
Найдем
Элемент, стоящий на пересечении строки () и столбца (
) разрешающий и равен 8. Неизвестная
вводится в базис, а неизвестная
выводится из него. Все элементы строки (
) разделим на разрешающий элемент. Полученные результаты запишем в новую симплекс-таблицу в строке (
).
Преобразуем строки (), (
) и (f) первой таблицы так, чтобы их элементы, стоящие в столбце (
), обратились в 0. С этой целью
1) умножим элементы строки () на 3, вычтем из соответствующих элементов строки (
), и запишем полученные результаты в строку (
) второй таблицы;
2) умножим элементы строки () на 23, вычтем из соответствующих элементов строки (
), и запишем полученные результаты в строку (
) второй таблицы;
3) умножим элементы строки () на 40, вычтем из соответствующих элементов строки (f), и запишем полученные результаты в строку (f) второй таблицы.
В строке (f) нет положительных чисел, кроме столба «свободные члены». Получили оптимальное решение:
при ,
,
,
.
Замечание. Первая симплекс-таблица второй основной задачи была заполнена с учетом того, что система ограничений (5.11) была предварительно сведена к допустимому виду (5.14), т. е. был найден допустимый базис. Зачастую поиск такого базиса довольно затруднителен. Рассмотрим следующий метод нахождения допустимого базиса, который называют методом искусственного базиса или М-методом.
Дата публикования: 2014-11-03; Прочитано: 215 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!