Глава II. Модели линейного программирования 2 страница

(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), т. е. был найден допустимый базис. Зачастую поиск такого базиса довольно затруднителен. Рассмотрим следующий метод нахождения допустимого базиса, который называют методом искусственного базиса или М-методом.