Основна задача лінійного програмування

Розглянуті питання з теми:

Вступ до навчальної дисципліни. Приклади застосування. Звичайні жорданови виключення. Геометрична інтерпретація. Застосування жорданових виключень у лінійній алгебрі. Модифіковані жорданови виключення. Основна задача лінійного програмування

Задачи исследования операций

Исследование операций (амер.: Operations research, англ.: Operational research) или ”наука об управлении” занимается методами принятия решений (или выбора способов действий) в управленческих задачах.

Сложность управленческих задач обуславливается:

а) взаимной зависимостью производственно-технических, коньюнктурно-коммерческих и прочих факторов современной экономики;

б) противоречивостью целей управления;

в) рассредоточенностью полномочий и ответственности за принимаемые решения;

г) неопределенностью внешних экономических факторов.

При решении любой конкретной задачи применение методов исследования операций предполагает:

а) всесторонний качественный и количественный анализ задачи организационного управления, выделение существенных факторов и их взаимосвязей;

б) построение математических моделей исследуемых процессов;

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

г) решение задач оптимизации в смысле выбранных критериев и в заданных ограничениях;

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

Характерные черты операционного подхода

Ориентация на принятие решения. Основные результаты анализа должны иметь непосредственное или полностью определенное отношение к выбору способа действий (т.е. стратегии или тактики).

Оценка на основе критериев экономической эффективности. Сравнение различных возможных вариантов действий должно основываться на количественных оценках, позволяющих однозначно определить полезность ожидаемого исхода для рассматриваемой задачи. Количественные оценки обычно предполагают использование таких величин как расходы, доходы, производительность, норма прибыли от дополнительных капитальных вложений, наличие денежных средств и т.д. В рекомендуемом решении должен быть достигнут оптимальный «баланс» всех этих нередко противоречивых факторов.

Доверие к математической модели. Процедуры обращения с упомянутыми выше параметрами должны быть определены точно и однозначно, т.е., опираясь на одни и те же данные, различные специалисты-аналитики должны получать одинаковые результаты.

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

Необходимость использования ЭВМ. Обусловлена сложностью используемых моделей и большим объемом данных, подлежащих обработке, а также громоздкостью вычислительных процедур.

Введение в линейное программирование

Ознакомление с методами исследования операций обычно начинают с изучения линейных моделей оптимизации, т.е. с рассмотрения задач, в которых функция цели (критерии оптимизации) и ограничения представляют собой линейные функции.

Такие задачи решаются методами так называемого «линейного программирования», где слово «программирование» понимается как планирование (поиск оптимальных стратегий).

Основные идеи линейного программирования (ЛП) были высказаны Л.В.Канторовичем в 1939 г. В 1947 г. те же идеи были опубликованы американцем Дж. Данцигом. Подходы к решению ЛП-задач, предложенные этими учеными, отличаются, и, хотя абсолютное большинство русскоязычной литературы по данному вопросу базируется на методах, получивших развитие под влиянием идей Л.В.Канторовича, в данном курсе лекций будут рассматриваться методы, следующие из работ Дж. Данцига, не требующие приведения задач к канонической форме и легко переносимые в вычислительную среду.

Идеи ЛП нашли широкое применение в связи с поиском оптимальных стратегий при решении задач, связанных с эффективным использованием ограниченных ресурсов: в промышленности, торговле, управлении военными операциями и т.п.

Рассмотрим упрощенный пример операционной модели, сводящийся к задаче линейного программирования.

Проблема «двух картошек»

Фирма специализируется на производстве картофельных полуфабрикатов и выпускает три различных продукта: дольки, кубики и чипсы, которые далее будем называть: продукт 1,2 и 3, соответственно.

Фирма может закупать картофель у двух различных поставщиков. При этом объемы продуктов 1,2 и 3 (в тоннах), которые можно получить из одной тонны картофеля, различаются по двум поставщикам (из-за различного размера, формы и т.д. исходного картофеля) и сведены в таблицу:

Продукт	1 поставщик	2 поставщик
	0.2	0.3
	0.2	0.1
	0.3	0.3

Из маркетинговых соображений следует, что за планируемый период можно реализовать на рынке: 1.8т, 1.2т и 2.4т продуктов 1,2 и 3, соответственно.

Относительная прибыль от переработки картофеля (разница стоимости всех видов продуктов, полученных из одной тонны сырья, и затрат на приобретение 1т картофеля) по первому поставщику составляет 5 денежных единиц, а по второму - 6.

Оказывается, из более высокой прибыли от закупки картофеля у 2-го поставщика вовсе не следует, что весь картофель нужно покупать у него.

Сформулируем задачу математически.

Пусть и - количества картофеля, которые будут закуплены у поставщиков 1 и 2, соответственно. Тогда и должны удовлетворять следующим неравенствам:

(1.1)

Оптимальными являются значения и , удовлетворяющие условиям (1.1), при которых относительная прибыль максимальна. Таким образом, задача оптимизации сводится к максимизации выражения

при наличии ограничений (1.1).

Все значения и , удовлетворяющие условиям (1.1), представлены на Рис. 1.1 заштрихованной областью.

Рис. 1.1.

Каждая из прямых , изображенных на Рис. 1.1, соответствует различным значениям и , приводящим к одному и тому же значению . Очевидно, в точке функция достигает максимального значения .

Обыкновенные жордановы исключения и их применение в линейной алгебре

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

Дж. Б. Данцигом в 1949 г. был сформулирован так называемый симплекс-метод решения задач линейного программирования - задач отыскания максимума (минимума) линейной функции при наличии ограничений в виде линейных неравенств или уравнений.

В вычислительных процедурах предложенного метода (и не только его) широко используется аппарат так называемых жордановых исключений (обыкновенных и модифицированных).

Обыкновенные жордановы исключения (ОЖИ)

Пусть рассматривается система

, (2.1)

из линейных форм с независимыми переменными . Эта система может быть записана в виде таблицы

		...		...
		...		...
...	.	.	.	.	.
		...		...
...	.	.	.	.	.
		...		...

(2.2)

Будем называть шагом обыкновенного жорданова исключения, произведенным над таблицей (2.2) с разрешающим элементом , с r -й разрешающей строкой и s ­м разрешающим столбцом, схематизированную операцию перемены ролями зависимой переменной и независимой , т.е. операцию решения уравнения

(2.3)

относительно , подстановки его во все остальные уравнения системы (2.1) и записи полученной системы в виде новой таблицы, аналогичной (2.2).

А именно, если , то из (2.3):

,

и

Полученная система может быть записана аналогично (2.2) в виде таблицы:

		...		...
		...		...
...	.	.	.	.	.
		...		...
...	.	.	.	.	.
		...		...

(2.4)

где , .

Таким образом, один шаг ОЖИ с разрешающим элементом переводит таблицу (2.2) в новую таблицу (2.4) по схеме, состоящей из следующих пяти правил:

1. Разрешающий элемент заменяется единицей.

2. Остальные элементы разрешающего столбца (s ­го) остаются без изменений.

3. Остальные элементы разрешающей строки (r -й) меняют лишь свои знаки.

4. Остальные элементы с координатами () вычисляются по формуле .

5. Все элементы новой таблицы делятся на разрешающий элемент , что в табл. (2.4) изображено символически делением всей таблицы на .

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

1. Элементы с координатами () вычисляются по формуле .

2. Остальные элементы разрешающего столбца (s ­го) делятся на .

3. Остальные элементы разрешающей строки (r -ой) делятся на .

4. Разрешающий элемент заменяется на .

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

Геометрический смысл

Каждый набор значений задает координаты точки евклидова n -мерного пространства Еⁿ, а уравнения

, определяют (n-1)-мерные гиперплоскости, проходящие через начало координат. Для каждой точки величина равна уклонению точки от плоскости , где уклонение - это расстояние, помноженное на величину (вес) .

В прямоугольной системе, заданной n ортогональными координатными плоскостями , каждая точка задается своими n уклонениями от всех координатных плоскостей (веса для них равны 1).

Один шаг ОЖИ с разрешающим элементом означает замену координатной плоскости новой плоскостью , вообще говоря, уже не ортогональной остальным координатным плоскостям, так что в наборе координат (уклонений) каждой точки пространства уклонение от координатной плоскости заменяется уклонением от новой координатной плоскости .

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

Применение жордановых исключений в линейной алгебре

Теорема Стейница. Если все линейные формы системы (2.1) линейно независимы (так что), то, произведя точно соответствующих шагов жордановых исключений, можно превратить все зависимых переменных в независимые (т.е. можно их все перебросить на верх таблицы).

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

		...			...
		...			...
...	.	.	.	.	...	.
		...			...
		...		0	...	0
...	.	.	.	.	.	.
		...		0	...	0

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

Обращение матриц

Пусть в системе (2.1) и матрица этой системы не вырождена. Тогда таблице (2.2) соответствует векторная форма .

Произведем над таблицей (2.2) последовательно шагов ЖИ для превращения всех зависимых переменных в независимые. Окончательная таблица после упорядочивания (если потребуется) строк и столбцов примет вид:

		...		...
		...		...
...	.	.	.	.	.
		...		...
...	.	.	.	.	.
		...		...

,

или в матричной форме , где, очевидно, .

Вычисление ранга матрицы

Для вычисления ранга прямоугольной матрицы достаточно составить таблицу вида (2.2) и с помощью ЖИ перебросить наверх максимально возможное количество зависимых переменных (пока не придем к таблице, вид которой показан в доказательстве теоремы Стейница).

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

Решение систем линейных алгебраических уравнений

Для решения системы линейных уравнений с неизвестными

, (2.5)

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

1 способ. Система (2.5) может быть записана в виде таблицы

		...
		...
...	.	.	.
		...

Проделав последовательно шагов ЖИ и упорядочив (если разрешающие элементы брались не по главной диагонали) строки и столбцы, получим:

		...
		...
...	.	.	.
		...

,

т.е. .

2 способ. Перепишем систему (2.5) в виде

		...
		...
...	.	.	.
		...

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

...	...

Примечание. Если ранг матрицы меньше , то второй способ решения приводит к таблице вида:

		...
		...
...	.	...	.	.
		...
	0	...	0
...	.	.	.	.
	0	...	0

Если хотя бы один из , , не равен нулю, то система (2.5) решений не имеет. В противном случае - множество решений.

3 способ. Метод Гаусса. Метод Гаусса отличается от предыдущего лишь тем, что после каждого шага ЖИ вычеркивают не только разрешающий столбец, но и разрешающую строку, выписывая отдельно выражение для соответствующего . На последнем шаге найдем значение одной из неизвестных, а значения остальных вычисляются последовательной подстановкой уже полученных неизвестных в выписанные выражения для (с конца к началу).

Основная задача линейного программирования (ОЗЛП)

Модифицированные жордановы исключения

В некоторых приложениях вычислительного аппарата жордановых исключений, например, в симплекс-методе (см. лекцию 4), важно, чтобы элементы разрешающей строки сохраняли знаки, а элементы разрешающего столбца изменяли их. В этих случаях вместо обыкновенных используются так называемые модифицированные жордановы исключения (МЖИ).

Запишем систему (2.1) в виде

, ,

или в виде таблицы

		...		...
		...		...
...	.	.	.	.	.
		...		...
...	.	.	.	.	.
		...		...

,

где для удобства обозначений положено

, , .

Один шаг МЖИ с разрешающим элементом означает переход к новой таблице

		...		...
		...		...
...	.	.	.	.	.
		...		...
...	.	.	.	.	.
		...		...

которая получается из предыдущей по правилам 1-5 ОЖИ, с тем лишь исключением, что правила 2 и 3 меняются ролями, а именно:

2. Остальные (кроме разрешающего) элементы разрешающей строки (r -й) остаются без изменений.

3. Остальные элементы разрешающего столбца (s ­го) меняют лишь свои знаки.

Примечание. Соответственно изменяются правила 2 и 3 алгоритма, ориентированного на машинную реализацию (см. Л2).

Доказательство справедливости полученного алгоритма МЖИ проводится аналогично доказательству перехода от таблицы (2.2) к (2.4).

Л3.2. Формулировка ОЗЛП

Дана линейная форма (целевая функция)

(3.1)

и задана система линейных неравенств (ограничений)