«С.С. Смородинский, Н.В. Батин ОПТИМИЗАЦИЯ РЕШЕНИЙ НА ОСНОВЕ МЕТОДОВ И МОДЕЛЕЙ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ Учебное пособие по курсу Системный анализ и исследование операций для студентов специальности ...»

Министерство образования Республики Беларусь

Учреждение образования

«Белорусский государственный университет

информатики и радиоэлектроники»

Кафедра информационных технологий автоматизированных систем

С.С. Смородинский, Н.В. Батин

ОПТИМИЗАЦИЯ РЕШЕНИЙ

НА ОСНОВЕ МЕТОДОВ И МОДЕЛЕЙ

МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ

Учебное пособие по курсу «Системный анализ и исследование операций»

для студентов специальности «Автоматизированные системы обработки информации»

дневной и дистанционной форм обучения Минск 2003 УДК 681.3 + 007 (075.8) ББК 32.97 я 73 С 51 Рецензент:

профессор кафедры «Математика и информатика»

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

С 51 Оптимизация решений на основе методов и моделей мат. программирования: Учеб. пособие по курсу «Систем. анализ и исслед. операций»

для студ. спец. «Автоматизир. системы обраб. информ.» дневн. и дистанц.

форм обуч. / С.С. Смородинский, Н.В. Батин. – Мн.: БГУИР, 2003. – 136 с.: ил.

ISBN 985-444-521-6.

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

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

УДК 681.3 + 007 (075.8) ББК 32.97 я © Смородинский С.С., Батин Н.В., ISBN 985-444-521-6 © БГУИР,

СОДЕРЖАНИЕ

Введение

1. ПОСТАНОВКА ЗАДАЧИ И ОСНОВНЫЕ ПОНЯТИЯ

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

1.1. Понятие математической модели. Математическая модель в задачах линейного программирования 1.2. Примеры задач линейного программирования 1.3. Графический метод решения задач линейного программирования 1.4. Приведение задач линейного программирования к стандартной форме

2. РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

НА ОСНОВЕ СИМПЛЕКС-МЕТОДА

2.1. Пример задачи линейного программирования: задача планирования производства 2.2. Принцип работы симплекс-метода 2.3. Определение начального допустимого решения 2.4. Определение оптимального решения на основе симплекс-таблиц 2.5. Решение задач линейного программирования средствами табличного процессора Excel 2.6. Анализ оптимального решения на чувствительность

3. РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

НА ОСНОВЕ МЕТОДОВ ИСКУССТВЕННОГО БАЗИСА

3.1. Назначение и принцип работы методов искусственного базиса 3.2. Двухэтапный метод 3.3. Анализ оптимального решения на чувствительность

4. РЕШЕНИЕ ЗАДАЧ ОПТИМИЗАЦИИ НА ОСНОВЕ МЕТОДОВ

ЛИНЕЙНОГО ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ

4.1. Назначение методов целочисленного программирования 4.2. Метод ветвей и границ

5. ТРАНСПОРТНЫЕ ЗАДАЧИ

5.1. Постановка задачи 5.2. Поиск допустимого решения 5.3. Поиск оптимального решения. Метод потенциалов 5.4. Транспортные задачи с неправильным балансом 5.5. Вырожденное решение

6. РЕШЕНИЕ ЗАДАЧ ОПТИМИЗАЦИИ НА ОСНОВЕ МЕТОДОВ

НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

6.1. Постановка задачи нелинейного программирования 6.2. Примеры задач нелинейного программирования 6.3. Решение задач нелинейного программирования. Градиентные методы.

Метод Франка-Вульфа 6.4. Решение задач нелинейного программирования средствами табличного процессора Excel

7. РЕШЕНИЕ ЗАДАЧ ОПТИМИЗАЦИИ НА ОСНОВЕ МЕТОДА

ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

7.1. Постановка задачи. Принцип работы метода динамического программирования 7.2. Примеры решения задач на основе метода динамического программирования

8. АНАЛИЗ И ОПТИМИЗАЦИЯ РЕШЕНИЙ

НА ОСНОВЕ МОДЕЛЕЙ МАССОВОГО ОБСЛУЖИВАНИЯ

8.1. Понятие системы массового обслуживания 8.2. Потоки заявок в СМО. Законы распределения интервалов времени между заявками и времени обслуживания 8.3. Типовой узел СМО. Классификация СМО 8.4. Параметры и характеристики СМО 8.5. Вероятности состояний СМО 8.6. Экономические характеристики СМО 8.7. Одноканальные СМО без ограничений на очередь 8.8. Многоканальные СМО без ограничений на очередь 8.9. СМО с ограничением на длину очереди 8.10. СМО без очереди 8.11. СМО с заявками с разным временем обслуживания 8.12. СМО с приоритетами 8.13. Многофазные СМО. Сети СМО 8.14. Замкнутые СМО

9. ПРИНЯТИЕ РЕШЕНИЙ В УСЛОВИЯХ РИСКА

И НЕОПРЕДЕЛЕННОСТИ

9.1. Понятия риска и неопределенности. Постановка задачи 9.2. Методы выбора решений в условиях риска и неопределенности Литература даже в сфере государственного управления решения, затрагивающие жизнь каждого из нас, теперь принимаются в соответствии с упорядоченными процедурами, которые значительно эффективнее приблизительных и произвольных методов прошлого. Благодаря этому удается избежать или по крайней мере смягчить последствия многих катастрофических ошибок».

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

ВВЕДЕНИЕ

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

Основное содержание курса «Системный анализ и исследование операций» связано с освоением процедур математического моделирования и оптимизации решений в задачах прогнозирования, планирования, диагностики, проектирования и управления. Моделирование становится основным инструментом исследования системного аналитика, который способен решать сложные системные задачи, включая задачи разработки, реализации, внедрения и сопровождения проектов различных уровней и назначения в различных областях науки, техники и экономики. Системный аналитик – это прежде всего комплексный специалист, который имеет следующие качества: 1) способен тщательно изучать объект моделирования и выполнять функции системного разработчика проекта; 2) ориентируется в современном математическом аппарате и умеет использовать его для моделирования и оптимизации решений с учетом всей доступной объективной и субъективной информации об объекте моделирования;

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

Системный аналитик выполняет основную работу практически на всех этапах операционного исследования: 1) постановка задачи операционного исследования; 2) определение конкурирующих стратегий достижения цели; 3) построение математической модели операции; 4) оценка эффективности конкурирующих стратегий; 5) выбор оптимальной или рациональной стратегии достижения цели; 6) проверка адекватности модели и внедрение оптимальной стратегии на практике. Этапы 2–5 операционного исследования возможно выполнить с использованием разнообразных перспективных компьютеризированных средств моделирования и оптимизации решений.

В учебном пособии рассматриваются основные разделы курса «Системный анализ и исследование операций»: решение задач оптимизации на основе методов и моделей линейного программирования (разделы 1–3, [1–4, 10, 13, 18]), методы, алгоритмы и процедуры линейного целочисленного программирования (раздел 4, [1, 3, 4]), методы, алгоритмы и процедуры решения транспортных задач (раздел 5, [1–4, 13]), решение задач оптимизации на основе методов нелинейного программирования (раздел 6, [1, 3, 4]), решение задач оптимизации на основе метода динамического программирования (раздел 7, [1–4]), методы анализа и оптимизации решений на основе моделей массового обслуживания (раздел 8, [1, 2, 5, 14]), методы анализа и оптимизации решений в условиях риска и неопределенности (раздел 9, [1–5, 6, 16, 19, 21]). Рекомендуемая литература включает также источники по теории принятия решений [6-8], методологическим и математическим основам системного анализа [9–11], перспективным методам экономико-математического моделирования и оптимизации решений [12–21].

1. ПОСТАНОВКА ЗАДАЧИ И ОСНОВНЫЕ ПОНЯТИЯ

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

Линейное программирование рассматривает задачи с линейной математической моделью. Это задачи, в которых требуется найти такие значения переменных X1, X2,..., Xn, при которых некоторая линейная функция от этих переменных принимает максимальное или минимальное значение:

при выполнении ограничений на переменные X1, X2,..., Xn, заданных линейными уравнениями или неравенствами:

Здесь p – количество ограничений, имеющих вид «не меньше», q – количество ограничений «равно», m – общее количество ограничений.

Функция (1.1) называется целевой функцией, а ограничения (1.2) – системой ограничений задачи.

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

В большинстве задач (но не всегда) требуется, чтобы переменные X1, X2,..., Xn принимали неотрицательные значения (ограничение на неотрицательность): Xj 0, j = 1,..., n. В некоторых задачах требуется, чтобы переменные принимали целочисленные значения (ограничение на целочисленность).

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

Любые значения переменных X1, X2,..., Xn, удовлетворяющие ограничениям задачи (1.2), называются допустимыми решениями (независимо от того, какое значение при этом принимает целевая функция). Большинство задач имеет бесконечно много допустимых решений. Все множество допустимых решений представляет собой область допустимых решений (ОДР).

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

1.2. Примеры задач линейного программирования Пример 1.1. Предприятие химической промышленности выпускает соляную и серную кислоту. Выпуск одной тонны соляной кислоты приносит предприятию прибыль в размере 25 ден. ед., выпуск одной тонны серной кислоты – 40 ден. ед. Для выполнения государственного заказа необходимо выпустить не менее 200 т соляной кислоты и не менее 100 т серной кислоты. Кроме того, необходимо учитывать, что выпуск кислот связан с образованием опасных отходов. При выпуске одной тонны соляной кислоты образуется 0,5 т опасных отходов, при выпуске одной тонны серной кислоты – 1,2 т опасных отходов. Общее количество опасных отходов не должно превышать 600 т, так как превышение этого ограничения приведет к выплате предприятием крупного штрафа.

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

Составим математическую модель задачи. Для этого введем переменные. Обозначим через X1 количество выпускаемой соляной кислоты (в тоннах), через X2 – количество серной кислоты.

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

X1 200. Аналогично составим ограничение, устанавливающее, что предприятие должно выпустить не менее 100 т серной кислоты: X2 100.

Составим ограничение на опасные отходы. При выпуске одной тонны соляной кислоты образуется 0,5 т опасных отходов; значит, общее количество опасных отходов при выпуске соляной кислоты составит 0,5X1 т. При выпуске серной кислоты образуется 1,2X2 т опасных отходов. Таким образом, общее количество опасных отходов составит 0,5X1 + 1,2X2 т. Эта величина не должна превышать 600 т. Поэтому можно записать следующее ограничение:

0,5X1 + 1,2X2 600.

Кроме того, переменные X1 и X2 по своему физическому смыслу не могут принимать отрицательных значений, так как они обозначают количество выпускаемых кислот. Поэтому необходимо указать ограничения неотрицательности): X1 0; X2 0.

В данной задаче требуется определить выпуск кислот, при котором прибыль будет максимальной. Прибыль от выпуска одной тонны соляной кислоты составляет 25 ден. ед.; значит, прибыль от выпуска соляной кислоты составит 25X1 ден. ед. Прибыль от выпуска серной кислоты составит 40X2 ден. ед. Таким образом, общая прибыль от выпуска кислот составит 25X1+40X2 ден. ед. Требуется найти такие значения переменных X1 и X2, при которых эта величина будет максимальной. Таким образом, целевая функция для данной задачи будет иметь следующий вид:

E = 25X1+40X2 max.

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

X 0,5X1 + 1,2X X1 0, X2 0.

В этой задаче имеется два ограничения «больше или равно» и одно ограничение «меньше или равно». Целевая функция подлежит максимизации.

Пример 1.2. Пусть в условиях примера 1.1 из-за ужесточения требований к экологической безопасности требуется свести к минимуму количество опасных отходов. В то же время необходимо учитывать, что для того, чтобы производство кислот было экономически целесообразным, необходимо получить прибыль не менее 20 тыс.

ден. ед.

Математическая модель такой задачи имеет следующий вид:

X 25·X1 + 40X X1 0, X2 0.

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

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

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

Как отмечено выше, ОДР – это множество значений переменных X1, X2,..., Xn, удовлетворяющих ограничениям (1.2). Таким образом, для задач с двумя переменными ОДР представляет собой множество точек (X1; X2), т.е. некоторую область на плоскости (обычно многоугольник). Для задач с тремя переменными ОДР представляет собой многогранник в пространстве, для задач с большим количеством переменных – некоторую область многомерного пространства. Можно доказать, что экстремум (минимум или максимум) целевой функции всегда достигается при значениях переменных X1, X2,..., Xn, соответствующих одной из угловых точек ОДР. Другими словами, оптимальное решение всегда находится в угловой точке ОДР. Поэтому задачу линейного программирования с двумя переменными можно решить следующим образом: построить ОДР на плоскости в системе координат (X1; X2), определить все угловые точки ОДР, вычислить значения целевой функции в этих точках и выбрать оптимальное решение.

Решим графическим методом задачу из примера 1.1 Решение показано на рис. 1.1.

Ограничение X1 200 задается вертикальной линией X1 = 200. Все точки (X1; X2), расположенные справа от этой линии, удовлетворяют ограничению X1 200, расположенные слева – не удовлетворяют. Ограничение X2 100 задается горизонтальной линией X2 = 100. Все точки, расположенные сверху от этой линии, удовлетворяют ограничению X2 100, расположенные снизу – не удовлетворяют.

Для построения линии, задающей ограничение 0,5X1 + 1,2X2 600, удобно записать его в виде равенства:

0,5X1 + 1,2X2 = 600. Выразим одну из переменных через другую: X2 = – 0,417X1 + 500. Это уравнение прямой.

Построим эту прямую. Она разбивает координатную плоскость на две полуплоскости. В одной из этих полуплоскостей находятся точки, удовлетворяющие ограничению, в другой – не удовлетворяющие. Чтобы найти полуплоскость, удовлетворяющую ограничению 0,5X1 + 1,2X2 600, подставим в него координаты любой точки, например, (0; 0). Для этой точки ограничение выполняется. Значит, она находится в полуплоскости, удовлетворяющей ограничению.

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

Рис. 1.1. Решение примера 1.1 графическим методом Оптимальное решение находится в одной из угловых точек ОДР (на рис. 1.1 они обозначены как A, B, C). Эти точки можно найти из построенного графика или путем решения соответствующих систем из двух уравнений.

Найдем значения целевой функции (1.4) в этих точках:

E(A) = 25·200 + 40·100 = 9000;

E(B) = 25·200 + 40·416,67 = 21 666,8;

E(C) = 25·960 + 40·100 = 28000.

Таким образом, оптимальное решение находится в точке C = (960; 100). Это означает, что предприятию следует выпустить 960 т соляной кислоты и 100 т серной кислоты. Прибыль при этом составит 28 000 ден. ед. Можно также найти количество опасных отходов, которое будет получено при производстве кислот: 0,5·960 + 1,2·100 = 600 т.

Решим графическим методом задачу из примера 1.2. Решение показано на рис. 1.2.

В данном случае ОДР имеет только две угловые точки (A и B). Найдем для них значения целевой функции (1.6):

E(A) = 0,5·200 + 1,2·375 = 550;

E(B) = 0,5·640 + 1,2·100 = 440.

Таким образом, оптимальное решение находится в точке B = (640; 100). Это означает, что предприятию следует выпустить 640 т соляной кислоты и 100 т серной кислоты. При этом образуется 440 т опасных отходов. Можно также найти прибыль от производства кислот: 25·640 + 40·100 = 20 000 ден. ед.

Рис. 1.2. Решение примера 1.2 графическим методом 1.4. Приведение задач линейного программирования к стандартной Для большинства методов решения задач линейного программирования требуется предварительно привести задачу к стандартной форме. Задача (или ее математическая модель) представлена в стандартной форме, если она соответствует следующим условиям:

• целевая функция подлежит максимизации;

• все ограничения имеют вид равенств;

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

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

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

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

X 'j X 'j'. На эти переменные накладываются ограничения неотрицательности: X 'j 0, X 'j' 0.

Приведем к стандартной форме задачу из примера 1.1. Из ограничений «больше или равно» необходимо вычесть избыточные переменные, к ограничению «меньше или равно» – прибавить остаточную переменную. Целевая функция задачи подлежит максимизации, и на все переменные накладывается ограничение неотрицательности; поэтому никаких других преобразований не требуется. Математическая модель задачи в стандартной форме будет иметь следующий вид:

X1 – X3 = X2 – X4 = 0,5X1 + 1,2X2 + X5 = Xj 0, j = 1,..., 5.

E = 25X1 + 40X2 max.

Здесь переменные X3 и X4 – избыточные, X5 – остаточная.

Примечание. Все переменные, которые вводятся в математическую модель для ее приведения к стандартной форме, имеют физический смысл. Так, в рассмотренном примере переменные X3 и X4 обозначают количество кислот, которое будет выпущено сверх государственного заказа. Переменная X5 обозначает, насколько количество опасных отходов, образующихся при производстве кислот, будет меньше максимально допустимой величины (600 т).

Приведем к стандартной форме задачу из примера 1.2. В ней имеются три ограничения «больше или равно». В каждое из них необходимо ввести избыточную переменную. Целевая функция задачи подлежит минимизации;

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

X1 – X3 = X2 – X4 = 25X1 + 40X2 – X5 = Xj 0, j = 1,..., 5.

–E = – 0,5·X1 – 1,2·X2 max.

2. РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

НА ОСНОВЕ СИМПЛЕКС-МЕТОДА

2.1. Пример задачи линейного программирования: задача Одной из наиболее распространенных практических задач, решаемых методами линейного программирования, является задача планирования производства при ограниченных ресурсах. Основной метод решения задач линейного программирования – симплекс-метод – будет рассмотрен на примере решения такой задачи.

Пример 2.1. Один из цехов машиностроительного предприятия выпускает изделия двух видов: корпуса и задвижки. Для производства этих изделий требуются три вида сырья: алюминий, сталь и пластмасса. На выпуск одного корпуса расходуется кг алюминия, 10 кг стали и 5 кг пластмассы. На выпуск одной задвижки расходуется кг алюминия, 5 кг стали и 20 кг пластмассы. Запасы ресурсов ограничены: за рабочую смену цех может израсходовать не более 200 кг алюминия, 250 кг стали и 500 кг пластмассы.

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

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

Для построения математической модели задачи введем переменные. Обозначим через X1 количество выпускаемых корпусов, через X2 – количество выпускаемых задвижек.

Составим ограничение на расход алюминия. На выпуск одного корпуса расходуется 20 кг алюминия; значит, расход алюминия на выпуск всех корпусов составит 20X1 кг. На выпуск задвижек будет израсходовано 5X2 кг алюминия. Таким образом, общий расход алюминия составит 20X1 + 5X2 кг. Эта величина не должна превышать 200 кг, так как цех не может израсходовать за смену свыше 200 кг алюминия. Поэтому можно записать следующее ограничение:

20X1 + 5X2 200.

Аналогично можно составить ограничение на расход стали:

10X1 + 5X и на расход пластмассы:

5X1 + 20X2 500.

Кроме того, переменные X1 и X2 по своему физическому смыслу не могут принимать отрицательных значений, так как они обозначают количество изделий. Поэтому необходимо указать ограничения неотрицательности:

X1 0, X2 0.

В данной задаче требуется определить количество выпускаемых изделий, при котором прибыль от их производства будет максимальной. Прибыль от выпуска одного корпуса составляет 100 ден. ед.; значит, прибыль от выпуска корпусов составит 100X1 ден. ед. Прибыль от выпуска задвижек составит 300X2 ден. ед. Таким образом, общая прибыль от выпуска всех изделий составит 100X1 + 300X2 ден. ед. Требуется найти такие значения переменных X1 и X2, при которых эта величина будет максимальной. Таким образом, целевая функция для данной задачи будет иметь следующий вид:

E = 100X1 + 300X2 max.

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

20X1 + 5X 5X1 + 20X X1 0, X2 0.

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

Эту задачу можно решить также графическим методом. Решение показано на Рис. 2.1. Решение примера 2.1 графическим методом Найдем значения целевой функции для угловых точек ОДР: E(O) = 100·0 + + 300·0 = 0, E(A) = 100·0 + 300·25 = 7500, E(B) = 100·4 + 300·24 = 7600, E(C) = = 100·10 + 300·0 = 1000. Таким образом, оптимальное решение находится в точке B = (4; 24). Это означает, что цех должен выпускать за смену 4 корпуса и 24 задвижки. Прибыль при этом составит 7600 ден. ед.

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

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

20X1 + 5X2 + X3 = 5X1 + 20X2 + X5 = Xj 0, j = 1,..., 5.

Здесь X3, X4, X5 – остаточные переменные. Их физический смысл будет показан в п. 2.4.

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

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

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

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

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

2. Определяется начальное допустимое решение (начальная угловая точка ОДР).

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

Реализация симплекс-метода существенно различается в зависимости от вида математической модели задачи. В данном разделе рассматривается реализация симплекс-метода для случая, когда математическая модель задачи состоит только из ограничений «меньше или равно», и целевая функция подлежит максимизации (как в примере 2.1). Реализация симплекс-метода для задач с математической моделью любого вида рассматривается в разделе 2.3. Определение начального допустимого решения В задаче, представленной в стандартной форме, количество переменных обычно больше, чем количество ограничений. Так, в стандартной форме для примера 2.1 имеются три ограничения (m = 3) и пять переменных (k = 5). Для определения начального решения k – m переменных принимаются равными нулю. Тогда в системе из m равенств остается m переменных (неизвестных); в этом случае их значения можно определить однозначно. Эти значения используются в качестве начального решения задачи. Переменные, значения которых принимаются равными нулю, называются небазисными, остальные – базисными. Количество базисных переменных (переменных, составляющих базис), всегда равно количеству ограничений (m).

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

Таким образом, базисные переменные принимают значения, равные правым частям ограничений.

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

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

Таким образом, в качестве начального допустимого решения (начальной угловой точки ОДР) принимается начало координат, т.е. решение, в котором все исходные переменные математической модели равны нулю: X1 = X2 =... = Xn = 0.

Если базисные переменные присутствуют не во всех ограничениях задачи, то решение X1 = X2 =... = Xn = обычно оказывается недопустимым (не соответствует системе ограничений). В этом случае начало координат не может использоваться в качестве начального допустимого решения (начальной угловой точки ОДР). Для поиска начального допустимого решения в таких случаях используются специальные методы (см. раздел 3).

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

Найдем начальное допустимое решение для примера 2.1. Для задачи, приведенной к стандартной форме (2.3), (2.4), в качестве базисных переменных следует выбрать переменные X3, X4, X5, так как каждая из них входит только в одно ограничение с коэффициентом, равным единице, и не входит в другие ограничения. Базисные переменные имеются во всех ограничениях задачи. Переменные X1 и X2 принимаются равными нулю, т.е. небазисными. Таким образом, начальное решение задачи следующее: X1 = 0, X2 = 0, X3 = 200, X4 = 250, X5 = 500.

Это решение является допустимым, так как значения X1 = X2 = 0 соответствуют системе ограничений (2.1).

Таким образом, в качестве начальной угловой точки ОДР выбрано начало координат.

Выбранное решение явно не является оптимальным, так как целевая функция E = 100X1 + 300X2 при этом равна нулю. По своему смыслу это решение означает, что никакие изделия не выпускаются.

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

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

1. Строится исходная симплекс-таблица. Общий вид симплекс-таблицы показан в табл. 2.1.

Симплекс-таблица строится по следующим правилам:

• в первой строке перечисляются все переменные задачи, как исходные (X1, X2,..., Xn), так и дополнительные, введенные при приведении к стандартной форме (Xn+1, Xn+2,..., Xk). Для задач, содержащих только ограничения «меньше или равно», дополнительные переменные Xn+1, Xn+2,..., Xk – это остаточные переменные;

• в первой колонке таблицы («Базис») перечисляются переменные, составляющие начальный базис задачи. Их количество всегда равно количеству ограничений. Для задач, содержащих только ограничения «меньше или равно», начальный базис состоит из остаточных переменных Xn+1, Xn+2,..., Xk. В этой же колонке указывается обозначение целевой функции E;

• в строке целевой функции указываются коэффициенты целевой функции с обратным знаком. Для переменных, не входящих в целевую функцию (например, для остаточных переменных Xn+1, Xn+2,..., Xk), указываются нули;

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

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

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

Исходная симплекс-таблица для примера 2.1 приведена в табл. 2.2.

2. Проверяется условие окончания решения задачи. Если в строке целевой функции (E-строке) все коэффициенты неотрицательны, это означает, что оптимальное решение найдено. В противном случае выполняется следующий шаг.

3. Определяется переменная для включения в базис. В качестве такой переменной выбирается переменная, которой соответствует максимальный по модулю отрицательный коэффициент в E-строке. Включение в базис (т.е. увеличение) такой переменной приводит к наиболее быстрому росту целевой функции.

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

Для рассматриваемого примера в базис необходимо включить переменную X2, так как ей соответствует максимальный по модулю отрицательный коэффициент E-строки (–300). Это означает увеличение выпуска задвижек. Из условия задачи и целевой функции видно, что увеличение выпуска задвижек приводит к более быстрому росту целевой функции, чем увеличение выпуска корпусов: выпуск каждой задвижки увеличивает целевую функцию (прибыль) на 300 ден. ед., а выпуск каждого корпуса – только на 100 ден. ед.

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

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

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

Найдем симплексные отношения для рассматриваемого примера: 200/5 = = 40, 250/5 = 50, 500/20 = 25. Минимальное симплексное отношение получено для последней строки, соответствующей базисной переменной X5. Значит, эта переменная исключается из базиса (становится равной нулю).

Такой способ определения переменной, исключаемой из базиса, имеет следующее обоснование. При включении в базис новой переменной ее значение увеличивается. Чтобы по-прежнему соблюдались ограничения (2.1), необходимо в каждом из ограничений уменьшать базисные переменные. Увеличение переменной, включаемой в базис, возможно только до тех пор, пока одна из базисных переменных не станет равной нулю. Минимальное симплексное отношение показывает, какая из базисных переменных первой уменьшается до нуля (т.е. исключается из базиса). Так, для рассматриваемого примера, при увеличении переменной X2 (т.е. при ее включении в базис) для соблюдения ограничений (2.1) необходимо уменьшать переменные X3, X4, X5. Например, при каждом увеличении переменной X2 на единицу необходимо уменьшать переменную X3 на 5, X4 – также на 5, X5 – на 20. Минимальное симплексное отношение показывает, что при увеличении X2 переменная X5 первой достигнет нулевого значения. Смысл симплексных отношений для данной задачи следующий: они показывают, что имеющегося запаса алюминия (200 кг) хватит на выпуск 40 задвижек, запаса стали (250 кг) – на 50 задвижек, запаса пластмассы (500 кг) – на 25 задвижек. Таким образом, запас пластмассы будет израсходован первым, поэтому из базиса исключается переменная X5. Ниже будет показано, что переменная X5 обозначает остаток запаса пластмассы.

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

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

5. Выполняется преобразование симплекс-таблицы по следующим правилам:

• в столбце «Базис» вместо переменной, исключенной из базиса на шаге 4, указывается переменная, включенная в базис на шаге 3;

• все элементы ведущей строки делятся на ведущий элемент;

• все элементы ведущего столбца (кроме ведущего элемента) заменяются нулями;

• все остальные элементы таблицы (включая E-строку и столбец «Решение») пересчитываются по «правилу прямоугольника». Этот пересчет выполняется следующим образом: ведущий и пересчитываемый элемент образуют диагональ прямоугольника; находится произведение ведущего и пересчитываемого прямоугольника; из этого произведения вычитается произведение элементов, образующих противоположную диагональ прямоугольника; результат делится на ведущий элемент.

Выполним пересчет симплекс-таблицы, приведенной в табл. 2.2. В столбце «Базис» X5 заменяется на X2. Все элементы ведущей строки делятся на ведущий элемент, равный 20. Ведущий столбец (X2) заполняется нулями. Все остальные элементы пересчитываются по «правилу прямоугольника». Например, коэффициент на пересечении E-строки и столбца X1 пересчитывается следующим образом: (20·(–100) – (–300)·5)/20 = –25. Коэффициент на пересечении строки X3 и столбца X5 пересчитывается следующим образом: (20·0 – 5·1)/20 = = – 0,25. Расчет этих элементов иллюстрируется рис. 2.2. Полученная симплекстаблица приведена в табл. 2.3.

Рис. 2.2. Примеры расчетов по «правилу прямоугольника»

Для рассматриваемого примера на шаге 5 получено следующее решение (табл. 2.3): X2 = 25; X3 = 75; X4 = 125;

X1 = X3 = 0 (так как переменные X1 и X3 – небазисные). Это решение соответствует угловой точке ОДР, обозначенной на рис.2.1 как A (X1 = 0; X2 = 25). Видно, что полученное решение (табл. 2.3) не является оптимальным, так как в E-строке имеется отрицательный элемент (–25). Поэтому алгоритм продолжается. Определяется переменная для включения в базис (шаг 3). Это переменная X1, так как только для этой переменной в E-строке содержится отрицательный элемент. Определяется переменная, исключаемая из базиса (шаг 4). Для этого вычисляются симплексные отношения: 75/18,75 = 4;

125/8,75 = 14,29; 25/0,25 = 100. Минимальное симплексное отношение соответствует переменной X3; она исключается из базиса. Таким образом, ведущий столбец – X1, ведущая строка – X3, ведущий элемент равен 18,75. Симплекс-таблица преобразуется по правилам, приведенным на шаге 5. Полученная симплекс-таблица показана в табл. 2.4.

Выполняется возврат к шагу 2 (проверка оптимальности полученного решения). Решение, полученное в табл. 2.4, оптимально, так как в E-строке нет отрицательных элементов.

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

Таким образом, для задачи из примера 2.1 получено следующее оптимальное решение: X1 = 4; X2 = 24; X3 = 0;

X4 = 90; X5 = 0; E = 7600. Значения переменных X1 = 4, X2 = 24 показывают, что цех должен выпускать за смену 4 корпуса и 24 задвижки. В этом случае будет получена максимальная прибыль в размере 7600 ден. ед. (значение целевой функции).

Остаточные переменные X3, X4, X5 также имеют физический смысл. Например, из системы ограничений (2.1) видно, что величина 20X1 + 5X2 представляет собой расход алюминия на выпуск всех изделий, а величина (правая часть ограничения) – имеющийся запас алюминия. Переменная X3 представляет собой разность этих величин, т.е. неизрасходованный остаток запаса алюминия. Так как X3 = 0, значит, весь запас алюминия ( кг) расходуется на выпуск изделий. Аналогично можно показать, что переменная X4 представляет собой неизрасходованный остаток стали, а X5 – пластмассы. Таким образом, остается неизрасходованным 90 кг стали (расход стали на выпуск всех изделий составит 250 – 90 = 160 кг). Неизрасходованный остаток пластмассы равен нулю, значит, все 500 кг пластмассы расходуются на выпуск изделий.

Примечания:

1. Смысл остаточных переменных (как и остальных переменных, используемых в математической модели) полностью зависит от постановки задачи.

2. По результатам решения задачи переменные X1 и X2 приняли целочисленные значения. Если бы они оказались дробными, то потребовалось бы использовать специальные методы (см.

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

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

Решим задачу из примера 2.1, используя табличный процессор Excel.

Предположим, что желательно получить результаты (значения переменных X1 и X2) в ячейках B2 и C2 (конечно, можно использовать и любые другие ячейки). В ячейках B3 и C3 введем коэффициенты целевой функции (100 и 300). В ячейке D3 введем формулу целевой функции:

=СУММПРОИЗВ(B2:C3;B2:C2) В ячейках B4 и C4 введем коэффициенты первого ограничения (на расход алюминия): 20 и 5. В ячейке D4 введем формулу этого ограничения:

=СУММПРОИЗВ(B4:C4;B2:C2) В ячейке F4 введем правую часть этого ограничения: 200.

Аналогично в ячейках B5 и C5 введем коэффициенты ограничения на расход стали (20 и 5), в ячейке D5 – формулу этого ограничения (=СУММПРО- ИЗВ(B5:C5;B2:C2)), в ячейке F5 – правую часть (250). В ячейках B6 и C6 введем коэффициенты ограничения на расход пластмассы (5 и 20), в ячейке D6 – формулу этого ограничения (=СУММПРОИЗВ(B6:C6;B2:C2)), в ячейке F6 – правую часть (500).

Примечание. Вводить описание математической модели в рабочий лист Excel можно и подругому. Например, для ввода целевой функции достаточно в любой ячейке указать формулу: = 100 · B2 + 300 · C2. Для ввода первого ограничения достаточно в одной из ячеек указать формулу = 20 · B2 + 5 · C2, а в другой – правую часть ограничения (200). Однако показанный выше способ позволяет при необходимости легко внести изменения в постановку задачи.

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

Рис. 2.3. Рабочий лист Excel для решения примера 2. Примечание. Подписи и обозначения на рабочем листе (X1, X2, ->, >= и т.д.), показанные на рис. 2.3, необязательны. Значения 0 в ячейках D3 - D6 получены автоматически для начальных значений переменных, равных нулю.

Для решения задачи из меню «Сервис» выберем элемент «Поиск решения». В поле «Установить целевую ячейку» указывается ячейка D3, где находится формула целевой функции. Используя переключатели, необходимо указать, что требуется установить ячейку D3 «равной максимальному значению» (так как целевая функция в этой задаче подлежит максимизации). В поле «Изменяя ячейки» указываются ячейки, в которых должны находиться значения переменных: B2:C2.

В области «Ограничения» указываются ограничения. Для начала их ввода требуется нажать кнопку «Добавить». На экран выводится окно «Добавление ограничения». В этом окне в поле «Ссылка на ячейку» указывается ячейка, в которой находится левая часть (формула) ограничения, а в поле «Ограничение» – правая часть ограничения (число или ссылка на ячейку, где находится правая часть ограничения). Чтобы задать первое из ограничений (на расход алюминия), требуется в поле «Ссылка на ячейку» указать ячейку D4, выбрать знак ограничения ( EТНР, то найденное решение принимается в качестве ТНР и выполняется переход к шагу 5; если E EТНР, то выполняется переход к шагу 5.

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

Применение метода ветвей и границ рассмотрим на следующем примере.

Пример 4.1. Предприятие выпускает панели для пультов управления двух видов: стандартные (для работы в обычных условиях) и специального исполнения (для работы при повышенных температурах). При изготовлении панелей используется пластмасса и алюминий. Для изготовления одной стандартной панели требуется 12, кг пластмассы и 8 кг алюминия; для изготовления одной панели специального исполнения – 7,2 кг пластмассы и 14,5 кг алюминия. Предприятие имеет 300 кг пластмассы и 400 кг алюминия. Прибыль предприятия от выпуска одной стандартной панели составляет 7 ден. ед., прибыль от выпуска одной панели специального исполнения – ден. ед. Требуется определить, сколько панелей каждого вида должно выпускать предприятие, чтобы получить максимальную прибыль.

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

Приведем задачу к стандартной форме:

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

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

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

Исходная задача (на рис. 4.1 она обозначена как задача 1) решается симплексметодом. Решение оказалось нецелочисленным: X1 = 11,89, X2 = 21,03. По условию задачи обе переменные должны принимать целочисленные значения. Для продолжения поиска оптимального решения выбирается любая из этих переменных, например, X1. В список решаемых задач включаются задачи 2 и 3. В задачу 2 входит ограничение X1 11, а в задачу 3 – ограничение X1 12. Смысл этих ограничений следующий:

• эти ограничения исключают из ОДР оптимальное, но нецелочисленное решение X = 11,89, X2 = 21,03, так как значение X1 = 11,89 не соответствует ни ограничению X1 11, ни ограничению X1 12. Таким образом, в ходе дальнейшего решения задачи исключается возврат к оптимальному, но нецелочисленному решению;

• эти ограничения не исключают из ОДР ни одного допустимого целочисленного решения, так как любое целочисленное значение X1 соответствует либо ограничению X1 11, либо ограничению X1 12.

Оценкой задач 2 и 3 является величина E = 272,46. Эта величина соответствует оптимальному (но нецелочисленному) решению задачи 1 (X1 = 11,89, X2 = 21,03). В задачах 2 и 3 из-за включения дополнительных ограничений (X1 11 для задачи 2, X1 12 для задачи 3) будет получено какое-то другое решение. Поэтому значения целевых функций в задачах 2 и 3 не могут быть больше, чем 272,46.

Так как задачи 2 и 3 имеют одинаковые оценки, для решения можно выбрать любую из них. Пусть выбрана задача 2. Она решается симплекс-методом. Решение также оказывается нецелочисленным. В список решаемых задач включаются задачи и 5 с оценкой 270,66. Для составления этих задач вводятся ограничения X2 21 и X 22. Эти ограничения имеют тот же смысл, что и ограничения, используемые при составлении задач 2 и 3 (см. выше).

Таким образом, в списке решаемых задач находятся три задачи: 3 (с оценкой 272,46), 4 и 5 (с оценкой 270,66). Для решения выбирается задача с максимальной оценкой. В данном случае это задача 3. При ее решении максимальное значение целевой функции может составить не более чем 272,46, а для задач 4 или 5 – не более Примечание. Важно обратить внимание, что оценка задачи показывает именно максимально возможное значение целевой функции этой задачи. Оценка задачи известна до того, как она будет решена. Действительное оптимальное решение задачи можно определить, только решив ее. Поэтому в рассматриваемом примере выбор задачи 3 не означает, что ее решение обязательно будет лучше, чем у задач 4 или 5.

Решение задачи 3 также оказывается нецелочисленным. В список решаемых задач включаются задачи 6 и 7 с оценкой 271,5.

В списке решаемых задач находятся четыре задачи: 4 и 5 (с оценкой 270,66), и 7 (с оценкой 271,5). Для решения можно выбрать любую из задач 6 или 7. Пусть выбрана задача 6. Ее решение оказалось нецелочисленным. В список решаемых задач включаются задачи 8 и 9 с оценкой 267,36.

В списке решаемых задач оказалось пять задач: 4 и 5 (с оценкой 270,66), 7 (с оценкой 271,5), 8 и 9 (с оценкой 267,36). Для решения выбирается задача 7. Она не имеет допустимых решений.

В списке решаемых задач осталось четыре задачи: 4 и 5 (с оценкой 270,66), 8 и 9 (с оценкой 267,36). Для решения можно выбрать задачу 4 или 5. Пусть выбрана задача 4. Ее решение оказалось целочисленным. Оно становится текущим наилучшим решением. Оценки задач 5, 8 и 9, находящихся в списке решаемых задач, сравниваются со значением целевой функции, полученным для целочисленного решения (EТНР = 266). Оценки всех задач лучше, чем величина EТНР. Это значит, что при решении этих задач могут быть получены лучшие решения, чем ТНР. Поэтому ни одна из задач не исключается.

В списке решаемых задач осталось три задачи: 5 (с оценкой 270,66), 8 и 9 (с оценкой 267,36). Для решения выбирается задача 5. Ее решение нецелочисленно. Значение целевой функции (E = 268,88) лучше, чем EТНР = 266. Поэтому в список решаемых задач включаются две новые задачи (10 и 11) с оценкой 268,66.

Таким образом, в списке решаемых задач находятся четыре задачи: 8 и 9 (с оценкой 267,36), 10 и 11 (с оценкой 268,88). Для решения необходимо выбрать задачу 10 или 11. Пусть выбрана задача 10. Ее решение нецелочисленно. Значение целевой функции (E = 268,62) лучше, чем EТНР = 266. Поэтому в список решаемых задач включаются две новые задачи (12 и 13) с оценкой 268,62.

В списке решаемых задач находятся пять задач: 8 и 9 (с оценкой 267,36), 11 (с оценкой 268,88), 12 и 13 (с оценкой 268,62). Для решения выбирается задача 11. Она не имеет допустимых решений.

В списке решаемых задач осталось четыре задачи: 8 и 9 (с оценкой 267,36), и 13 (с оценкой 268,62). Для решения можно выбрать задачу 12 или 13. Пусть выбрана задача 12. Ее решение оказалось целочисленным. Значение целевой функции (E = 268) лучше, чем EТНР = 266. Таким образом, получено лучшее решение, чем ТНР, найденное ранее в задаче 4. Полученное решение X1 = 10, X2 = 22 становится текущим наилучшим решением, а величина EТНР принимает значение 268. Кроме того, необходимо сравнить с новым значением EТНР оценки всех задач, имеющихся в списке решаемых задач. Оценки задач 8 и 9 (267,36) хуже, чем EТНР. Поэтому решать эти задачи не имеет смысла, так как их решение будет хуже, чем уже полученное целочисленное решение (ТНР). Задачи 8 и 9 исключаются из списка решаемых задач. Исключить задачу 13 нельзя, так как ее оценка (268,62) лучше, чем EТНР.

В списке решаемых задач остается одна задача: это задача 13. Она решается симплекс-методом. Ее решение нецелочисленно. Значение целевой функции (E = 265,19) хуже, чем EТНР. Поэтому включать в список решаемых задач новые задачи не требуется.

В списке решаемых задач не осталось ни одной задачи. Таким образом, получено оптимальное решение: X1 = 10, X2 = 22, E = 268. Это значит, что предприятию следует выпустить 10 стандартных панелей и 22 панели специального исполнения.

Прибыль предприятия в этом случае будет максимальной и составит 268 ден. ед.

Можно также определить, что неизрасходованный остаток запаса пластмассы составит 16,6 кг, а алюминия – 1 кг.

Примечание. Математические модели некоторых задач, составляемых в ходе поиска решения по методу ветвей и границ, можно упростить. Например, в задаче можно заменить ограничения X1 11 и X1 10 на одно ограничение: X1 10. В задаче 12 можно заменить ограничения X2 22 и X2 22 на X2 = 22. Аналогичные упрощения возможны и в задачах 8, 9, 11, 13.

X1 = 11, X2 = E = 268, X1 = 10, X2 =

5. ТРАНСПОРТНЫЕ ЗАДАЧИ

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

Общая постановка транспортной задачи следующая. Имеются M поставщиков некоторого товара. Количество товара, имеющееся у поставщиков, составляет A1, A2,..., AM единиц. Имеются N потребителей этого товара; их спрос составляет B1, B2,..., BN единиц. Сумма запасов товара, имеющихся у поставщиков, равна сумме величин спроса всех потребителей:

Известны затраты на перевозку единицы товара от каждого поставщика каждому потребителю (стоимости перевозок): Cij, i = 1,..., M, j = 1,..., N. Требуется составить оптимальный план перевозок, т.е. определить, сколько товара каждый поставщик должен доставлять каждому из потребителей, чтобы общие затраты на перевозки были минимальными. При этом, конечно, каждому потребителю должно быть доставлено необходимое количество товара.

Пример 5.1. С четырех складов (СК1, СК2, СК3, СК4) доставляется товар в три магазина (МГ1, МГ2, МГ3). На складе СК1 имеется 40 тонн товара, на складе СК2 – 50 тонн, на складе СК3 – 60 тонн, на складе СК4 – 30 тонн.

Магазину МГ1 требуется 60 тонн товара, магазину МГ2 – 80 тонн, магазину МГ3 – 40 тонн. Затраты (в ден. ед.), связанные с перевозкой одной тонны товара с каждого склада в каждый магазин, приведены в табл. 5.1.

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

Данную задачу можно представить как задачу линейного программирования. Для построения математической модели этой задачи введем переменные Xij, i = 1,..., 4, j = 1,..., 3, обозначающие количество товара, перевозимого с i-го склада в j-й магазин.

На складах имеется 180 единиц товара; магазинам требуется также 180 единиц товара. Поэтому для удовлетворения спроса всех магазинов потребуется вывезти со складов весь товар. Ограничения, выражающие это требование, имеют следующий X11 + X12 + X13 = X21 + X22 + X23 = X31 + X32 + X33 = X41 + X42 + X43 = 30.

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

X11 + X21 + X31 + X41 = X12 + X22 + X32 + X42 = X13 + X23 + X33 + X43 = 40.

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

Xij 0, i= 1,..., 4, j = 1,..., 3.

Целевая функция представляет собой затраты на выполнение всех перевозок:

+ 10X31 +4X32 +7X33 + 8X41 + 6X42 + 3X43 min.

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

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

• поиск оптимального решения, т.е. плана перевозок с минимальными затратами.

5.2. Поиск допустимого решения Имеется несколько методов поиска допустимого решения: метод северо-западного угла, метод минимального элемента, метод Фогеля [1, 4].

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

Метод минимального элемента реализуется следующим образом. Выбирается минимальная стоимость перевозки единицы груза, т.е. минимальный из коэффициентов целевой функции Cij, i = 1,..., M, j = 1,..., N. Если запас i-го поставщика превосходит спрос j-го потребителя (Ai > Bj), то спрос j-го потребителя полностью удовлетворяется за счет перевозок от i-го поставщика: Xij = Bj. При этом запас i-го поставщика уменьшается на величину Bj (Ai = Ai – Bj), а j-й потребитель исключается из дальнейшего рассмотрения, так как он уже получил необходимое количество товара (j-й столбец вычеркивается из расчетной таблицы). Если, наоборот, спрос j-го потребителя превосходит запас, имеющийся у i-го поставщика (Ai < Bj), то i-й поставщик перевозит весь имеющийся у него товар j-му потребителю: Xij = Ai. При этом спрос j-го потребителя уменьшается на величину Ai (Bj = Bj – Ai), а i-й поставщик исключается из дальнейшего рассмотрения, так как весь имеющийся у него запас израсходован (i-я строка вычеркивается из расчетной таблицы). В сокращенной расчетной таблице снова выбирается минимальная стоимость перевозок, и выполняются действия, аналогичные рассмотренным выше. Процесс продолжается, пока не будут распределены все запасы и удовлетворены все потребности.

Примечание. Если запас i-го поставщика оказывается равным спросу j-го потребителя (Ai = Bj), то из рассмотрения исключается или поставщик, или потребитель (но не оба вместе). Если исключается поставщик, то предполагается, что неудовлетворенный спрос потребителя составляет 0 единиц товара. Если исключается потребитель, то предполагается, что у поставщика остается запас товара в размере 0 единиц. Дальнейшие действия выполняются обычным образом согласно алгоритму метода минимального элемента. Подробнее такой случай рассмотрен в подразделе 5.5.

Рассмотрим поиск допустимого плана для примера 5.1. Наиболее дешевыми являются перевозки от второго поставщика третьему потребителю, т.е. со склада СК в магазин МГ3. Запас товара на складе СК2 составляет 50 тонн, а спрос магазина МГ – 40 тонн. Поэтому склад СК1 поставляет магазину МГ3 40 тонн товара. Запас товара на складе СК1 уменьшается на 40 тонн (на складе остается 10 тонн), а магазин МГ исключается из рассмотрения, так как для него уже запланирована перевозка необходимого количества товара (табл. 5.3).

В сокращенной расчетной таблице (см. табл. 5.3) выбирается минимальный элемент. Наиболее дешевыми являются перевозки со склада СК2 в магазин МГ2. Запас товара на складе составляет 10 тонн (так как для этого склада уже запланирована перевозка 40 тонн товара в магазин МГ3), а спрос магазина – 80 тонн. Поэтому склад СК2 поставляет магазину МГ2 весь имеющийся у него товар. Склад СК2 исключается из рассмотрения, а спрос магазина МГ2 уменьшается на 10 тонн (табл. 5.4).

В сокращенной расчетной таблице (см. табл. 5.4) минимальную стоимость имеют перевозки со склада СК1 в магазин МГ2. Запас товара на складе СК1 составляет 40 тонн, а спрос магазина МГ2 – 70 тонн (так как для этого магазина уже запланирована перевозка 10 тонн товара со склада СК2). Поэтому склад СК1 поставляет магазину МГ2 весь имеющийся у него товар. Склад СК1 исключается из рассмотрения, а спрос магазина МГ2 уменьшается на 40 тонн (табл. 5.5).

В сокращенной расчетной таблице (см. табл. 5.5) наиболее дешевыми являются перевозки со склада СК3 в магазин МГ2. Запас товара на складе СК3 составляет тонн, а спрос магазина МГ2 – 30 тонн. Поэтому склад СК3 поставляет магазину МГ 30 тонн товара. Запас товара на складе СК3 уменьшается на 30 тонн (на складе остается еще 30 тонн), а магазин МГ2 исключается из рассмотрения, так как для него уже запланирована перевозка необходимого количества товара (табл. 5.6).

В сокращенной расчетной таблице (см. табл. 5.6) минимальный элемент соответствует перевозкам со склада СК4 в магазин МГ1. Запас товара на складе СК4 составляет 30 тонн, а спрос магазина МГ1 – 60 тонн. Поэтому склад СК4 поставляет магазину МГ1 весь имеющийся у него товар. Склад СК4 исключается из рассмотрения, а спрос магазина МГ1 уменьшается на 30 тонн (табл. 5.7).

Запас товара (30 тонн) остается только на складе СК3. Такое количество товара требуется магазину МГ1 (для всех остальных магазинов уже запланированы необходимые перевозки). Поэтому склад СК3 поставляет магазину МГ1 30 тонн товара. На этом поиск допустимого решения завершается.

Полученный допустимый план перевозок приведен в табл. 5.8. Склад СК1 поставляет 40 тонн товара магазину МГ2; склад СК2 поставляет 10 тонн товара магазину МГ2 и 40 тонн – магазину МГ3; склад СК3 поставляет тонн товара магазину МГ1 и 30 тонн – магазину МГ2; склад СК4 поставляет 30 тонн товара магазину МГ1.

Другими словами, переменные приняли следующие значения: X12 = 40, X22 = 10, X23 = 40, X31 = 30, X32 = 30, X41 = 30; остальные переменные равны нулю. Общие затраты на перевозки составят 840 ден. ед.

Переменные, принявшие ненулевые значения, называются базисными, остальные (нулевые) – небазисными.

Если допустимый план перевозок составлен правильно, то количество базисных переменных всегда равно M + N – 1, где M – количество поставщиков, N – количество потребителей.

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

Рассмотрим поиск оптимального решения для примера 5.1.

1. Составляются уравнения для определения вспомогательных величин Ui и Vj, i = 1,..., M, j = 1,..., N:

где Cij – стоимости перевозок, соответствующие базисным переменным.

Количество таких уравнений равно M + N – 1 (т.е. равно количеству базисных переменных). Величины Ui называются платежами (или потенциалами) поставщиков, а Vj – платежами (потенциалами) потребителей.

Система уравнений (5.1) для рассматриваемого примера имеет следующий вид:

U3 + V1 = U4 + V1 = 8.

2. Из системы уравнений (5.1) определяются платежи. Так как количество неизвестных (платежей) равно M + N, а система состоит из M + N – 1 уравнения, один из платежей (обычно U1) принимается равным нулю.

Найдем платежи для рассматриваемого примера. Пусть U1 = 0. Тогда V2 = = 3 (из первого уравнения). По значению V2 = 3 из второго уравнения найдем U2 = –1. Из третьего уравнения найдем V3 = 2. Из пятого уравнения по значению V2 = 3 получим U3 = 1. Продолжая расчеты аналогичным образом, получим: V1 = 9, U4 = -1 (платежи указаны в порядке их вычисления). Для дальнейших расчетов удобно указать значения платежей возле соответствующих строк и столбцов расчетной таблицы (см. табл. 5.9, 5.10).

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

4. Для всех небазисных переменных находятся разности стоимостей и псевдостоимостей: Dij = Cij – = 3, и т.д. В табл. 5.10 они указаны в правых нижних углах ячеек.

5. Если для всех величин Dij выполняется условие Dij 0, то оптимальное решение найдено, и решение задачи завершается. Если имеются величины Dij < 0, то выполняется следующий шаг.

6. Определяется переменная для включения в базис. В качестве такой переменной выбирается переменная, которой соответствует максимальная по модулю отрицательная величина Dij. Включение переменной Xij в базис означает, что должны выполняться перевозки от i-го поставщика к j-му потребителю. Соответствующая ячейка расчетной таблицы обозначается знаком «плюс».

В рассматриваемом примере имеются две отрицательные величины Dij:

D11 = –5 и D21 = –2. Максимальная по модулю из этих величин – D11. Значит, для включения в базис выбирается переменная X11.

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

7. Определяется переменная для исключения из базиса. Для этого строится цикл.

Рассмотрим построение цикла для примера 5.1. Включение в базис переменной X11 означает, что будут выполняться перевозки товара со склада СК1 в магазин МГ1. Так как запас товара на складе СК1 ограничен (составляет только 40 тонн), потребуется снизить поставки магазину МГ2, т.е. переменную X12.

Для того чтобы магазин МГ2 получил необходимое количество товара (80 тонн), необходимо, чтобы какой-либо из складов, уже поставляющих товар этому магазину, увеличил свои поставки. Магазину МГ2 поставляют товар два склада: СК2 и СК3. Однако склад СК2 не может увеличить поставки магазину МГ2, так как в таком случае этот склад должен был бы уменьшить поставки магазину МГ3, а этот магазин получает весь необходимый товар (40 тонн) только со склада СК2. Поэтому поставки магазину МГ2 увеличивает склад СК3 (переменная X32 увеличивается). Так как запас товара на складе СК3 ограничен, из-за увеличения поставок магазину МГ2 этот склад должен уменьшить поставки какому-либо другому магазину, в данном случае – магазину МГ1 (переменная X уменьшается). Для того чтобы магазин МГ1 получил необходимое количество товара, поставки в этот магазин будет выполнять склад СК1. Таким образом, цикл построен. Переменные, которые требуется увеличить, обозначаются знаком «плюс», а уменьшаемые – знаком «минус». Цикл показан в табл. 5.10.

Примечание. Если в расчетной таблице оказалась хотя бы одна величина Dij < 0, то всегда можно построить цикл, причем только один.

Склады Минимальная из переменных, отмеченных знаком «минус», исключается из базиса. Обозначим эту переменную как Xrs. В данном случае это переменная X31. Исключение переменной Xrs из базиса означает, что перевозки от r-го поставщика s-му потребителю прекращаются.

Примечание. Если несколько переменных, отмеченных знаком «минус», имеют одинаковое минимальное значение, то для исключения из базиса выбирается любая из них.

8. Определяются новые значения базисных переменных (новый план перевозок). Все переменные, отмеченные знаком «плюс», увеличиваются на Xrs, а отмеченные знаком «минус» – уменьшаются на эту же величину. Значения остальных переменных не изменяются.

В данном примере Xrs = X31 = 30 (таким образом, перевозки со склада СК3 в магазин МГ1 выполняться не будут). Переменные, отмеченные в цикле знаком «плюс», увеличиваются на 30; это значит, что соответствующие перевозки увеличиваются на 30 тонн. Переменные, отмеченные знаком «минус», уменьшаются на 30. Новый план перевозок показан в табл. 5.11. Умножив величины перевозок (Xij) на соответствующие стоимости перевозки единицы груза (Cij), найдем целевую функцию: E = 690.Таким образом, в результате перехода к новому решению затраты на перевозки снизились.

Примечание. Если несколько переменных принимают нулевые значения, то из базиса исключается только одна из них – переменная Xrs, выбранная на шаге 7. Остальные переменные остаются базисными, хотя и имеют нулевые значения. Подробнее такой случай рассмотрен в подразделе 5.5.

9. Выполняется возврат к шагу 1.

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

U4 + V1 = 8.

Принимая U1 = 0, найдем остальные платежи: V1 = 4, V2 = 3, U2 = –1, V3 = 2, U3 = 1, U4 = 4 (платежи указаны в порядке их вычисления). Затем определяются значения псевдостоимостей, далее – разности стоимостей и псевдостоимостей. Все эти величины приведены в табл. 5.11.

В таблице имеются отрицательные разности стоимостей и псевдостоимостей: это величины D42 = –1 и D43 = – 3. Это означает, что полученное решение не является оптимальным. Переменная X43 включается в базис. Для определения переменной, исключаемой из базиса, строится цикл.

Склады Включение в базис переменной X43 означает, что будут выполняться перевозки товара со склада СК4 в магазин МГ3. Поэтому требуется уменьшить перевозки со склада СК4 какому-либо магазину (так как запас товара на складе ограничен). В данном случае можно уменьшить только поставки магазину МГ1. Чтобы магазин МГ получил необходимое количество товара, требуется увеличение поставок со склада СК1, т.е. увеличение переменной X11. Из-за увеличения поставок магазину МГ1 склад СК1 должен уменьшить поставки магазину МГ (уменьшается переменная X12). Чтобы магазин МГ2 получил необходимое количество товара, необходимо, чтобы какой-либо из складов, уже поставляющих товар этому магазину, увеличил свои поставки. Магазину МГ2 поставляют товар склады СК2 и СК3; однако склад СК3 не может увеличить свои поставки, так как он поставляет магазину МГ2 весь имеющийся у него товар (60 тонн). Поэтому поставки магазину МГ2 увеличивает склад СК2 (увеличивается переменная X22). Из-за этого склад СК2 должен снизить поставки магазину МГ (уменьшается переменная X23). Для того чтобы магазин МГ3 получил необходимое количество товара, поставки в этот магазин будет выполнять склад СК4 (переменная X43 включается в базис). Таким образом, цикл построен (см. табл. 5.11).

Из базиса исключается переменная X12 = 10, так как эта переменная – минимальная из отмеченных знаком «минус». Это значит, что перевозки со склада СК1 в магазин МГ2 выполняться не будут.

Определяется новый план перевозок: переменные, отмеченные в цикле знаком «плюс», увеличиваются на Xrs = X12 = 10, а отмеченные знаком «минус» – уменьшаются на 10. Новый план перевозок показан в табл. 5.12. Целевая функция (стоимость всех перевозок) для этого плана равна E = 660 ден. ед.

Склады Для полученного плана перевозок составим систему уравнений (5.1), чтобы определить платежи:

U4 + V3 = 3.

В табл. 5.13 приведены платежи (Ui и Vj), псевдостоимости ( C ij ), разности стоимостей и псевдостоимостей (Dij). Все величины Dij неотрицательны. Это означает, что полученное решение оптимально.

Склады Таким образом, оптимальный план перевозок состоит в следующем. Склад СК1 поставляет 40 тонн товара магазину МГ1; склад СК2 поставляет 20 тонн товара магазину МГ2 и 30 тонн – магазину МГ3; склад СК3 поставляет 60 тонн товара магазину МГ2; склад СК4 поставляет 20 тонн товара магазину МГ1 и 10 тонн – магазину МГ3. Другими словами, переменные приняли следующие значения: X11 = 40, X22 = 20, X23 = 30, X32 = 60, X41 = 20, X43 = 10; остальные переменные равны нулю. Общие затраты на перевозки составят 660 ден. ед.

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

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

Пример 5.2. Пусть в условиях примера 5.1 на складе СК3 имеется только 45 тонн товара. Требуется составить план перевозок, при котором затраты на их выполнение будут минимальными.

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

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

15 тонн. Обозначим фиктивный склад как СК5. Стоимости перевозки единицы товара с этого склада в любой магазин будем считать равными нулю. Расчетная таблица для этой задачи показана в табл. 5.14.

Таким образом, получена задача с правильным балансом. Она решается точно так же, как обычная транспортная задача.

Сначала требуется найти допустимый план перевозок. Воспользуемся для этого методом минимального элемента. Минимальные стоимости соответствуют перевозкам со склада СК5 (т.е. фиктивного склада) в любой магазин; эти стоимости равны нулю. Выберем перевозки со склада СК5 в магазин МГ1. Запас товара на складе СК считается равным 15 тонн, а спрос магазина МГ1 составляет 60 тонн. Поэтому поставки со склада СК5 магазину МГ1 принимаются равными 15 тонн. Склад СК5 исключается из рассмотрения (строка СК5 вычеркивается из расчетной таблицы), а спрос магазина МГ1 уменьшается на 15 тонн.

Аналогично выполняется дальнейшее построение допустимого плана по методу минимального элемента. Полученный допустимый план приведен в табл. 5.15. Значение целевой функции (стоимость перевозок) для этого плана составляет 690 ден. ед.

На основе допустимого плана перевозок определяется оптимальный план. Для этого используется метод потенциалов. Оптимальный план приведен в табл. 5.16.

Оптимальный план перевозок состоит в следующем. Склад СК1 поставляет тонн товара магазину МГ1; склад СК2 поставляет 35 тонн товара магазину МГ2 и тонн – магазину МГ3; склад СК3 поставляет 45 тонн товара магазину МГ2; склад СК поставляет 5 тонн товара магазину МГ1 и 25 тонн – магазину МГ3. Поставки с фиктивного склада, вошедшие в оптимальный базис, означают, что соответствующим потребителям будет поставлено меньше товара, чем им требуется. Таким образом, магазину МГ1 будет поставлено на 15 тонн товара меньше, чем ему требуется (т.е. всего 45 тонн вместо 60 необходимых). Общие затраты на перевозки составят 540 ден. ед.

Пример 5.3. В условиях примера 5.2 требуется составить план перевозок с минимальными затратами. При этом необходимо выполнить следующее дополнительное требование: спрос магазина МГ1 должен быть обязательно удовлетворен полностью.

Как и в примере 5.2, для приведения этой задачи к правильному балансу необходимо добавить фиктивного поставщика (склад СК5) с запасом товара в размере 15 тонн. Однако стоимость перевозки единицы товара от фиктивного поставщика в магазин МГ1 следует считать очень большим числом (например, 1000 ден. ед.). Стоимости перевозки единицы товара от фиктивного поставщика в другие магазины будем считать равными нулю. Расчетная таблица для этой задачи показана в табл. 5.17.

Получена задача с правильным балансом. Она решается точно так же, как обычная транспортная задача. Сначала по методу минимального элемента определяется допустимый план (табл. 5.18), затем по методу потенциалов – оптимальный план (табл. 5.19). Эти методы обеспечивают получение плана перевозок с минимальными затратами. Поэтому перевозки с фиктивного склада СК5 в магазин МГ1 не войдут в базис (т.е. примут нулевое значение), так как затраты на эти перевозки предполагаются очень большими.

Для данной задачи получен следующий оптимальный план перевозок. Склад СК1 поставляет 40 тонн товара магазину МГ1; склад СК2 поставляет 20 тонн товара магазину МГ2 и 30 тонн – магазину МГ3; склад СК3 поставляет 45 тонн товара магазину МГ2; склад СК4 поставляет 20 тонн товара магазину МГ1 и 10 тонн – магазину МГ3. Магазину МГ2 будет поставлено на 15 тонн товара меньше, чем ему требуется (т.е. всего 65 тонн вместо 80 необходимых). Общие затраты на перевозки составят Пример 5.4. В условиях примера 5.2 требуется составить план перевозок с минимальными затратами. При этом необходимо выполнить следующее дополнительное требование: недопоставка товара распределяется равномерно между всеми магазинами. Это означает, что каждый из магазинов должен получить несколько меньше товара, чем ему требуется.

Для приведения такой задачи к правильному балансу предполагается, что спрос всех потребителей снизился. Для этого все величины спроса умножаются на коN M эффициент Ai B j, т.е. на отношение суммы величин спроса к сумме запаj =1 i = сов. Вводить фиктивного поставщика в этом случае не требуется.

В рассматриваемом примере сумма величин спроса равна 180, сумма запасов – 165. Значит, величины спроса умножаются на коэффициент, равный 165/180 = 0,917.

Можно сказать, что таким образом спрос магазинов корректируется с учетом возможностей поставщиков (складов). Уменьшенная величина спроса для магазина МГ1 составит 60·0,917 = 55,02 тонны, для МГ2 – 80·0,917 = = 73,36 тонны, для МГ3 – 40·0,917 = 36,68 тонны. Округлим эти величины до целых чисел (будем считать, что величины спроса магазинов должны выражаться целыми числами). Расчетная таблица для данной задачи приведена в табл. 5.20.

Полученная задача с правильным балансом решается обычным образом. Оптимальный план для рассматриваемой задачи приведен в табл. 5.21.

Таким образом, получен следующий оптимальный план перевозок. Склад СК поставляет 40 тонн товара магазину МГ1; склад СК2 поставляет 28 тонн товара магазину МГ2 и 22 тонны – магазину МГ3; склад СК3 поставляет 45 тонн товара магазину МГ2; склад СК4 поставляет 15 тонн товара магазину МГ1 и 15 тонн – магазину МГ3.

Недопоставка товара магазину МГ1 составит 60 - 55 = 5 тонн, магазину МГ2 – 80 – = 3 тонны. Общие затраты на перевозки составят 583 ден. ед.

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

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

Если требуется только обеспечить минимальную стоимость перевозок (без каких-либо дополнительных условий), то для приведения задачи к правильному балансу добавляется фиктивный потребитель; его спрос принимаетM N ревозок к этому потребителю принимаются равными нулю. После этого задача решается обычным образом.

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

5.5. Вырожденное решение Для того чтобы иметь возможность решить систему уравнений (5.1) при поиске оптимального плана перевозок по методу потенциалов, необходимо, чтобы количество базисных переменных всегда было в точности равно M + N – 1.

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

• при поиске допустимого плана – в случае, если запас товара у поставщика оказывается в точности равен спросу потребителя;

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

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

Пример 5.5. С двух карьеров (К1 и К2) поставляются стройматериалы на три стройки (С1, С2, С3). Возможности карьеров по поставке стройматериалов (тонны), потребности строек (тонны) и стоимости перевозок одной тонны стройматериалов с каждого карьера на каждую из строек (ден. ед.) приведены в табл. 5.22.

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

Решим эту задачу, как показано в подразделах 5.2 и 5.3.

Для определения допустимого решения воспользуемся методом минимального элемента. Наиболее дешевыми (6 ден. ед. за тонну) являются перевозки с карьера К2 на стройку С2. Карьер К2 поставляет стройке С2 15 тонн стройматериалов, так как карьер может поставить 45 тонн, а стройке требуется 15 тонн. Стройка С2 исключается из рассмотрения (второй столбец вычеркивается из расчетной таблицы), а в карьере К2 остается 30 тонн стройматериалов.

В сокращенной расчетной таблице минимальный элемент соответствует перевозкам с карьера К2 на стройку С1. Запас стройматериалов в карьере К2 в точности равен потребности стройки С1 (30 тонн). Карьер К2 поставляет стройке С1 30 тонн стройматериалов. Из рассмотрения можно исключить или поставщика (карьер К2), или потребителя (стройку С1), но не обоих вместе.

Пусть исключается карьер К2 (вторая строка вычеркивается из расчетной таблицы). При этом считается, что спрос стройки С1 остается неудовлетворенным на 0 тонн стройматериалов.

В оставшейся части расчетной таблицы выбирается минимальный элемент. Он соответствует перевозкам с карьера К1 на стройку С1 (14 ден. ед. за тонну). Карьер может поставить 30 тонн стройматериалов, а стройке требуется 0 тонн. Поэтому величина поставок стройматериалов с карьера К1 на стройку С1 принимается равной нулю, однако переменная X11 = 0 включается в базис.

Стройка С1 исключается из рассмотрения.

В карьере СК3 имеется запас стройматериалов в размере 30 тонн. Такое количество стройматериалов требуется стройке С3. Поэтому карьер К1 поставляет стройке С3 30 тонн стройматериалов. На этом поиск допустимого плана перевозок завершается. Он приведен в табл. 5.23.

Полученный допустимый план перевозок состоит в следующем. Карьер К1 поставляет 30 тонн стройматериалов стройке С3; карьер К2 поставляет 30 тонн стройматериалов стройке С1 и 15 тонн – стройке С2. Общие затраты на перевозки составят Переменная X11 = 0 включена в базис только для того, чтобы количество базисных переменных было равно M + N – 1 (в данном случае – 4). Никаких перевозок с карьера К1 на стройку С1 не выполняется.

Найдем оптимальный план перевозок, используя метод потенциалов. Составим систему уравнений для определения платежей:

U1 + V1 = U1 + V3 = U2 + V2 = 6.

Принимая U1=0, найдем платежи: V1 = 14, V3 = 25, U2 = –6, V2 = 12. Найдем псевдостоимости = Ui + Vj, чина D23 оказалась отрицательной. Это означает, что имеющийся план перевозок не является оптимальным.

Переменная X23 включается в базис. Для определения нового плана перевозок строится цикл (см. табл. 5.24).

Обе переменные, обозначенные знаком «минус» (X13 и X21), имеют одинаковые значения, равные 30. Любую из этих переменных (но только одну) можно исключить из базиса. Пусть исключается переменная X21. Вычисляются новые значения базисных переменных: все переменные, отмеченные знаком «плюс», увеличиваются на 30 (т.е. на величину переменной, исключаемой из базиса), а переменные, отмеченные знаком «минус» – уменьшаются на ту же величину. Переменная X13 становится равной нулю, но остается в базисе (так как исключается из базиса только одна переменная – X21). Новый план перевозок приведен в табл. 5.25.

Проверим полученный план на оптимальность. Составим систему уравнений для определения платежей:

U1 + V1 = U1 + V3 = U2 + V3 = 10.

Найдем платежи: U1 = 0, V1 = 14, V3 = 25, U2 = –15, V2 = 21. Найдем псевдостоимости, затем – разности стоимостей и псевдостоимостей. Эти величины приведены в табл. 5.26.

Все разности стоимостей и псевдостоимостей оказались положительными. Это означает, что получено оптимальное решение. Таким образом, план перевозок должен быть следующим. Карьер К1 поставляет 30 тонн стройматериалов стройке С1; карьер К2 поставляет 15 тонн стройматериалов стройке С2 и 30 тонн – стройке С3. Общие

6. РЕШЕНИЕ ЗАДАЧ ОПТИМИЗАЦИИ НА ОСНОВЕ МЕТОДОВ

НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

6.1. Постановка задачи нелинейного программирования Задачи нелинейного программирования – это задачи, в которых (как и в задачах линейного программирования) требуется найти значения переменных X1, X2,..., Xn, обеспечивающие максимальное или минимальное значение некоторой целевой функции при соблюдении системы ограничений. При этом целевая функция и/или некоX1, торые из ограничений являются нелинейными, т.е. содержат нелинейные составляющие, например, Как и в задачах линейного программирования, любые значения переменных X1, X2,..., Xn, удовлетворяющие ограничениям задачи, называются допустимыми решениями, а все множество допустимых решений – областью допустимых решений (ОДР). Допустимые значения переменных X1, X2,..., Xn, при которых целевая функция принимает экстремальное значение, представляют собой оптимальное решение. В задачах нелинейного программирования оптимальное решение может находиться как на границе, так и внутри ОДР.

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

Классификация методов нелинейного программирования 6.2. Примеры задач нелинейного программирования Пример 6.1. Для транспортировки некоторого химиката требуется изготовить контейнеры. Требования к контейнерам следующие: 1) емкость контейнера – 6 м ; 2) высота может составлять от 1 до 3 м; 3) основание контейнера должно быть квадратным. Дно и стенки контейнера, непосредственно соприкасающиеся с химикатом, должны быть изготовлены из более стойкого материала, чем крышка контейнера. Стоимость материала дна и стенок контейнера – 6 ден. ед./м, стоимость материала крышки – 4 ден. ед./м. Требуется найти габаритные размеры контейнера (размеры основания и высоту), при которых его стоимость будет минимальной.

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

HL = E = 6L + 24HL + 4L min Здесь первое и второе ограничения устанавливают, что высота контейнера должна составлять от 1 до 3 м; третье ограничение устанавливает, что емкость контейнера равна 6 м. Целевая функция E выражает стоимость контейнера (первое слагаемое – стоимость материала для основания, второе – стоимость материала для стенок, третье – для крышки). Данная задача представляет собой задачу нелинейного программирования: нелинейными здесь являются целевая функция и ограничение на емкость контейнера.

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

Предприятие имеет возможность израсходовать на выпуск приборов не более 0,6 м провода и не более 0,5 кг пластмассы.

Прибыль предприятия от выпуска одного прибора А составляет 8 ден. ед., одной запасной части к прибору А – 2 ден. ед., одного прибора В – 9 ден. ед., одной запасной части к прибору В – 1,5 ден. ед.

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

Введем переменные: X1 – количество приборов типа А; X2 – количество запасных частей к ним; X3 – количество запасных частей в комплекте к одному прибору типа А (соотношение количества запасных частей и приборов типа А); X4 – количество приборов типа B; X5 – количество запасных частей к ним; X6 – количество запасных частей в комплекте к одному прибору типа B (соотношение количества запасных частей и приборов типа B).

Составим математическую модель задачи:

Здесь первое ограничение устанавливает, что общее количество запасных частей к приборам типа A (X2) должно быть равно произведению количества этих приборов (X1) на количество запасных частей в одном комплекте (X3). Второе и третье ограничения устанавливают, что количество запасных частей к одному прибору типа A должно составлять не менее трех и не более шести. Четвертое, пятое и шестое ограничения имеют тот же смысл, но для приборов типа B. Седьмое и восьмое ограничения устанавливают предельный расход провода и пластмассы. Целевая функция выражает прибыль от выпуска приборов и запасных частей.

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

Пример 6.3. Предприятие выпускает электронные изделия двух типов (изделия A и B). На выпуск изделий расходуется платина и палладий. На одно изделие A требуется 13 г платины и 8 г палладия, на одно изделие B – 6 г платины и 11 г палладия. Предприятие имеет возможность использовать не более 90 г платины и не более 88 г палладия.

Изделия A продаются по цене 12 тыс. ден. ед., изделия B – по 10 тыс. ден. ед.

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

• себестоимость одного изделия A: 7 + 0,2X1, где X1 – объем производства изделий A;

• себестоимость одного изделия B: 8 + 0,2X2, где X2 – объем производства изделий B.