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

Ответы на вопросы по заказу заданий по линейному программированию:

Сколько стоит помощь?

• Цена зависит от объёма, сложности и срочности. Присылайте любые задания по любым предметам - я изучу и оценю.

Какой срок выполнения?

• Мне и моей команде под силу выполнить как срочный заказ, так и сложный заказ. Стандартный срок выполнения – от 1 до 3 дней. Мы всегда стараемся выполнять любые работы и задания раньше срока.

Если требуется доработка, это бесплатно?

• Доработка бесплатна. Срок выполнения от 1 до 2 дней.

Могу ли я не платить, если меня не устроит стоимость?

• Оценка стоимости бесплатна.

Каким способом можно оплатить?

• Можно оплатить любым способом: картой Visa / MasterCard, с баланса мобильного, google pay, apple pay, qiwi и т.д.

Какие у вас гарантии?

• Если работу не зачли, и мы не смогли её исправить – верну полную стоимость заказа.

В какое время я вам могу написать и прислать задание на выполнение?

• Присылайте в любое время! Я стараюсь быть всегда онлайн.

Содержание:

1. Ответы на вопросы по заказу заданий по линейному программированию:
2. Рассмотрим несколько примеров задач линейного программирования
3. Задача 1.
4. Задача 2.
5. Задача 3.
6. Задача 4.
7. Геометрия задачи линейного программирования
8. Примеры решения задачи линейного программирования путем последовательного исключения неизвестных
9. Задача 7.1.
10. Задача 7.2.
11. Задача 7.3.
12. Задача 7.4.
13. Графический метод решения задачи линейного программирования при малом числе переменных
14. Графический метод состоит в следующем.
15. Решение общей задачи линейного программирования
16. Задача 8.1.
17. Задача 8.2.
18. Симплекс-таблицы
19. Алгоритм работы по симплекс-методу
20. Работа с целевой функцией
21. Задача 8.3.
22. Метод искусственного базиса. Двухфазный симплекс-метод
23. Задача 8.4.
24. Задача 8.5.
25. Задача 8.6.
26. Задача 8.7.

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

Пишут так:

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

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

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

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

где какие-то заданные функции в

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

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

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