Методы оптимальных решений (стр. 2 )

Решение.

Пусть и – искомые количества продуктов и соответственно. Их стоимость составляет

Общее количество питательного вещества A в обоих видах продуктов равно . Оно должно быть не меньше 6 единиц: .

Аналогичные неравенства составим для питательных веществ B и C: и .

Очевидно, и .

Таким образом, получим следующую стандартную ЗЛП:

(16)

при условиях

(17)

Геометрический метод решения задач линейного программирования.

Геометрический метод решения ЗЛП – простой и наглядный способ решения стандартных ЗЛП с двумя переменными:

(18)

при условиях

(19)

Рассмотрим следующие геометрические объекты.

Выпуклые множества и их свойства.

Множество точек называется выпуклым, если оно вместе с произвольными двумя своими точками содержит весь отрезок, соединяющий эти точки.

Справедливо утверждение: пересечение любого числа выпуклых множеств есть выпуклое множество.

Каждое неравенство системы ограничений (19) геометрически определяет полуплоскость с граничной прямой , или , или .

Поясним сказанное. Рассмотрим, например, неравенство .

Посмотрим прямую L: (см. рис.2).

Рис. 2

Для того чтобы определить, какая полуплоскость удовлетворяет заданному неравенству, необходимо выбрать любую точку, не лежащую на L, и подставить ее координаты в неравенство. Если неравенство будет выполняться, то данная точка является допустимым решением, и полуплоскость, содержащая точку, удовлетворяет неравенству. Как правило, в качестве «пробной» берут точку .

Подставим в заданное неравенство: . Получим истинное утверждение. Следовательно, заданному неравенству соответствует нижняя полуплоскость (заштрихованная на рис. 2), содержащая точку .

Полуплоскости, описываемые неравенствами (19) – выпуклые множества. Их пересечение – область допустимых решений ЗЛП, которая является также выпуклым множеством.

Это множество называют также многоугольником решений. Он может быть точкой, отрезком, лучом, ограниченным или неограниченным многоугольником. (Случай вырождения, когда система ограничений (19) – пустое множество и ЗЛП не имеет решения, исключается).

Ввиду неравенств и многоугольник решений всегда находится в первом квадранте координатной плоскости .

Для нахождения экстремума целевой функции F воспользуемся вектором набла - градиентом F:

.

Он показывает направление наискорейшего изменения целевой функции F.

Прямая называется линией уровня функции F. Иными словами на множестве всех точек линии уровня функции F она сохраняет постоянное значение .

Алгоритм решения ЗЛП геометрическим методом.

1.  Строится многоугольник решений.

2.  Строится вектор набла, перпендикулярно ему проводятся линии уровня и при этом учитывают, что оптимальное решение ЗЛП находится в угловой точке многоугольника решений.

3.  Первая точка встречи линии уровня с многоугольником решений определяет минимум целевой функции.

4.  Последняя точка встречи линии уровня с многоугольником решений определяет максимум целевой функции.

5.  Если линия уровня параллельна одной из сторон многоугольника решений, то экстремум достигается во всех точках этой стороны . ЗЛП в этом случае имеет бесконечное множество решений.

6.  Для нахождения координаты точки экстремума решают систему из двух уравнений прямых, дающих в пересечении эту точку.

Пример 1. Экономико-математическая модель задачи о планировании производства.

Построим многоугольник решений. С этой целью запишем уравнения границ полуплоскостей из (17) в виде

или

«Пробная» точка удовлетворяет всем неравенствам из (17) и потому многоугольник решений расположен в нижних полуплоскостях, порожденных прямыми , и как показано на рис. 3

Построим вектор набла . Последней точкой встречи линии уровня с многоугольником решений будет точка (см. рис.3) с координатами: , , являющимися решениями системы уравнений

Подставив координаты точки в целевую функцию, найдем

Рис. 3

Пример 2. Экономико-математическая модель задачи о диете.

Построим многоугольник решений. С этой целью запишем уравнения границ полуплоскостей из (17) в виде

или

«Пробная» точка удовлетворяет всем неравенствам из (17) и потому многоугольник решений расположен в верхних полуплоскостях, порожденных прямыми , и как показано на рис. 4

Построим вектор набла . Первой точкой встречи линии уровня с многоугольником решений будет точка (см. рис. 4) с координатами: , , являющимися решениями системы уравнений:

Подставив координаты точки в целевую функцию, найдем

Рис. 4

Симплекс-метод для решения задач линейного программирования.

С увеличением числа неизвестных геометрический метод решения ЗЛП становится затруднительным при трех переменных и невозможным при большем числе переменных.

Поэтому был разработан универсальный метод решения ЗЛП – симплекс-метод, позволяющий решать ЗЛП в канонической форме.

Изложим суть симплекс-метода на примере задач с 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 отвечают требуемым минимальным объемам единиц и единиц соответственно (т. к. и ), а потребности в питательном веществе С больше требуемого минимального объема единиц на единиц.

В заключение рассмотрим вопрос: всегда ли после конечного числа шагов симплекс-метод закончится либо нахождением оптимального решения, либо установлением того факта, что задача не имеет решения.

Ответ утвердительный и содержится в следующей теореме.

Теорема. Если существует оптимальное решение ЗЛП, то существует и базисное оптимальное решение. Последнее всегда может быть получено с помощью симплекс-метода.

Симплекс-таблицы для решения ЗЛП.

Метод искусственного базиса (М-метод).

Описанный процесс решения ЗЛП симплекс-методом довольно трудоемкий и требует выполнения однообразных преобразований. Причем с возрастанием числа неизвестных растет и число шагов.

Оказывается, эти преобразования можно записать в виде последовательности однотипно заполненных таблиц, называемых симплекс-таблицами.

Изложим способ составления и преобразования таких таблиц на примерах первой и второй основных задач.

I.  Первая основная задача.

Для заполнения первой симплекс-таблицы необходимо переписать целевую функцию F и систему ограничений в виде:

Заполним таблицу

Базисные неизвестные	Свободные члены
	42	1	1	1	0	0
	48	1	2	0	1	0
	72	1	4	0	0	1
F	0	–25	–34	0	0	0

В выражении для F выясняем, имеются ли в последней строке таблицы, кроме столбца «свободные члены», отрицательные числа. Если таковых нет, то задача решена. Если же есть, то выполняем преобразование: в столбце имеем (из двух отрицательных чисел –25 и –34 выбирают меньшее по модулю), над этим элементом ищем положительные числа. Если таковых нет, то задача не имеет решения. В нашем случае над –25 есть три положительных числа: 1; 1 и 1.