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

Задачи математического и линейного программирования. Модели линейного программирования

Нередко экономические задачи имеют не единственное решение и требуется выбрать лучшее – оптимальное из них. Моделирование таких задач сводится к задачам математического программирования (ЗМП).

Математическое программирование – область математики, изучающая оптимизационные процессы посредством поиска экстремума функции при заданных ограничениях.

Сформулируем в общем виде ЗМП:

(3.1)

при условиях

(3.2)

(3.3)

где – целевая функция, условия (3.2) – специальные ограничения, условия (3.3) – общие ограничения ЗМП.

Точку , координаты которой удовлетворяют ограничениям (3.2) и (3.3), называют допустимым решением ЗМП.

Множество всех допустимых решений ЗМП называют допустимым множеством.

Допустимое решение , удовлетворяющее соотношению (3.1), называют оптимальным решением ЗМП.

Если в ЗМП целевая функция и функции , – линейные, то имеем общую задачу линейного программирования (ЗЛП):

(3.4)

(3.5)

(3.6)

В зависимости от вида специальных ограничений различают следующие ЗЛП:

- каноническая ЗЛП, включающая в качестве ограничений (3.5) только уравнения, т. е.

;

- стандартная ЗЛП, включающая в качестве ограничений (3.5) только неравенства, т. е.

Рассмотрим следующие примеры моделей, приводимых к ЗЛП.

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

На заводе имеются запасы трех видов сырья: , и , из которого можно наладить производство двух видов товаров: и . Запасы сырья, норма его расхода на производство единицы товаров, а также прибыль от реализации единицы каждого товара приведены в таблице 3.1 (цифры условные).

Таблица 3.1

Сырье Товары				Прибыль
Запасы

Необходимо составить такой план производства товаров, при котором прибыль от их реализации будет максимальной.

Решение. План производства зададим числами и , где – количество единиц товара , которое следует произвести . Неизвестные и должны удовлетворять условиям

или , (3.7)

(3.8)

Поясним смысл первого неравенства системы (3.7). В левой части записано количество сырья , которое расходуется на выпуск единиц товара и единиц товара . Это количество не должно превышать имеющегося запаса сырья , т. е. 126 единиц. Аналогичный смысл имеют второе и третье неравенства системы (3.7).

Прибыль, предприятия от реализации плана производства товаров, очевидно, составит

. (3.9)

В интересах предприятия максимизировать эту прибыль. Следовательно, чтобы составить план производства товаров, при котором прибыль от их реализации будет максимальной нужно решить стандартную ЗЛП: при условиях (3.7) и (3.8):

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

Имеются два вида продуктов: и . Содержание в 1 кг питательных веществ A, B и C, ежесуточные потребности организма V в них и стоимость S 1 кг продуктов приведены в таблице 3.2

Таблица 3.2

Витамины Продукты	A	B	C	S
V

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

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

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

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

Очевидно, и .

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

(3.10)

при условиях

(3.11)

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

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

(4.1)

при условиях

(4.2)

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

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

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

Например, четырехугольник на рис. 4.1 – выпуклое множество точек, а на рис. 4.2 выпуклым не является

Рис. 4.1 Рис. 4.2

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

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

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

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

Рис. 4.3

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

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

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

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

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

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

.

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

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

Линия уровня перпендикулярна вектору набла и при увеличении a перемещается параллельно самой себе в направлении вектора набла как показано на рис. 4.4.

Рис. 4.4

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

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

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

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

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

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

Рис. 4.5 Рис. 4.6

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

По описанному алгоритму решим ЗЛП из предыдущей Лекции 3.

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

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

или

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

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

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

.

Рис. 4.7

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

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

или

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

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

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

.

Рис. 4.8

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

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

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

Изложим суть симплекс-метода на примере задач с 5 неизвестными.

Пусть ЗЛП приведена к виду

(5.1)

при ограничениях:

, (5.2)

где ,

. (5.3)

Про систему ограничений (5.2) говорят, что она имеет допустимый вид, если одни неизвестные выражаются через остальные , причем свободные члены этих выражений неотрицательны .

Неизвестные и называются базисными, а неизвестные – свободными.

Возможны два принципиальных случая:

1Å Все коэффициенты при свободных неизвестных в выражении для F неположительны: и . Тогда для всякого неотрицательного решения системы уравнений (5.2) имеем и , а потому

или .

Следовательно, базисное решение , , , , является оптимальными, т. е. задача решена.

2Å Имеется свободное неизвестное, коэффициент при котором в выражении для F положителен, а все коэффициенты при этом неизвестном в уравнениях (5.2) – неотрицательны.

Для определенности положим . Исходя из базисного решения, станем наращивать значение , не меняя . Тогда значения базисных неизвестных будут оставаться неотрицательными:

,

а значение будет неограниченно возрастать, т. е. и задача решения не имеет.

Решения ЗЛП редуцируются к одному из случаев 1Å или 2Å путем перехода к новому базису, в котором целевая функция не уменьшит своего значения для базисного решения, а новая система ограничений должна иметь допустимый вид. Преобразование базиса и перестройку целевой функции и системы ограничений называют шагом в решении ЗЛП. Таким образом, сделав нужное число шагов, решают ЗЛП (5.1) – (5.3).

Применим симплекс-метод к первой задаче, рассмотренной в Лекции 4.

I. Основная задача в примере 1имеет вид

Сначала приведем ее к каноническому виду, вводя балансовые неизвестные , и :

(5.4)

(5.5)

Теперь приведем (5.4) к допустимому виду – неизвестные , и выразим через и , при этом свободные члены в правых частях полученных уравнений неотрицательны:

(5.6)

Здесь , и – базисные неизвестные, а и – свободные неизвестные.

Шаг 1: положим в (5.6) и , тогда , , . Получим неотрицательное решение системы уравнений (5.6). Его называют базисным решением. Для него .

Шаг 2: положим в (5.6) , а начнем наращивать так, чтобы , и оставались неотрицательными, т. е.

.

Решая эти неравенства, найдем наименьшее значение . Тогда . Объявив и свободными неизвестными, приведем (5.6) к допустимому виду:

(5.7)

Получим неотрицательное решение системы уравнений (5.7). Для него

(5.8)

примет значение .

Сделаем выводы.

Во-первых, значение F по сравнению с 1-ым шагом увеличилось.

Во-вторых, в (5.8) коэффициент при отрицательный и для дальнейшего увеличения значения F надо положить и наращивать .

Шаг 3: положим в (5.7) , а начнем наращивать так, чтобы , и оставались неотрицательными, т. е.

.

Откуда находим наименьшее значение . Тогда . Объявив и свободными неизвестными, приведем (5.7) к допустимому виду: