Решение задач по линейному программированию

Решение задач по линейному программированию с примерами онлайн

 

Если у вас нету времени на решение задач по линейному программированию вы всегда можете попросить меня, вам нужно написать мне, и я вам помогу онлайн или в срок 1-3 дня всё зависит что там у вас за работа, вдруг она огромная! Чуть ниже размещён теоретический и практический материал, который вам поможет сделать работу если у вас много свободного времени и желания!

 

Возможно, вас также заинтересует эта ссылка:

Заказать работу по линейному программированию помощь в учёбе

 

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

Пишут так:

Решение задач по линейному программированию

Определенная таким образом задача называется задачей оптимизации. Множество Решение задач по линейному программированию называется допустимым множеством данной задачи, а функция Решение задач по линейному программированию - целевой функцией.

В подавляющем большинстве случаев точка Решение задач по линейному программированию задается набором из нескольких чисел:

Решение задач по линейному программированию
т.е. является точкой Решение задач по линейному программированию мерного арифметического пространства Решение задач по линейному программированию соответственно множество Решение задач по линейному программированию есть подмножество в Решение задач по линейному программированию

Очень многое зависит от того, в каком виде задается допустимое множество Решение задач по линейному программированию Во многих случаях Решение задач по линейному программированию выделяется из Решение задач по линейному программированию с помощью системы неравенств (нестрогих):

Решение задач по линейному программированию

где Решение задач по линейному программированию какие-то заданные функции в Решение задач по линейному программированию

Иначе говоря, Решение задач по линейному программированию есть множество точек Решение задач по линейному программированию удовлетворяющих системе неравенств (7.2).

В этом случае задача оптимизации приобретает следующий вид. Дана функция Решение задач по линейному программированию переменных Решение задач по линейному программированию и система неравенств (7.2). Требуется найти Решение задач по линейному программированию при условиях (7.2):

Решение задач по линейному программированию

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

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

Решение задач по линейному программированию

или их части, но это, впрочем, не обязательно.

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

Решение задач по линейному программированию

Тогда говорят о задаче линейного программирования. Линейное программирование оформилось как отдельный раздел прикладной математики в 1940 - 1950-х гг., когда выяснилось, что целый ряд задач из сферы планирования и управления может быть сформулирован в виде задач линейного программирования. Для решения таких задач разработаны эффективные методы, с одним из которых (так называемым симплекс-методом) мы познакомимся дальше. Подсчитано, что в настоящее время примерно 80 - 85 % всех решаемых на практике задач оптимизации относится к задачам линейного программирования.

В дальнейшем, вместо того чтобы одновременно рассматривать оба типа задач: Решение задач по линейному программированию будем рассматривать

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

Еще раз напомним, что в задаче оптимизации (7.1) множество Решение задач по линейному программированию называется допустимым; соответственно любая точка Решение задач по линейному программированию называется допустимым решением. Допустимое решение, дающее Решение задач по линейному программированиюРешение задач по линейному программированию называется оптимальным решением. Неравенства (7.2) называются ограничениями.

 

Возможно, вас также заинтересует эта ссылка:

 

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

 

Задача 1.

Задача о банке (пример заимствован из книги Дж. Синки "Управление финансами в коммерческом банке"

Пусть собственные средства банка в сумме с депозитами составляют 100 млн долл. Часть этих средств, но не менее 35 млн долл., должна быть размещена в кредитах. Кредиты являются неликвидными активами банка, так как в случае непредвиденной потребности в наличности обратить кредиты в деньги без существенных потерь невозможно.

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

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

  • 1) Решение задач по линейному программированию - балансовое ограничение;
  • 2) Решение задач по линейному программированию - кредитное ограничение;
  • 3) Решение задач по линейному программированию - ликвидное ограничение;
  • 4) Решение задач по линейному программированию

Цель банка состоит в том, чтобы получить максимальную прибыль от кредитов и ценных бумаг:

Решение задач по линейному программированию

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

Так как кредиты менее ликвидны, чем ценные бумаги, то обычно Решение задач по линейному программированию Мы пришли к задаче линейного программирования с ограничениями 1) ... 4) и целевой функцией Решение задач по линейному программированию которую требуется максимизировать.

 

 

Задача 2.

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

Рассмотрим простую математическую модель этой задачи

Пусть имеются два вида продуктов: Решение задач по линейному программированию содержащих питательные вещества Решение задач по линейному программированию В 1 кг продуктов Решение задач по линейному программированию содержится определенное количество питательных веществ того или иного вида. Эти сведения представлены в табл. 7.1.

Решение задач по линейному программированию

Кроме этих данных, нам известны: Решение задач по линейному программированию - ежесуточные потребности организма в питательных веществах Решение задач по линейному программированию (соответственно) и Решение задач по линейному программированию - стоимости 1 кг продуктов Решение задач по линейному программированию Требуется рассчитать количество Решение задач по линейному программированию продукта Решение задач по линейному программированию и количество Решение задач по линейному программированию продукта Решение задач по линейному программированию так, чтобы обеспечить необходимое количество питательных веществ при минимальных затратах на продукты. Очевидно, общая стоимость продуктов будет Решение задач по линейному программированию

Общее количество вещества Решение задач по линейному программированию в обоих видах продуктов равно Решение задач по линейному программированию Оно должно быть не меньше Решение задач по линейному программированию

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

Дана система

Решение задач по линейному программированию

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

Среди решений системы (7.3), удовлетворяющих дополнительно условиям неотрицательности:

Решение задач по линейному программированию

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

Решение задач по линейному программированию

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

 

Возможно, вас также заинтересует эта ссылка:

Контрольная работа по линейному программированию заказать

 

Задача 3.

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

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

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

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

Решение задач по линейному программированию

Математическая задача об использовании ресурсов состоит в отыскании значений неизвестных Решение задач по линейному программированию удовлетворяющих условиям:

Решение задач по линейному программированию

и максимизирующих функцию Решение задач по линейному программированию

 

Возможно, вас также заинтересует эта ссылка:

Помощь по линейному программированию онлайн

 

 

Задача 4.

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

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

Составим таблицу (табл. 7.2).

Решение задач по линейному программированию

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

Решение задач по линейному программированию

Аналогичное условие должно выполняться для Решение задач по линейному программированию

Решение задач по линейному программированию

Общее количество угля, доставленное в Решение задач по линейному программированию должно равняться Решение задач по линейному программированию Отсюда

Решение задач по линейному программированию

Аналогично получаем условия

Решение задач по линейному программированию

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

Решение задач по линейному программированию

Таким образом, приходим к следующей задаче. Дана система

Решение задач по линейному программированию

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

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

Из рассмотренных четырех примеров, казалось бы, только первые три подходят под общую схему задач математического программирования. Так, в четвертом примере не все ограничения неравенства; часть из них (а именно (7.5)) являются уравнениями. Однако случай уравнений легко свести к случаю неравенств: достаточно каждое уравнение Решение задач по линейному программированию заменить системой из двух неравенств Решение задач по линейному программированию Впрочем, сведение уравнений к неравенствам может быть осуществлено и более эффективным способом (см. ниже).

Дадим теперь общую формулировку задачи линейного программирования.

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

Решение задач по линейному программированию

Требуется решить задачу

Решение задач по линейному программированию

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

Решение задач по линейному программированию

- это вытекает из реального смысла чисел Решение задач по линейному программированию Будем называть эти условия тривиальными ограничениями.

Наиболее часто встречаются две разновидности задачи линейного программирования.

  • 1. Каноническая задача линейного программирования. В этом случае система Решение задач по линейному программированию помимо тривиальных ограничений (7.6), включает в себя только уравнения. Примером может служить транспортная задача линейного программирования.
  • 2. Стандартная задача линейного программирования. Это означает, что система Решение задач по линейному программированию состоит только из неравенств, в число которых входят тривиальные ограничения (7.6). Примерами могут служить рассмотренные выше задачи о банке, о диете, об использовании ресурсов.

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

Пусть дана стандартная задача линейного программирования -будем называть ее задачей Решение задач по линейному программированию

Решение задач по линейному программированию

где Решение задач по линейному программированию - заданная система линейных неравенств, включающая (7.6).

Пусть Решение задач по линейному программированию - число нетривиальных неравенств в системе Решение задач по линейному программированию Рассмотрим любое из этих неравенств:

Решение задач по линейному программированию

Введем новую дополнительную переменную Решение задач по линейному программированию и заменим неравенство (7.7) двумя ограничениями: уравнением

Решение задач по линейному программированию

и условием Решение задач по линейному программированию

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

дополнительные переменные Решение задач по линейному программированию называют обычно балансовыми.

Назовем задачей Решение задач по линейному программированию задачу Решение задач по линейному программированию при условиях Решение задач по линейному программированию

Сравнивая задачи Решение задач по линейному программированию нетрудно убедиться в их эквивалентности: любое оптимальное решение задачи Решение задач по линейному программированию дает оптимальное решение задачи Решение задач по линейному программированию если к значениям переменных Решение задач по линейному программированию добавить значения балансовых переменных. Обратно, любое оптимальное решение задачи Решение задач по линейному программированию если отбросить значения балансовых переменных, дает оптимальное решение задачи Решение задач по линейному программированию

В качестве примера сведения стандартной задачи к канонической можно привести задачу о диете.

Введя для первого неравенства системы (7.2) балансовую переменную Решение задач по линейному программированию для второго - Решение задач по линейному программированию для третьего неравенства - Решение задач по линейному программированию получим каноническую задачу:

Решение задач по линейному программированию

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

Пусть дана каноническая задача линейного программирования:

Решение задач по линейному программированию

Будем считать ее задачей Решение задач по линейному программированию

Применив к системе из двух уравнений (7.8) метод Гаусса, выделим базис неизвестных:

Решение задач по линейному программированию

Учитывая эти равенства, можно написать новое выражение для Решение задач по линейному программированию

Решение задач по линейному программированию

Рассмотрим теперь новую задачу линейного программирования, которую будем считать задачей Решение задач по линейному программированию

Решение задач по линейному программированию

Если эту стандартную задачу мы захотели бы свести к канонической, то пришлось бы ввести балансовые переменные Решение задач по линейному программированию и заменить систему (7.9) новой системой

Решение задач по линейному программированию

но тогда новая задача

Решение задач по линейному программированию

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

 

Возможно, вас также заинтересует эта ссылка:

Курсовая работа по линейному программированию заказать готовую онлайн

 

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

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

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

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

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

Доказательство теоремы 7.1 будет дано ниже.

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

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

принимает оптимальное значение данной задачи.

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

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

Указанный способ решения задачи линейного программирования, как правило, требует громоздких вычислений. В § 8.1 и 8.2 мы ознакомимся с так называемым симплекс-методом, представляющим собой целенаправленную процедуру перебора вершин.

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

Пусть точка Решение задач по линейному программированию имеет координаты Решение задач по линейному программированию Заменив последнюю координату Решение задач по линейному программированию нулем, получим точку Решение задач по линейному программированию Будем называть эту точку проекцией точки Решение задач по линейному программированию на координатную плоскость Решение задач по линейному программированию Аналогично определяется проекция точки Решение задач по линейному программированию на любую координатную плоскость. Например, проекция на координатную плоскость Решение задач по линейному программированию есть точка Решение задач по линейному программированию Вообще, сохранив любые Решение задач по линейному программированию координат точки Решение задач по линейному программированию и заменив остальные координаты нулями, получим проекцию точки Решение задач по линейному программированию на соответствующую координатную плоскость.

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

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

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

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

Решение задач по линейному программированию

Если Решение задач по линейному программированию то оставим неравенство (7.11) без изменения. Если же Решение задач по линейному программированию то, в зависимости от знака Решение задач по линейному программированию приведем его к виду Решение задач по линейному программированию (при Решение задач по линейному программированию либо Решение задач по линейному программированию Итак, любое из неравенств системы Решение задач по линейному программированию приводится к одному из трех видов

Решение задач по линейному программированию

где Решение задач по линейному программированию суть выражения вида

Решение задач по линейному программированию

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

Таким образом, система Решение задач по линейному программированию равносильна системе из трех блоков:

Решение задач по линейному программированию

Разумеется, при этом не исключено, что в системе (7.12), (7.13), (7.14) не будет одного или даже двух блоков. Это зависит от знаков чисел Решение задач по линейному программированию

Построим теперь систему неравенств с Решение задач по линейному программированию неизвестными Решение задач по линейному программированию следующим образом: для любого неравенства Решение задач по линейному программированию блока (7.12) и любого неравенства Решение задач по линейному программированию блока (7.13) напишем новое неравенство

Решение задач по линейному программированию

неравенства же блока (7.14) оставим без изменения. В итоге получится новая система

Решение задач по линейному программированию

неравенств с Решение задач по линейному программированию неизвестными Решение задач по линейному программированию Эта система выделяет из пространства Решение задач по линейному программированию выпуклую многогранную область Решение задач по линейному программированию

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

Поясним подробнее определение системы (7.15). Может случиться, что в системе из трех блоков (7.12), (7.13), (7.14) первый или второй блок отсутствует. Тогда в системе (7.15) будут только неравенства Решение задач по линейному программированию Если отсутствует блок (7.14), то в (7.15) будут только неравенства Решение задач по линейному программированию Наконец, если отсутствуют блоки (7.12), (7.14) или (7.13), (7.14), то системы (7.15) нет вовсе. Мы будем считать ее в этом случае тождественной, т.е. состоящей из неравенства Решение задач по линейному программированию (или точнее, из неравенства Решение задач по линейному программированию

Фактически мы должны доказать два утверждения.

  • А. Если от любого решения системы Решение задач по линейному программированию отбросить последнюю координату, то получим некоторое решение системы (7.15).
  • В. Для любого решения системы (7.15) можно найти такое значение неизвестного Решение задач по линейному программированию присоединив которое, получим решение исходной системы Решение задач по линейному программированию

Доказательство. Утверждение Решение задач по линейному программированию очевидно (если какой-нибудь набор значений неизвестных удовлетворяет системе Решение задач по линейному программированию то он удовлетворяет и системе (7.12), (7.13), (7.14); но тогда для этого же набора выполняются все неравенства системы (7.15)).

Докажем утверждение Решение задач по линейному программированию Сначала рассмотрим основной случай, когда в системе (7.15) имеется хотя бы одно неравенство Решение задач по линейному программированию Пусть

Решение задач по линейному программированию

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

получим некоторые числа Решение задач по линейному программированию Для них выполняются неравенства

Решение задач по линейному программированию

Мы видим, что каждое из чисел Решение задач по линейному программированию не больше, чем любое из чисел Решение задач по линейному программированию Но в таком случае обязательно найдется такое число Решение задач по линейному программированию которое заключено между всеми числами Решение задач по линейному программированию и всеми числами Решение задач по линейному программированию

Решение задач по линейному программированию

Отсюда следует, что набор значений неизвестных

Решение задач по линейному программированию

является решением системы (7.12), (7.13), (7.14), а следовательно, и (7.15).

В исключительном случае, когда в системе (7.12), (7.13), (7.14) отсутствует первый или второй блок, рассуждаем следующим образом. Если нет первого блока, в качестве Решение задач по линейному программированию можно взять любое число, удовлетворяющее условиям

Решение задач по линейному программированию

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

Решение задач по линейному программированию

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

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

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

Решение задач по линейному программированию

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

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

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

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

точек области Решение задач по линейному программированию проектирующихся в Решение задач по линейному программированию обязательно имеется вершина области Решение задач по линейному программированию

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

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

Решение задач по линейному программированию

Множество всех решений системы (7.16) есть либо отрезок Решение задач по линейному программированию либо лучи Решение задач по линейному программированию либо вся числовая прямая. Последнее невозможно, ибо это означало бы, что в системе (7.12), (7.13), (7.14) блоки (7.12) и (7.13) попросту отсутствуют, т.е. система неравенств Решение задач по линейному программированию состоит только из блока (7.14). Это, в свою очередь, означало бы, что в систему Решение задач по линейному программированию неизвестное Решение задач по линейному программированию реально не входит. Однако это, как было сказано ранее, противоречит тому, что по условию Решение задач по линейному программированию имеет вершины.

Итак, множество всех решений системы (7.16) есть либо Решение задач по линейному программированию

либо Решение задач по линейному программированию Покажем, что точка Решение задач по линейному программированию является вершиной области Решение задач по линейному программированию

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

Решение задач по линейному программированию а это противоречит сказанному выше о множестве решений системы (7.16).

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

Пусть теперь Решение задач по линейному программированию - какая угодно линейная функция. Хотя бы один из коэффициентов Решение задач по линейному программированию не равен нулю;

пусть, например, Решение задач по линейному программированию Перейдем тогда в пространстве Решение задач по линейному программированию к новым координатам по формулам

Решение задач по линейному программированию

или, что то же,

Решение задач по линейному программированию

Очевидно, любое линейное неравенство с переменными Решение задач по линейному программированию перепишется в виде линейного неравенства с Решение задач по линейному программированию поэтому выпуклая многогранная область Решение задач по линейному программированию в координатах Решение задач по линейному программированию превратится в выпуклую многогранную область Решение задач по линейному программированию в координатах Решение задач по линейному программированию При этом Решение задач по линейному программированию значит, по доказанному, Решение задач по линейному программированию достигает минимума в Решение задач по линейному программированию Теорема доказана.

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

Как и ранее, систему ограничений данной задачи обозначим через Решение задач по линейному программированию и соответствующую выпуклую многогранную область в Решение задач по линейному программированию - через Решение задач по линейному программированию

Выберем одну из неизвестных Решение задач по линейному программированию реально входящую в систему Решение задач по линейному программированию -но только не Решение задач по линейному программированию - и спроектируем Решение задач по линейному программированию на координатную плоскость Решение задач по линейному программированию Обозначим проекцию через Решение задач по линейному программированию а соответствующую систему неравенств в Решение задач по линейному программированию Снова выберем одну из неизвестных, реально входящую в Решение задач по линейному программированию - опять-таки не Решение задач по линейному программированию - и спроектируем Решение задач по линейному программированию на соответствующую координатную плоскость. Получим область Решение задач по линейному программированию И так далее, пока не придем к некоторой области Решение задач по линейному программированию в пространстве Решение задач по линейному программированию т.е. на числовой прямой, определенной с помощью некоторой системы линейных неравенств с одной переменной Решение задач по линейному программированию

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

Оптимальная вершина получается последовательным дополнением значения Решение задач по линейному программированию крайними значениями остальных переменных. В этом отношении нахождение оптимальной вершины полностью аналогично обратному ходу метода Гаусса.

Замечание. На самом деле можно показать, что в данном случае «нереальных» неизвестных не будет и процесс исключения состоит ровно из Решение задач по линейному программированию шагов. Действительно, при наличии «нереальных» неизвестных среди чисел Решение задач по линейному программированию - координат вершины имеются

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

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

Доказательство. Мы должны доказать два утверждения.

  • 1. Если Решение задач по линейному программированию имеет вершину, то Решение задач по линейному программированию не содержит прямых.
  • 2. Если Решение задач по линейному программированию не имеет вершин, то Решение задач по линейному программированию содержит прямую.

Докажем первое утверждение. Пусть существует вершина Решение задач по линейному программированию Рассуждая от противного, допустим, что Решение задач по линейному программированию содержит некоторую прямую Решение задач по линейному программированию Очевидно, Решение задач по линейному программированию (иначе Решение задач по линейному программированию не была бы вершиной Решение задач по линейному программированию Рассмотрим двумерную плоскость м (рис. 7.1), содержащую Решение задач по линейному программированию если Решение задач по линейному программированию - две точки на Решение задач по линейному программированию то Решение задач по линейному программированию состоит из всех точек вида Решение задач по линейному программированию Решение задач по линейному программированию - любые числа. Плоскость Решение задач по линейному программированию можно рассматривать как пространство Решение задач по линейному программированию с координатами Решение задач по линейному программированию Пересечение Решение задач по линейному программированию есть выпуклая многогранная (лучше сказать - многоугольная) область в Решение задач по линейному программированию действительно, любое линейное неравенство Решение задач по линейному программированию из числа тех, что задают Решение задач по линейному программированию после замены переменных Решение задач по линейному программированию линейными функциями от Решение задач по линейному программированию превращается в линейное неравенство относительно Решение задач по линейному программированию Итак, Решение задач по линейному программированию есть выпуклая многогранная область в Решение задач по линейному программированию имеющая вершину Решение задач по линейному программированию и содержащая прямую Решение задач по линейному программированию Непосредственно очевидно, что в Решение задач по линейному программированию такая область невозможна.

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

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

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

Завершим теперь доказательство теоремы 7.2. Так как множество Решение задач по линейному программированию имеет вершины, то оно не содержит прямых. Следовательно, подмножество Решение задач по линейному программированию для которого Решение задач по линейному программированию тоже не содержит прямых, а значит, Решение задач по линейному программированию имеет вершины. Остается показать, что любая вершина Решение задач по линейному программированию

является одновременно вершиной Решение задач по линейному программированию Предположим противное: Решение задач по линейному программированию вершина Решение задач по линейному программированию но не вершина Решение задач по линейному программированию Тогда найдутся такие точки Решение задач по линейному программированиюРешение задач по линейному программированию - внутренняя точка отрезка Решение задач по линейному программированию Так как Решение задач по линейному программированию - вершина Решение задач по линейному программированию не могут одновременно принадлежать Решение задач по линейному программированию Следовательно, из двух неравенств Решение задач по линейному программированию хотя бы одно должно быть строгим. Отсюда вытекает, что для любого числа Решение задач по линейному программированию из интервала (0, 1) выполняется неравенство

Решение задач по линейному программированию

С другой стороны, Решение задач по линейному программированию для некоторого Решение задач по линейному программированию так как Решение задач по линейному программированию - внутренняя точка отрезка Решение задач по линейному программированию Поэтому

Решение задач по линейному программированию

что противоречит полученному выше неравенству. Следовательно, всякая вершина множества Решение задач по линейному программированию является вершиной множества Решение задач по линейному программированию Теорема 7.2 доказана.

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

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

 

Возможно, вас также заинтересует эта ссылка:

РГР по линейному программированию расчетно графическая работа

 

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

Будем решать задачу линейного программирования (ЛП), заданную в стандартной форме. Рассмотрим ряд примеров.

 

 

Задача 7.1.

Решить задачу ЛП

Решение задач по линейному программированию

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

  • Решение:

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

Решение задач по линейному программированию
Шаг 2. Исключим переменную Решение задач по линейному программированию из предыдущей системы неравенств, а именно для каждого неравенства со знаком Решение задач по линейному программированию найдем неравенство с противоположным знаком и запишем сквозное неравенство. Получим систему из шести неравенств

Решение задач по линейному программированию

Из последней системы неравенств находим Решение задач по линейному программированию и Решение задач по линейному программированию Осталось определить значения неизвестных Решение задач по линейному программированию при которых достигаются экстремальные значения целевой функции Решение задач по линейному программированию

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

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

получилось из сквозного неравенства Решение задач по линейному программированию Подставляя найденное значение Решение задач по линейному программированию имеем Решение задач по линейному программированию откуда Решение задач по линейному программированию Теперь из выражения для целевой функции найдем Решение задач по линейному программированию так что окончательно Решение задач по линейному программированию

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

 

Возможно, вас также заинтересует эта ссылка:

Задачи по линейному программированию с решением

 

 

Задача 7.2.

Решить задачу ЛП

Решение задач по линейному программированию

  • Решение:

Шаг 1. Как и в примере 7.1, исключаем переменную Решение задач по линейному программированию Для этого выражаем ее из записи для целевой функции и

подставляем в остальные неравенства системы.

Решение задач по линейному программированию

На этом закончился первый шаг процедуры исключения неизвестных. На следующем этапе записываем сквозные неравенства. Шаг 2. Решаем неравенства относительно Решение задач по линейному программированию

Решение задач по линейному программированию

Легко видеть, что Решение задач по линейному программированию Вместе с тем целевая функция неограничена сверху и Решение задач по линейному программированию

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

 

 

Задача 7.3.

Решить задачу ЛП
Решение задач по линейному программированию

  • Решение:

Шаг 1. Находим переменную Решение задач по линейному программированию из выражения для целевой функции и подставляем во все неравенства.

Решение задач по линейному программированию

Шаг 2. Решаем неравенства относительно Решение задач по линейному программированию
Решение задач по линейному программированию
Очевидно, что в последней системе неравенств третье и пятое неравенства противоречат друг другу, поэтому исходная система ограничений несовместна.

Рассмотрим последний пример, когда решение существует, но достигается на грани соответствующего многогранника.

 

 

Задача 7.4.

Решить задачу ЛП

Решение задач по линейному программированию

  • Решение:

Шаг 1.

Решение задач по линейному программированию

Шаг 2.

Решение задач по линейному программированию

Шаг 3.

Решение задач по линейному программированию

Отсюда получим Решение задач по линейному программированию Следовательно, Решение задач по линейному программированию Очевидно, что Решение задач по линейному программированию достигается при значениях переменных Решение задач по линейному программированиюРешение задач по линейному программированию

При нахождении значений неизвестных, для которых достигается максимум целевой функции, мы сразу попадем на шаг 1, откуда ясно, что Решение задач по линейному программированию Подставляя Решение задач по линейному программированию в систему неравенств шага 1, получим такую систему:

Решение задач по линейному программированию

Отсюда получим двойное неравенство Решение задач по линейному программированию Наконец,

значение переменной Решение задач по линейному программированию находится из выражения для целевой функции: Решение задач по линейному программированию Таким образом,
Решение задач по линейному программированию
Полагая Решение задач по линейному программированию получим две вершины многогранника, в которых достигается максимум целевой функции:

Решение задач по линейному программированию

Подведем некоторые итоги. Пусть дана задача линейного программирования в стандартной форме:
Решение задач по линейному программированию
Геометрическое истолкование задачи (7.17), (7.18) состоит в том, что неравенства (7.17) задают выпуклое многогранное тело в пространстве Решение задач по линейному программированию на котором рассматривается экстремум целевой функции (7.18).

При обсуждении примеров в первой части § 7.3 задача (7.17), (7.18) рассматривалась как единое целое в пространстве Решение задач по линейному программированию основных переменных Решение задач по линейному программированию и параметра Решение задач по линейному программированию Иными словами, фигурную скобку в условиях (7.17) следует продлить и на целевую функцию (7.18). В этом пространстве геометрический образ задачи (7.17), (7.18) - это выпуклое многогранное тело Решение задач по линейному программированию Задача о нахождении диапазона значений функции Решение задач по линейному программированию - это задача о проектировании тела Решение задач по линейному программированию на ось Решение задач по линейному программированию В частности, поскольку проекция выпуклого замкнутого множества остается выпуклым и замкнутым, то множество значений Решение задач по линейному программированию либо пусто, либо ограничено, и тогда оно есть отрезок, либо неограничено, и тогда оно представляет собой луч Решение задач по линейному программированию или Решение задач по линейному программированию Отсюда понятно, как получились доказательства теорем 7.1 и 7.2.

 

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

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

Пусть область допустимых решений Решение задач по линейному программированию задается системой неравенств вида

Решение задач по линейному программированию

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

найти максимум (или минимум) Решение задач по линейному программированию на множестве Решение задач по линейному программированию а также точку, в которой достигается этот максимум (или минимум).

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

 

 

Графический метод состоит в следующем.

1. Строится множество Решение задач по линейному программированию всех допустимых решений.

2. Если Решение задач по линейному программированию то задача неразрешима.

3. Если Решение задач по линейному программированию то рассматриваются прямые уровня Решение задач по линейному программированию а при монотонном изменении Решение задач по линейному программированию При увеличении Решение задач по линейному программированию прямая Решение задач по линейному программированию смещается параллельно в направлении вектора Решение задач по линейному программированию Если Решение задач по линейному программированию - первая точка встречи прямой уровня с областью Решение задач по линейному программированию то прямая уровня Решение задач по линейному программированию при Решение задач по линейному программированию не имеет общих точек с Решение задач по линейному программированию откуда следует, что Решение задач по линейному программированию Аналогичным образом, если

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

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

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

  • 1. Решение задач по линейному программированию - полуплоскость;
  • 2. Решение задач по линейному программированию - область, ограниченная двумя параллельными прямыми.

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

Решение задач по линейному программированию

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

Графический метод позволяет избежать полного перебора вершин. Действительно, если из чертежа видно, что Решение задач по линейному программированию - единственная первая (или последняя) точка пересечения линии уровня с Решение задач по линейному программированию то незачем вычислять координаты других вершин, так как Решение задач по линейному программированию - единственное оптимальное решение. Для некоторых задач, однако, из чертежа не ясно, в какой именно точке линия уровня пересекает в первый раз допустимое множество. В этом случае необходимо найти координаты всех "подозрительных" на оптимальность вершин, вычислить для них значения целевой функции и выбрать из них вершины с оптимальным значением. Заметим, что могут оказаться две оптимальные вершины Решение задач по линейному программированию Тогда множество всех оптимальных решений Решение задач по линейному программированию - это отрезок Решение задач по линейному программированию

Пусть Решение задач по линейному программированию - оптимальное значение Решение задач по линейному программированию

Множество всех оптимальных решений Решение задач по линейному программированию является подмножеством линии уровня Решение задач по линейному программированию и задается системой линейных неравенств. Поэтому возможны лишь следующие случаи:

  • а) Решение задач по линейному программированию - точка на прямой уровня Решение задач по линейному программированию
  • б) Решение задач по линейному программированию - отрезок на прямой уровня Решение задач по линейному программированию
  • в) Решение задач по линейному программированию - луч, содержащийся в прямой Решение задач по линейному программированию
  • г) Решение задач по линейному программированию совпадает с прямой уровня Решение задач по линейному программированию

 

 

 

Рассмотрим теперь несколько примеров.

Пусть Решение задач по линейному программированию - квадрат, стороны которого параллельны осям координат. Каждая из его вершин может быть как точкой максимума, так и точкой минимума в зависимости от того, в какой четверти находится вектор Решение задач по линейному программированию (рис.7.2 - 7.5).

Решение задач по линейному программированию

Решим графическим методом задачу о банке из § 7.1:

Решение задач по линейному программированию

Построим в плоскости Решение задач по линейному программированию полуплоскости, заданные неравенствами 1) ... 5). Общая их часть (заштрихованный треугольник на рис. 7.6) - область Решение задач по линейному программированию допустимых решений. Построим вектор Решение задач по линейному программированию и прямую уровня, перпендикулярную вектору Решение задач по линейному программированию и проходящую через начало координат. Перемещая эту прямую параллельно в направлении вектора Решение задач по линейному программированию найдем последнюю точку пересечения прямой уровня и допустимого множества Решение задач по линейному программированию

Решение задач по линейному программированию

Найденная точка максимума находится на пересечении прямых 1 и 3. Ее координаты получаются решением следующей системы линейных уравнений:

Решение задач по линейному программированию

Итак, оптимальный портфель активов (точка максимума) имеет структуру Решение задач по линейному программированию Максимальная прибыль составит Решение задач по линейному программированиюРешение задач по линейному программированию

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

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

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

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

Решение задач по линейному программированию - цена продукта Решение задач по линейному программированию

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

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

Приходим к задаче линейного программирования:

Решение задач по линейному программированию

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

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

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

Пусть, например, Решение задач по линейному программированию и

Решение задач по линейному программированию

а числа Решение задач по линейному программированию конкретно не указаны. Уравнения, отвечающие условиям (7.19), имеют вид
Решение задач по линейному программированию

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

1. Все три координаты Решение задач по линейному программированию равны нулю (система (7.23) -(7.25)), что дает вершину Решение задач по линейному программированию

2. Лишь одна координата равна нулю. Это приводит к вершинам:

Решение задач по линейному программированию

(система (7.21), (7.22), (7.23));

Решение задач по линейному программированию

(система (7.20), (7.22), (7.24));

Решение задач по линейному программированию

(система (7.20), (7.21), (7.25)).

3. Ровно две координаты равны нулю. Это дает вершины

Решение задач по линейному программированию (система (7.20), (7.24), (7.25));

Решение задач по линейному программированию (система (7.21), (7.23), (7.25));

Решение задач по линейному программированию

(система (7.22), (7.23), (7.24)).

4. Все три координаты отличны от нуля, что дает вершину

Решение задач по линейному программированию

(система (7.20), (7.21), (7.22)).

Итак, вершинами допустимого множества являются следующие точки: Решение задач по линейному программированию Поэтому максимальное значение

Решение задач по линейному программированию

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

 

 

Решение общей задачи линейного программирования

Симплекс-метод

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

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

Итак, рассмотрим задачу линейного программирования с ограничениями в форме уравнений. Даны система
Решение задач по линейному программированию

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

Решение задач по линейному программированию

Среди неотрицательных решений системы (8.1) нужно найти такое, которое минимизирует функцию (8.2).

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

Пример допустимой системы:

Решение задач по линейному программированию

здесь свободные члены равны соответственно 5, 4 и 0. Можно ли привести систему уравнений к допустимому виду и как это сделать, рассмотрим в § 8.2.

Неизвестные в допустимом виде системы, которые выражены через остальные неизвестные, называются базисными, а весь набор этих неизвестных, который мы обозначим для краткости одной буквой Решение задач по линейному программированию - допустимым базисом; остальные неизвестные называются свободными. Например, в системе (8.3) допустимый базис образован неизвестными Решение задач по линейному программированию неизвестные же Решение задач по линейному программированию - свободные.

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

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

Решение задач по линейному программированию

а система ограничений приведена к виду (8.3), то новое выражение для Решение задач по линейному программированию будет

Решение задач по линейному программированию

Чтобы упростить дальнейшие записи, будем считать, что имеется всего 5 неизвестных Решение задач по линейному программированию и система ограничений приведена к допустимому виду с базисом Решение задач по линейному программированию

Решение задач по линейному программированию

а целевая функция - к виду

Решение задач по линейному программированию

Напомним, что решается задача о минимизации Решение задач по линейному программированию при ограничениях (8.4) и условиях Решение задач по линейному программированию

Положим все свободные неизвестные равными нулю

Решение задач по линейному программированию

и найдем из системы (8.4) значения базисных неизвестных:

Решение задач по линейному программированию

Полученное таким путем решение системы (8.4)

Решение задач по линейному программированию

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

 

 

Возможны три случая.

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

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

Пусть, например, Решение задач по линейному программированию Будем тогда, отправляясь от базисного решения (8.6), наращивать значение Решение задач по линейному программированию (не меняя Решение задач по линейному программированию Значения базисных неизвестных также будут меняться; мы получим

Решение задач по линейному программированию

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

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

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

Опишем конкретно содержание шага. Пусть, например, Решение задач по линейному программированию отрицательны, а Решение задач по линейному программированию - положительно или равно 0:

Решение задач по линейному программированию

Если снова, как в случае II, наращивать значение Решение задач по линейному программированию то будем иметь

Решение задач по линейному программированию

Поскольку Решение задач по линейному программированию значения Решение задач по линейному программированию будут уменьшаться,

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

одно из неизвестных Решение задач по линейному программированию или Решение задач по линейному программированию обратится в нуль: для Решение задач по линейному программированию таким моментом будет Решение задач по линейному программированию а для Решение задач по линейному программированию будет Решение задач по линейному программированию Выберем из

этих отношении Решение задач по линейному программированию наименьшее; пусть, например, это будет - Решение задач по линейному программированию Тогда наращивание Решение задач по линейному программированию возможно только от 0 до Решение задач по линейному программированию

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

Решение задач по линейному программированию

для которого значение функции Решение задач по линейному программированию будет Решение задач по линейному программированию (поскольку Решение задач по линейному программированию

Таким образом, с ростом Решение задач по линейному программированию 'первым" из базисных неизвестных обращается в нуль неизвестное Решение задач по линейному программированию Это служит для нас сигналом к замене базиса Решение задач по линейному программированию а именно: из старого базиса удаляется неизвестное Решение задач по линейному программированию и вместо него в базис вводится неизвестное Решение задач по линейному программированию (из числа прежних свободных).

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

Решение задач по линейному программированию

и подставляем это выражение для Решение задач по линейному программированию в остальные два уравнения. В итоге получим систему вида

Решение задач по линейному программированию

с базисным решением

Решение задач по линейному программированию

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

Что же касается нового значения функции Решение задач по линейному программированию то оно равно

Решение задач по линейному программированию

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

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

Решение задач по линейному программированию

которое получается из (8.5) заменой неизвестного Решение задач по линейному программированию по формуле (8.9).

Если для полученной задачи (8.10), (8.13) снова имеет место случай III, то делаем следующий шаг, т.е. переходим к новому базису Решение задач по линейному программированию для

которого Решение задач по линейному программированию

Шаги повторяются до тех пор, пока не придем к одному из случаев I или П. Тогда процесс заканчивается.

 

 

Задача 8.1.

Решить задачу Решение задач по линейному программированию при условиях

Решение задач по линейному программированию

  • Решение:

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

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

Решение задач по линейному программированию

из которых меньшим является отношение Решение задач по линейному программированию отвечающее уравнению для Решение задач по линейному программированию

Производим замену базиса по схеме Решение задач по линейному программированию что означает: вместо Решение задач по линейному программированию в базис вводится Решение задач по линейному программированию Новый базис теперь состоит из

Решение задач по линейному программированию Чтобы осуществить соответствующую перестройку системы (8.14), нужно выразить эти неизвестные через Решение задач по линейному программированию

Начинаем с уравнения для Решение задач по линейному программированию из которого выражаем Решение задач по линейному программированию (новое базисное неизвестное):

Решение задач по линейному программированию

затем выражаем Решение задач по линейному программированию

Решение задач по линейному программированию

Итак, задача приведена к виду

Решение задач по линейному программированию
(мы сохранили порядок уравнений в (8.14)) и

Решение задач по линейному программированию

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

Из третьего уравнения выражаем Решение задач по линейному программированию и подставляем это выражение в остальные уравнения и в функцию Решение задач по линейному программированию В итоге получим:

Решение задач по линейному программированию

Выкладки предоставляем читателю провести самостоятельно.

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

Решение задач по линейному программированию

является оптимальным, а искомый минимум Решение задач по линейному программированию равен - Решение задач по линейному программированию Итак,

оптимальное решение есть

Решение задач по линейному программированию

и Решение задач по линейному программированию Задача решена.

В разобранном примере 8.1 процесс закончился случаем Решение задач по линейному программированию т.е. нахождением оптимального решения. Однако встречается еще одна возможность окончания процесса - когда наступает случай II, тогда Решение задач по линейному программированию Разберем пример.

 

 

Задача 8.2.

Решить задачу Решение задач по линейному программированию при условиях

Решение задач по линейному программированию

  • Решение:

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

Решение задач по линейному программированию

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

 

 

Симплекс-таблицы

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

Описание симплекс-таблиц произведем на примере задачи (8.4), (8.5) из § 8.1, где требуется минимизировать функцию (8.5) при ограничениях (8.4) и условиях Решение задач по линейному программированию

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

Аналогичную работу следует проделать и с равенством (8.5):

Решение задач по линейному программированию

Теперь можно заполнить табл. 8.1.

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

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

Решение задач по линейному программированию

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

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

Пусть, наконец, среди чисел отмеченного столбца, кроме последнего числа, есть положительные. Это означает, что мы имеем случай III и, следовательно, должны сделать шаг. Например, как мы считали ранее, пусть Решение задач по линейному программированию (это означает, что Решение задач по линейному программированию

в точном соответствии с

предположением (8.7). В этом случае описанная ранее методика предписывает составить отношения

Решение задач по линейному программированию

и выбрать из них меньшее.

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

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

при помощи все того же метода Гаусса. А именно умножаем выделенную строку на такое число, чтобы на месте разрешающего элемента появилась единица (т.е. умножаем на Решение задач по линейному программированию - это соответствует тому, что первое из уравнений (8.20) разрешается относительно нового базисного неизвестного Решение задач по линейному программированию Полученную таким образом новую строку вписываем уже в новую таблицу - снова в виде первой строки. Затем к каждой из остальных строк табл. 8.1 прибавляем вновь полученную строку, умноженную на такое число, чтобы в клетке отмеченного столбца появился нуль - это соответствует исключению неизвестного Решение задач по линейному программированию из остальных уравнений, а также из выражения для Решение задач по линейному программированию

Преобразованные таким образом строки пишем в новую таблицу (табл. 8.2) на место прежних строк.

К новой таблице применяется та же процедура. В результате или находится оптимальное решение (случай I), или обнаруживается, что Решение задач по линейному программированию (случай II), т.е. целевая функция неограничена, или же производится следующий шаг (случай III) - получим новую таблицу (табл. 8.3) и т.д., пока процесс не остановится (случай I или II).

Вот как будет выглядеть при такой методике решение примера 8.1. Исходная таблица имеет вид (табл. 8.2).

Решение задач по линейному программированию

Заполнение табл. 8.3 начинается со строки Решение задач по линейному программированию (содержимое таблицы соответствует (8.15) и (8.16)).

Решение задач по линейному программированию

Следующая табл. 8.4 соответствует (8.17) и (8.18).

Решение задач по линейному программированию

В табл. 8.4 последняя строка (не считая свободного члена) не имеет положительных чисел. Значит, достигнуто оптимальное решение

Решение задач по линейному программированию

а минимум Решение задач по линейному программированию равен Решение задач по линейному программированию

Итак, подведем итог в виде следующего алгоритма.

 

 

Алгоритм работы по симплекс-методу

1. Выделяем исходный допустимый базис и заполняем первую таблицу.

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

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

4. Пусть среди просмотренных в пункте 3 чисел имеются положительные. Для каждого из таких чисел Решение задач по линейному программированию составляем отношение

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

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

6. С новой таблицей возвращаемся к выполнению пункта 2.

 

Работа с целевой функцией

При подготовке задачи линейного программирования к решению с помощью симплекс-метода приходится решать технический вопрос: как наиболее рационально найти выражение целевой функции Решение задач по линейному программированию через свободные неизвестные?

Пусть задача имеет вид

Решение задач по линейному программированию

Чтобы получить требуемое выражение для Решение задач по линейному программированию следует в равенстве (8.22) заменить Решение задач по линейному программированию по формулам (8.21). Осуществляя такую замену, находим

Решение задач по линейному программированию

После приведения подобных членов получим

Решение задач по линейному программированию

где, очевидно,

Решение задач по линейному программированию

Обозначим:

Решение задач по линейному программированию - вектор из "базисных" коэффициентов в равенстве (8.22),

Решение задач по линейному программированию - вектор свободных членов в (8.21),

Решение задач по линейному программированию - вектор из коэффициентов при Решение задач по линейному программированию в (8.21),

Решение задач по линейному программированию - вектор из коэффициентов при Решение задач по линейному программированию в (8.21).

Тогда предыдущие равенства перепишутся в виде

Решение задач по линейному программированию

Чтобы научиться правильно использовать эти формулы, запишем их так:

Решение задач по линейному программированию
и далее учтем, что Решение задач по линейному программированию - это столбец свободных членов из симплекс-таблицы, отвечающей (8.21), Решение задач по линейному программированию это столбец для переменной Решение задач по линейному программированию из той же симплекс-таблицы, Решение задач по линейному программированию - аналогичный столбец для Решение задач по линейному программированию Обозначим эти столбцы Решение задач по линейному программированию Тогда получим:

Решение задач по линейному программированию
Это и есть искомые формулы.

Обычно поступают так: над неизвестными Решение задач по линейному программированию в заглавной строке симплекс-таблицы пишут числа Решение задач по линейному программированию (коэффициенты из равенства (8.22)), а слева от базисных неизвестных пишут Решение задач по линейному программированию ("базисные" коэффициенты из (8.22)). Далее пользуются формулами (8.23) для заполнения последней строки таблицы (строки для Решение задач по линейному программированию (табл. 8.5).

Решение задач по линейному программированию

Разумеется, при переходе от первой симплекс-таблицы ко второй строка для Решение задач по линейному программированию получается сама собой (при помощи симплекс-алгоритма, описанного в конце § 8.2 - см. пункт 5 алгоритма). Но в принципе ее можно получить также и с помощью формул (8.23). Такой "двойной" способ нахождения последней строки можно использовать в качестве контроля вычислений.

 

 

Задача 8.3.

Решить задачу линейного программирования

Решение задач по линейному программированию

  • Решение:

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

Для заполнения последней строки таблицы можно воспользоваться формулами типа (8.23) (точка означает скалярное умножение):

Решение задач по линейному программированию
Решение задач по линейному программированию

Следовательно, последняя строка табл. 8.6 выглядит следую щим образом:
Решение задач по линейному программированию

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

 

 

Метод искусственного базиса. Двухфазный симплекс-метод

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

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

Решение задач по линейному программированию

Свободные члены Решение задач по линейному программированию уравнений будем считать неотрицательными: если это условие не выполняется, например, если Решение задач по линейному программированию то, умножив обе части первого уравнения на -1, получим уравнение, в котором свободный член больше 0. Итак, пусть

Решение задач по линейному программированию

Наряду с задачей (8.24) ... (8.26), которую будем считать исходной, рассмотрим другую задачу линейного программирования: при ограничениях

Решение задач по линейному программированию

и условиях

Решение задач по линейному программированию

минимизировать функцию

Решение задач по линейному программированию

Сформулированная задача является вспомогательной для основной задачи (8.24) ... (8.26) и служит для нахождения допустимого базиса. Неизвестными в ней являются Решение задач по линейному программированию При этом неизвестные Решение задач по линейному программированию называются искусственными, они образуют искусственный базис. Разумеется, если в системе уравнений (8.24) имеются одна или две базисные переменные, то число искусственных переменных можно уменьшить. В систему ограничений (8.28) включили выражение для целевой функции (8.26) в качестве дополнительного уравнения. Это не принципиально, но удобно, поскольку при симплексных преобразованиях сразу получается выражение для целевой функции исходной задачи.

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

Для решения задачи (8.28) - (8.30) можно воспользоваться симплекс-методом, поскольку указан допустимый базис. Таким базисом ввиду (8.28) является Решение задач по линейному программированию

При решении задачи могут представиться две возможности:

Решение задач по линейному программированию

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

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

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

Нахождение Решение задач по линейному программированию называют первой фазой решения задачи (8.24) - (8.26), а возможное его продолжение с целевой функцией Решение задач по линейному программированию - второй фазой, при этом сам метод - двухфазным симплекс-методом.

Прежде чем обратиться к примерам, сделаем одно замечание. Решая задачу (8.28) - (8.30), мы стремимся (если это возможно) получить оптимальное решение, в котором значения искусственных неизвестных равны нулю. Наилучший способ достичь этого -выбрать последовательность шагов таким образом, чтобы все искусственные неизвестные вышли из базиса, т.е. стали свободными. Тогда в базисном решении значения этих неизвестных и будут как раз нулями.

  • Таким образом, переходя при решении задачи (8.28) -(8.30) от одного базиса к другому, мы стараемся в первую очередь выводить из базиса одно искусственное неизвестное за другим. Возможны, впрочем, и такие (досадные) случаи, когда в процессе решения приходится заменять одно искусственное неизвестное на другое (выбор разрешающего элемента по-другому не получается). Но общим направлением вычислительного процесса во всех случаях остается постепенный вывод искусственных неизвестных из базиса.

 

 

Задача 8.4.

Решить задачу линейного программирования

Решение задач по линейному программированию

при условии Решение задач по линейному программированию и ограничениях

Решение задач по линейному программированию

  • Решение:

Приведем сначала задачу к канонической форме, введя две балансовые переменные Решение задач по линейному программированию Получим задачу:

Решение задач по линейному программированию

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

Решение задач по линейному программированию

при условии Решение задач по линейному программированию и ограничениях

Решение задач по линейному программированию

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

Заполняем симплекс-таблицу (табл. 8.7). При нахождении коэффициентов последней строки для целевой функции Решение задач по линейному программированию достаточно сложить уравнения (8.32), соответствующие искусственным переменным Решение задач по линейному программированию т.е. первое и третье уравнения. В последней строке имеются сразу три положительных числа 4, 3 и 1. Выбираем первое из них. Разрешающий элемент находится в столбце Решение задач по линейному программированию и строке Решение задач по линейному программированию Производим шаг, в результате которого искусственное неизвестное Решение задач по линейному программированию выходит из базиса, уступая в нем место неизвестному Решение задач по линейному программированию При этом мы можем вычеркнуть столбец Решение задач по линейному программированию из получающейся табл. 8.8, поскольку искусственная переменная Решение задач по линейному программированию стала свободной и для дальнейшего стала излишней.

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

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

базис не входят. Таблицу 8.9 - без столбцов Решение задач по линейному программированию - можно рассматривать как симплекс-таблицу для задачи (8.31), (8.32), причем в ней содержится оптимальное решение этой задачи:

Решение задач по линейному программированию

Поскольку нас интересуют непосредственно лишь значения неизвестных Решение задач по линейному программированию ответ запишется в виде

Решение задач по линейному программированию

 

 

 

Задача 8.5.

Решить задачу линейного программирования:

Решение задач по линейному программированию

  • Решение:

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

Решение задач по линейному программированию

Укажем без пояснения последовательность симплекс-таблиц 8.10 и 8.11 для соответствующей задачи. Разрешающие элементы выделяются пунктиром.

Решение задач по линейному программированию

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

Решение задач по линейному программированию

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

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

 

 

Задача 8.6.

Найти исходный базис для системы ограничений

Решение задач по линейному программированию

  • Решение:

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

Решение задач по линейному программированию

Выбирая разрешающий элемент в строке Решение задач по линейному программированию и столбце Решение задач по линейному программированию выполним шаг исключения. Получим табл. 8.13.

Решение задач по линейному программированию

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

Запишем уравнение, соответствующее строке Решение задач по линейному программированию

Решение задач по линейному программированию

Поскольку все неизвестные принимают только неотрицательные значения, данное уравнение имеет единственное решение:

Решение задач по линейному программированию

Получается, что данная система ограничений эквивалентна следующей:

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

В разобранных случаях фактически отсутствовала вторая фаза симплекс-метода. Рассмотрим пример, когда она имеется.

 

 

Задача 8.7.

Решить задачу линейного программирования

Решение задач по линейному программированию

  • Решение:

После введения балансовых переменных система ограничений (8.33) принимает вид:

Решение задач по линейному программированию

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

А именно среди правых частей неравенств вида «больше или равно» находим неравенство с наибольшей правой частью (в рассматриваемом примере это третье неравенство с правой частью 400). Все остальные неравенства такого типа преобразуются по правилу: в системе уравнений (8.35) из выделенного уравнения

следует вычесть почленно данное и записать вместо последнего. Тогда система (8.35) примет вид
Решение задач по линейному программированию
Поэтому достаточно ввести только одну искусственную переменную в третье уравнение, чтобы привести систему ограничений (8.36) к допустимому базису. Окончательно задача (8.33), (8.34) преобразуется к следующему виду:
Решение задач по линейному программированию
Поэтому первой фазой решения данной задачи будет решение (8.37)- (8.38). Начальной симплекс-таблицей будет табл. 8.14.
Решение задач по линейному программированию

В качестве разрешающего элемента удобно взять число 2 в строке Решение задач по линейному программированию и столбце Решение задач по линейному программированию Получим табл. 8.15.
Решение задач по линейному программированию

На втором шаге из базиса исключается искусственная переменная Решение задач по линейному программированию и вспомогательная целевая функция обращается в нуль. Поэтому можно вычеркнуть строку Решение задач по линейному программированию и столбец Решение задач по линейному программированию (табл. 8.16)- Это означает завершение первой фазы.

Решение задач по линейному программированию

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

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

Решение задач по линейному программированию

Решение задач по линейному программированию

Теорема о конечности симплекс-алгоритма

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

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

Предположим теперь, что процесс продолжается без остановки, образуя бесконечную последовательность базисов

Решение задач по линейному программированию

для которых

Решение задач по линейному программированию

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

Решение задач по линейному программированию

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

Решение задач по линейному программированию

откуда следует в силу (8.40), что

Решение задач по линейному программированию

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

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

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

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

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

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

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

Условимся считать вектор

Решение задач по линейному программированию

положительным и записывать это

Решение задач по линейному программированию

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

Решение задач по линейному программированию

то мы скажем, что вектор Решение задач по линейному программированию больше, чем вектор Решение задач по линейному программированию (или что вектор Решение задач по линейному программированию меньше, чем вектор Решение задач по линейному программированию если разность Решение задач по линейному программированию есть положительный вектор. Другими словами, условие Решение задач по линейному программированию означает, что

Решение задач по линейному программированию

или же

Решение задач по линейному программированию

или же

Решение задач по линейному программированию

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

Решение задач по линейному программированию

Далее, если Решение задач по линейному программированию

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

Решение задач по линейному программированию

и линейная функция

Решение задач по линейному программированию

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

Исходным данным нашей задачи соответствует некоторая симплекс-таблица. Составим эту таблицу (табл. 8.19), а затем припишем к ней справа еще Решение задач по линейному программированию столбцов.
Решение задач по линейному программированию

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

Условимся называть базис положительным, если все векторы

Решение задач по линейному программированию

положительны в указанном ранее смысле. Разумеется, если все свободные члены Решение задач по линейному программированию положительны, то базис будет положительным независимо от того, какие числа стоят в приписанной части табл. 8.19. Однако если какое-либо из чисел Решение задач по линейному программированию равно нулю, то условие положительности базиса накладывает некоторое ограничение на числа Решение задач по линейному программированию первое из них, отличное от нуля, должно быть положительным. Таким образом, свойство базиса быть положительным может зависеть не только от самой системы ограничений (8.41), но и от приписанных чисел Решение задач по линейному программированию

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

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

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

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

Введем в рассмотрение еще один вектор Решение задач по линейному программированию

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

1) новый базис снова будет положительным;

2) новый вектор Решение задач по линейному программированию меньше, чем старый вектор Решение задач по линейному программированию

Решение задач по линейному программированию

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

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

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

Решение задач по линейному программированию

Если при этом Решение задач по линейному программированию Если же Решение задач по линейному программированию то

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

показывает, что новый базис является положительным. Наконец, заметим, что

Решение задач по линейному программированию

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

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

Решение задач по линейному программированию
Здесь матрица Решение задач по линейному программированию - единичная, а все числа последней строки равны нулю. Теорема доказана.

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

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

  • Рассчитываемая диета должна была включать 77 видов пищи. Формулировка задачи в терминах линейного программирования включала 9 уравнений с 86 неизвестными, из которых 9 были дополнительными. Оптимальное решение, конечно, удовлетворяло всем требованиям задачи.

Однако, поскольку симплекс-метод дает только базисное решение, оптимальная диета включала лишь 9 различных видов пищи (пшеничную муку, кукурузу, сгущенное молоко, растительное масло, сало, говяжью печень, капусту, картофель и шпинат). Ясно, что подобная диета не вполне отвечала бы требованиям вкуса и разнообразия пищи. Правильная постановка задачи должна, разумеется, учитывать и такие требования.