close

Вход

Забыли?

вход по аккаунту

?

Snirnov

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное
образовательное учреждение высшего образования
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
СБОРНИК ЗАДАНИЙ
ПО СОСТАВЛЕНИЮ И ОПТИМИЗАЦИИ
МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ
ТЕХНИЧЕСКИХ СИСТЕМ
Методические указания
к практическим занятиям
Санкт-Петербург
2016
Составитель – Смирнов О. Л.
Рецензент – кандидат технических наук, доцент Н. В. Соловьёв
Издание предназначено для студентов и магистров специальностей «Проектирование и технология электронных средств», «Лазерные системы в ракетной технике», «Вычислительные машины,
комплексы, системы и сети», выполняющих практические занятия
на дневных и вечерних факультетах, а также слушателей факультета
повышения квалификации преподавателей.
Подготовлено к публикации кафедрой конструирования и технологии электронных и лазерных средств по рекомендации методической комиссии института радиотехники, электроники и связи СанктПетербургского Государственного университета аэрокосмического
приборостроения.
Публикуется в авторской редакции.
Компьютерная верстка А. Н. Колешко
Подписано к печати 09.03.16. Формат 60 × 84 1/16.
Бумага офсетная. Усл. печ. л. 8,7. Тираж 50 экз. Заказ № 72.
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
© Санкт-Петербургский государственный
университет аэрокосмического
приборостроения, 2016
ПРЕДИСЛОВИЕ
Появление сложных систем вызвало необходимость разработки
методологии их проектирования. Проектирование включает цель,
описание, формализацию, анализ и синтез оптимального объекта.
На этапе его описания и формализации составляется математическая модель с помощью формул, уравнений, неравенств и логических операторов. На этапе анализа составляются математические
модели внутреннего функционирования объекта и взаимодействия
его с внешней средой. На этапе синтеза составляются постановки
оптимизационных задач, связывающих векторы исходных данных, оптимизируемых переменных и систем ограничений с экстремизируемыми целевыми функциями объекта. Выбираются или
создаются новые методы оптимизации управляемых переменных
проектируемого объекта и разрабатываются алгоритмы и программы решения оптимизационных задач.
В данном учебно-методическом пособии рассматривается методика составления математических моделей на основе словесного
описания объекта, методика решения задач безусловной и условной оптимизации, методика решения задач линейного программирования с нецелочисленными, целочисленными и бинарными
переменными, решение задач методом ветвей и границ и решение
задач многокритериальной оптимизации.
Для каждого раздела составлено до пятидесяти вариантов индивидуальных заданий, позволяющих обеспечить усвоение материала для потоков, состоящих из нескольких групп студентов.
3
РАЗДЕЛ 1. СОСТАВЛЕНИЕ МАТЕМАТИЧЕСКИХ
МОДЕЛЕЙ
Математика изучает модели объектов, т.е. целенаправленные и
упрощенные их отображения [1]. Для создания моделей используются буквенные обозначения, математические символы и соотношения. Описание объекта и формулировка проблемы переводятся
на язык математики и превращаются в математическую модель.
Модель исследуется как математическая задача. Полученные результаты интерпретируются на языке исходной проблемы и после
этого решается вопрос об их применении.
Для проведения математических исследований требуется выполнение 8 этапов [2]:
– определение цели исследования и изучение объекта;
– формулировка проблемы;
– сбор данных (статистических, экспертных и прочих);
– построение математической модели;
– выбор вычислительного метода и создание алгоритма решения
задачи;
– программирование алгоритма и отладка программы;
– проверка качества модели на контрольном примере;
– внедрение результатов на практике.
Чтобы определить цель и четко сформулировать проблему, нужно тщательно изучить объект. Для этого надо получить необходимые данные в исчерпывающем объеме. Результатом 4-го этапа
должна быть формулировка проблемы в виде строгой математической задачи. Исходя из цели исследования и описания модели
выбирают известный метод решения задачи или разрабатывают
новый. Далее составляют алгоритм, определяющий порядок решения и программу для компьютера. Решают тестовые задачи и
вводят при необходимости исправления в алгоритм и программу.
Заключительный этап 8 проводится совместно заказчиками и разработчиками модели. Результаты математических исследований
являются лишь рекомендацией к использованию их на практике.
Окончательное решение вопроса зависит от заказчика.
Для составления математической модели объекта рекомендуется выполнение следующих этапов [2]:
– определение известных и неизвестных величин, а также предпосылок – что дано и что требуется найти;
– выявление важнейших факторов проблемы;
4
– выявление управляемых и неуправляемых параметров;
– математическое описание объекта уравнениями, неравенствами, функциями и иными отношениями взаимосвязей между элементами модели (параметрами, переменными) исходя из содержания рассматриваемой задачи.
Известные параметры задачи считаются заданными до построения модели. Значение неизвестных параметров вычисляются в результате исследования модели.
Важнейшими считаются факторы, которые влияют на конечный результат. Управляемыми считаются параметры, которые
могут принимать произвольные числовые значения исходя из условий задачи, неуправляемыми являются те, значение которых зафиксировано и не может меняться.
Существуют модели описания и модели принятия решения.
Описательные модели отражают содержание и свойства объектов.
С их помощью вычисляют числовые значения параметров и показателей. Модели принятия решения позволяют найти наилучшие
значения показателей. Наименее сложными среди них являются
оптимизационные модели, Эти модели отличаются от описательных тем, что в них имеется возможность выбора значений управляющих параметров.
Пример составления модели
Рассмотрим пример составления математической модели [2].
Нефтеперерабатывающий завод располагает двумя сортами
нефти: сортом A в количестве 10 единиц и сортом B – 15 единиц.
При переработке из нефти получаются два материала: бензин (C) и
мазут (D). Имеется три варианта технологического процесса переработки:
I: 1ед.A + 2ед.B дает 3ед.C + 2ед.D
II:2ед.A + 1ед.B дает 1ед.C + 5ед.D
III:2ед.A + 2ед.B дает 1ед.C + 2ед.D
Цена бензина – 10 долл. за единицу, мазута – 1 долл. за единицу.
Требуется определить наиболее выгодное сочетание технологических процессов переработки имеющегося количества нефти.
Из условия задачи следует, что выгодность технологического
процесса означает получение максимального дохода от реализации
готовой продукции (бензина и мазута). В связи с этим принятие решения заводом состоит в определении того, какую технологию и
сколько раз применить, чтобы получить максимальный доход.
5
Обозначим неизвестные величины: хi – количество использования i-го технологического процесса (i = 1,2,3). Остальные параметры модели (запасы сортов нефти, цены бензина и мазута) известны. Теперь одно конкретное решение завода сводится к выбору
одного вектора х = (х1, х2, х3), для которого выручка завода равна
(32х1+15х2 +12х3) долларов. Здесь 32 доллара – это доход, полученный от одного применения первого технологического процесса
(10 долларов ·3ед.C + 1 доллара ·2ед.D = 32 доллара). Аналогичный
смысл имеют коэффициенты 15 и 12 для второго и третьего технологических процессов соответственно. Учет запаса нефти приводит
к следующим условиям:
для сорта A: x1+2x2+2x3≤10
для сорта B: 2x1+x2+2x3≤15,
где в первом неравенстве коэффициенты 1, 2, 2 – это нормы расхода
нефти сорта A для одноразового применения технологических процессов I, II, III соответственно. Коэффициенты второго неравенства
имеют аналогичный смысл для нефти сорта B.
Математическая модель, в целом имеет вид:
Найти такой вектор х = (х1, х2, х3), чтобы максимизировать
f(x) =32х1+15х2 +12х3
при выполнении условий:
x1+2x2+2x3≤10
2x1+x2+2x3≤15
х1≥0, х2≥0, х3≥0, (х1, х2, х3 – целые числа)
Методика и примеры составления математических моделей разных типов изложены в большом числе монографий и учебных пособий. Ниже [3 – 10] приведены ссылки на источники, из которых
были заимствованы перечисленные ниже задания.
Варианты заданий
(Составить модель. Описать методику решения.
Привести и решить пример)
1
На предприятии производятся два вида продукции из двух видов
сырья. Производство единицы продукта №1 (первого вида) приносит предприятию доход, равный 10 единицам, а производство единицы продукта №2 (второго вида) – доход в 8 единиц. Переработка
6
сырья производится аппаратами двух типов, которые условно называются в дальнейшем машинами и агрегатами. На переработке
сырья первого вида занято пять машин, причем производственные
условия не допускают, чтобы суммарное время использования машин на этой работе превышало 40 ч (за некоторый период). На переработке сырья второго вида занято 25 машин. Суммарное время
их использования в течение того же периода не должно превышать
200 ч. При производстве единицы продукта №1 на переработку сырья первого вида затрачивается 4 ч и на переработку сырья второго
вида – 9 ч, в то время как производство единицы продукта №2 требует затраты 3 ч на переработку каждого из видов сырья.
На предприятии принимается решение увеличить выпуск продукции как за счет приобретения нового оборудования тех типов,
что и имеющиеся, так и за счет сверхурочных часов работы.
Максимальное число сверхурочных часов, приходящихся на
период, равно восьми, причем эти часы должны распределяться на
переработку первого и второго видов сырья равномерно. Доплата
за час сверхурочной работы на переработке любого из видов сырья
одинакова; полная оплата за час сверхурочной работы равна 2 единицам. Повышение затрат за период, связанный с приобретением
одной машины, перерабатывающей сырье первого вида, составляет
10 единиц. Агрегаты, перерабатывающие сырье второго вида, дополнительно не приобретаются. Необходимо максимизировать доход от выпуска продукции.
2
Промышленная фирма производит изделие, представляющее
собой сборку из трех различных узлов. Эти узлы изготовляются на
двух заводах. Из-за различий в составе технологического оборудования производительность заводов по выпуску каждого из трех видов узлов неодинакова. В приводимой ниже табл. 1.1 содержатся
исходные данные, характеризующие как производительность заводов по выпуску каждого из узлов, так и максимальный суммарный
ресурс времени, которым в течение недели располагает каждый из
заводов для производства этих узлов.
Таблица 1.1
Завод
Максимальный недельный
фонд времени, ч.
Производительность, узел/час
Узел 1
Узел 2
Узел 3
1
2
100
80
8
6
5
12
10
4
7
Идеальной является такая ситуация, когда производственные
мощности обоих заводов используются таким образом, что в итоге обеспечивается выпуск одинакового количества каждого из видов узлов. Однако этого трудно добиться из-за различий в производительности заводов. Более реальная цель состоит в том, чтобы
максимизировать выпуск изделий, что, по существу, эквивалентно
минимизации дисбаланса, возникающего вследствие некомплектности поставки по одному или двум видам узлов. Возможный объем производства каждого из трех видов узлов зависит от того, какой фонд времени выделяет каждый завод для их изготовления.
Требуется определить еженедельные затраты времени (в часах) на
производство каждого из трех видов узлов на каждом заводе, не
превышающие в сумме временные ресурсы каждого завода и обеспечивающие максимальный выпуск изделий.
3
Экономика представлена двумя отраслями народного хозяйства, каждая из которых выпускает свою продукцию и затрачивает
на воспроизводство труд, средства труда и предметы труда. Валовый продукт каждой отрасли за год распределяется, соответственно, на конечный продукт и производственное потребление, причем,
в процессе производства данной отрасли может применяться продукция обеих отраслей. Известно, что потребление одной отраслью
продукции другой пропорционально объему валового выпуска первой из них. Конечный продукт обеих отраслей делится на валовые
капитальные вложения и непроизводственное потребление. Без
учета амортизационных отчислений можно считать, что валовые
капитальные вложения из одной отрасли в другую каждый год пропорциональны приросту валовой продукции второй отрасли. Определить, как должна функционировать рассматриваемая экономическая система во времени
4
Фирма А производит некоторый товар, который имеет спрос в
течение n единиц времени. Этот товар поступает на рынок в момент
i (i=1,...,n). Для конкурентной борьбы с фирмой А дочерняя фирма
В концерна Д, не заботясь о собственных доходах, производит аналогичный товар, который поступает на рынок в момент j (j=1,...,n).
Ее цель – разорение первой фирмы, после чего ей будет легко, опираясь на капитал D, наверстать упущенное. Для этой цели проще
всего продавать товары по пониженной цене. Однако имеются законы (соглашения), запрещающие поступать подобным образом.
8
В этом случае единственным законным инструментом этой фирмы
является выбор момента поступления товара на рынок. Будем считать, что качество конкурирующих товаров зависит от времени их
поступления на рынок относительно друг друга – чем позднее товар выбрасывается на рынок, тем качество его выше, а реализуется
только товар высшего качества. Каждая фирма должна заранее готовить свое производство к выпуску и продаже товара в выбранный
период времени. А чтобы разорить первую фирму, вторая фирма
должна минимизировать ее доходы
5
Для обеспечения нормальной работы оборудования необходимо
закупить n видов запасных частей на сумму d рублей. Стоимость
j-й детали равна bj, потребность в ней есть случайная величина yj,
имеющая показательный закон распределения с параметром aj. Использование j-й детали позволяет получить прибыль cj. Отсутствие
детали в случае необходимости приводит к убыткам rj. Если деталь
не используется в данном периоде, то убыток составляет qj. Как
распределить имеющиеся средства, чтобы общая прибыль была
наибольшей?
6
Фабрика производит два вида лака для наружных и внутренних
работ. Используется два исходных продукта: нефть и кислота. Максимально возможные суточные запасы этих продуктов определяются емкостями их хранения и равны 6 и 8 т. соответственно. Для
производства 1 т. лака для внутренних работ расходуется 1 т. нефти
и 2 т. кислоты. Для производства 1 т. лака для наружных работ расходуется 2 т. нефти и 1 т. кислоты. Суточный спрос на лак для наружных работ не превышает 2 т. Спрос на лак для внутренних работ – неограничен. Доход от реализации 1 т. лака для внутренних
работ равен 3 миллиона рублей, а доход от реализации 1 т. лака для
наружных работ – 2 миллиона рублей. Необходимо определить, какое количество лака каждого вида должна производить фабрика в
сутки, чтобы доход от его реализации был максимальным.
7
Автотранспортная компания для перевозки грузов располагает
четырьмя автомашинами следующей грузоподъемности: машина
1 – 2 т, машина 2 и машина 3 – по 5 т, машина 4 – 8 т. Для каждой автомашины известна стоимость её эксплуатации за день: для
машины 1 – 15 единиц, для машины 2 – 20 единиц, для машины
3 – 19 единиц, для машины 4 – 30 единиц. Необходимо в течение
9
одного дня развести грузы четырем получателям. В книжный магазин нужно доставить груз весом в 1 т, в мебельный магазин – в
3 т, в фермерское хозяйство – в 5 т и на сталелитейный завод – в 8
т. Одна и та же машина не может доставлять груз в книжный или
мебельный магазин и на ферму. Требуется так назначить автомашины для доставки всех грузов, чтобы суммарные затраты были
минимальными.
8
На местности имеется сеть дорог, связывающих несколько населенных пунктов. Путешественник находится в пункте a0, из которого, двигаясь по одной из трех дорог, можно попасть в пункты a1,
a2, a3. Из каждого пункта опять выходят ровно три дороги, ведущие в a4, a5, a6. Из них – в a7, a8, a9 и так далее, вплоть до конечных
пунктов b1 = a3*n–2, b2 = a3•n–1, b3= a3•n. Длины всех дорог заданы.
Найти наиболее короткий путь из a0 в один из конечных пунктов.
Решить задачу при N = 5. Оцените количество операций сложения
и сравнения при ее решении по методу Беллмана, а также при полном переборе всех путей.
9
Построить расписание обслуживания n = 5 требований одним
прибором, минимизирующее максимальное отклонение моментов завершения обслуживания требований от директивных сроков
Lmax = maxj{Cj –dj}. Отношения предшествования заданы в виде
1 –> 2 –> 3 и 4 –> 5. Длительность обслуживания любого требования равна 2. Директивные сроки d1 = 4, d2 = 2, d3 = 4, d4 = 7, d5 = 5.
10
Построить математическую модель задачи о диете. Доступны
следующие продукты: пирожные, 30с за шт., котлеты 40с за шт.,
кола, 80c за бут., бигмаки, 70c за шт. В единице продукта содержится следующее количество приведенных ниже веществ (табл. 1.2).
Таблица 1.2
пирожное
котлета
кола
бигмаки
калории
300
100
250
200
сахар
5
5
3
3
жир
4
2
2
7
витамины
0
1
1
0
Заданы ограничения на потребление веществ в день. Сумма калорий ≥ 500 и ≤ 900. Сумма витаминов ≥ 6. Сумма сахара ≥ 10 и ≤ 40.
10
Сумма жира ≥ 8 и ≤ 15. Требуется определить набор из указанных
продуктов на день минимальной стоимости при выполнении приведенных ограничений.
11
Банк собирается выдать кредитов на сумму, не превышающую
10 млн $. Типы кредитов и информация о доходах по ним и рисках
приведены в табл. 1.3.
Таблица 1.3
Тип кредита
Личный
Покупка авто
Жильё
С/х
Бизнес
Доля дохода
0.10
0.13
0.14
0.20
0.10
Доля невозврата
0.04
0.09
0.10
0.15
0.05
Банк обязан разместить ≥ 30% всех кредитов на нужды с/х и
бизнеса, и ≥ 40% от кредитов на личные нужды, авто и жильё – на
жильё. Общая доля невозврата по всем кредитам не должна превосходить 0.09. Необходимо определить суммы кредитов по указанным видам так, чтобы максимизировать доход.
12
Рассмотрим следующую задачу. Пусть на каждом шаге некоторой последовательности действий мы вправе выбрать один из двух
вариантов возможных образов действий. При выборе первого варианта мы с вероятностью р1 получаем единицу прибыли, с вероятностью р2 – две единицы прибыли и с вероятностью р3 процесс заканчивается. При втором варианте эти вероятности соответственно
равны р′1, р′2, p′3. Указать последовательность выборов, максимизирующую вероятность получения по крайней мере п единиц прибыли до завершения процесса.
13
В некоторый начальный момент мы располагаем х долларами и
сывороткой в количестве у, а также возможностью покупки добавочных количеств сыворотки в точно установленные моменты времени:
t1 < t2 < .... За z долларов в каждый из моментов tk можно купить сыворотку в количестве ckz, где ск– монотонно возрастающая функция
k. Задана вероятность вспышки эпидемии в период между моментами tk и tk.hl, причем в случае ее возникновения мы можем использовать только то количество сыворотки, которое уже имеется у нас на
11
руках. Задача состоит в определении поведения закупки сыворотки,
максимизирующего полную вероятность успешности борьбы с эпидемией. Требуется составить допустимый план работ на месяц с максимальным доходом. Вероятность успешного исхода э т ой борьбы
при наличии сыворотки в количестве w считается известной.
Условие ск > ск–х означает, что стоимость сыворотки уменьшается со временем вследствие совершенствования технологии производства.
14
Построить математическую модель оптимального планирования объемов производства. Компания производит погрузчики и
тележки. От одного погрузчика компания получает доход в размере $80 и от одной тележки в размере $40. Имеется три обрабатывающих центра, на которых выполняются операции металлообработки, сварки и сборки, необходимые для производства любого из
продуктов. Для интервала планирования, равного месяцу, задана
предельная производственная мощность каждого обрабатывающего центра в часах, a также количество часов, необходимое на этом
центре для производства одного погрузчика и одной тележки. Эта
информация задана в табл. 1.4.
Таблица 1.4
Мехобработка
Сварка
Сборка
Погрузчик
(часы/ед.)
Тележка
(часы/ед.)
Общая мощеость
(часы)
6
2
9
4
3
3
2400
1500
2700
15
Известно, что автомашина может взять с собой бензина в количестве, достаточном для прохождения расстояния в d миль. Чтобы
она могла пройти расстояние в 2d миль по пустынной местности,
ей необходимо создать на своем пути промежуточные заправочные
пункты, завезя на них запасы бензина. Как следует их разместить,
чтобы общие расходы бензина, необходимые для достижения пункта назначения, были минимальными, и чему равно общее расстояние, которое при этом придется пройти машине?
16
Газеты доставляются для продажи в ряд киосков. Предполагая,
что функция распределения количества продаваемых в каждом
из киосков газет известна и что определенное количество непро12
данных газет может быть возвращено с соответствующей уценкой,
определить, сколько должно быть отпечатано экземпляров газеты
и как они должны быть распределены по киоскам.
17
Человек стоит в очереди в ожидании обслуживания, причем
перед ним стоят N человек. Ему известна полезность d от выстаивания очереди и вероятность р того, что за единицу времени будет
обслужен один человек. С другой стороны, он терпит убыток величиной с, за каждую единицу времени, потраченную на ожидание.
Задача состоит в определении такого поведения ожидания, которому соответствует максимальный средний доход.
18
На трёх базах имеется запас сырья необходимого для производства четырех предприятий. На первой базе – 60 т., на второй – 90 т.,
на третьей – 140 т. Первому предприятию для производства требуется 40 т. сырья, второму – 30 т., третьему – 100 т., четвертому –
120 т. Найти оптимальный план задачи методом северо-западного
угла, зная, что стоимость перевозок с первой базы на первое предприятие равна 4 ед., на второе – 2 ед., на третье – 3 ед., на четвертое – 4 ед., со второй базы на первое предприятие равна 2 ед., на второе – 4 ед., на третье – 3 ед., на четвертое – 5 ед., с третьей базы на
первое предприятие равна 6 ед., на второе – 5 ед., на третье – 4 ед.,
на четвертое – 6 ед.
19
Нужно распределить между N предприятиями сумму a, выделенную для их инвестирования. Известно, что вложение средств в
размере y в k-е предприятие обеспечивает прибыль в размере dk(у).
Целью распределения является получение максимального суммарного дохода. Решить задачу при N = 4, a = 300 при условии, что
суммы инвестиций всегда кратны 50, а функции dk(у) для у = 50j
(j = 0, 1, ..., 6) принимают значения, заданные в табл. 1.5.
Таблица 1.5
y
0
50
100
150
200
250
300
d1(y)
0
50
120
140
150
200
250
d2(y)
0
60
130
140
130
160
200
d3(y)
0
30
60
100
130
200
250
d4(y)
0
40
100
110
120
160
220
13
20
На двух торговых базах А и В имеется 30 гарнитуров мебели,
по 15 на каждой. Всю мебель требуется доставить в два мебельных
магазина, С и D причем в С надо доставить 10 гарнитуров, а в D –
20. Известно, что доставка одного гарнитура с базы А в магазин С
обходится в одну денежную единицу, в магазин D – в три денежных единицы. Соответственно с базы В в магазины С и D: две и пять
денежных единиц. Составить план перевозок так, чтобы стоимость
всех перевозок была наименьшей. 21
В пунктах А и В расположены кирпичные заводы, а в С и D –
карьеры, снабжающие их песком. потребность заводов в песке
меньше, чем производительность карьеров. Известно, сколько песка нужно каждому из заводов и сколько добывается в каждом карьере. Также известна стоимость перевозки 1 т песка из каждого
карьера к заводам (числа на стрелочках). Нужно так спланировать
снабжение заводов песком, чтобы затраты на перевозку были наименьшими. 22
Некоторому заводу требуется составить оптимальный план выпуска двух видов изделий, которые обрабатываются на четырех
видах машин. Известны определенные возможности и производительность оборудования; цена изделий, обеспечивающая прибыль
заводу, составляет 4 тыс. руб. за изделие I вида, 6 тыс. руб. – за изделие II вида. Составить план выпуска этих изделий так, чтобы от
реализации их завод получил наибольшую прибыль.
23
Проблема проектирования эффективного перегонного устройства для производства тяжелой воды включает задачу о минимизации выражения
VN=g(a1)+ g(a2)/a1+ g(a3)/a1a2+…+ g(am)/a1a2…am–1,
где аi подчинены следующим ограничениям:
a) аi≥1
b) a1a2…am=x.
Показать, что эта задача может быть сведена к функциональному уравнению
fk+1(x)=min[g(a1) + fk(x/a1)/a1],
a1≥1
14
и получить решение в случае g(y) = yb, b > 0.
24
Игрок имеет сумму денег х и хочет держать пари в N различных
случаях. Существует вероятность рk того, что он может правильно
предсказать исход в k-м случае. Ограничивается лишь ставка пари;
это необходимо для того, чтобы игрок мог оплатить все свои проигрыши.
Показать, что задачу максимизации ожидаемого им дохода
можно свести к задаче максимизации линейной функции:
LN (x) =
N
∑ pk xk
k =1
при условиях:
a) xi ≥ 0
b)
N
∑ xi ≤x + xj , j =1,2,...,N ài ≥ 1
i =1
25
Пусть требуется определить план выпуска четырех видов продукции: A, B, C, D. Ресурсы трех видов: трудовые, материальные,
финансовые, Количество каждого i-го вида ресурса для производства каждого j-го вида продукции, для изготовления которых используются ресдукции называют нормой расхода и обозначают aijj.
Нормы расхода и наличие ресурсов приведены в табл. 1.6.
Таблица 1.6
Ресурсы
Трудовые
Материальные
Финансовые
Нижняя граница
Верхняя граница
План
Вид продукции
Запас ресурсов
A
B
C
D
6
7
3
1
12
x1
4
9
4
–
2
x2
2
11
9
3
–
x3
1
5
6
–
–
x4
800
2000
12000
–
–
–
Для выпуска единицы продукции, вида A требуется шесть единиц трудовых ресурсов, вида C – 11 единиц материальных ресурсов
и т. д.
15
Предприятие располагает 12000 единицами финансовых ресурсов, 2000 единицами материальных, 800 единицами трудовых.
Исходя из рыночного спроса и производственно-технологических возможностей, заданы верхние и нижние предельные границы выпуска каждого вида продукции.
На основании исходных данных требуется составить математическую модель для определения плана выпуска продукции.
26
Некоторому заводу требуется составить оптимальный план выпуска двух видов изделий, которые обрабатываются на четырех
видах машин. Известны определенные возможности и производительность оборудования; цена изделий, обеспечивающая прибыль
заводу, составляет 4 тыс. руб. за изделие I вида, 6 тыс. руб. – за
изделие II вида. Составить план выпуска этих изделий так, чтобы
от реализации их завод получил наибольшую прибыль. В таблице
указано время, необходимое для обработки каждого из двух видов
изделий на оборудовании всех четырех видов (таблица 1.7).
Таблица 1.7
Изделия
I
II
Возможное время
работы машин
Виды машин
1
2
3
4
1
1
18
0,5
1
12
1
0
12
0
1
9
27
При выпуске продукции предприятие ограничено имеющимися
ресурсами, количество которых обозначим m, а вектор ресурсов В =
(b1, b2, ..., bт). Известны также технологические коэффициенты aij,
которые показывают норму расхода i-го ресурса на производство
единицы j-й продукции. Эффективность выпуска единицы j-й продукции характеризуется прибылью pj. Требуется определить план
выпуска продукции Х=(х1, х2, ..., xп), максимизирующий прибыль
предприятия при заданных ресурсах.
28
Частное предприятие планирует в течение N лет заниматься
выпуском изделий, используя некоторое оборудование. В начале
можно либо купить новое оборудование возраста Х0 = 0 лет и стоимостью р, либо подержанное оборудование возраста Х0 > 0 лет по
его ликвидной стоимости р(Х0). Показатели эксплуатации обору16
дования включают: f (t) – стоимость произведенных за год изделий
на оборудовании возраста t лет; r(t) – затраты на эксплуатацию в
течение года оборудования возраста t лет.
В процессе эксплуатации оборудование можно менять, продавая
старое по ликвидной стоимости p(t) и покупая новое стоимостью р.
В конце N -го года оборудование продается по ликвидной стоимости. Определить оптимальный возраст оборудования X0 при начальной покупке и оптимальный график его замены. Выполнить
расчеты при N = 8, X0 = {0,1,2}, (p(t) = 6 при 0 < t < 6) f (t) = 30 – t/2,
r(t) = 13 +t/2, p = 17, (p(t) = 2 при 7 < t < 10)
29
Предприятие, выпускает товары, изготавливая их отдельными партиями. Чем больше размер этих партий, тем относительно
дешевле обходится выпуск. Поэтому в отдельные месяцы выгодно выпускать больше изделий, чем это нужно для удовлетворения
спроса, а излишки хранить на складе для их реализации в последующие месяцы. За хранение в течение месяца каждой тысячи штук
изделий нужно платить а = 1 усл.ед. Емкость склада ограничена
величиной C = 4000 штук.
Составить оптимальный план производства на N = 4 месяцев,
при котором общая сумма затрат на производство и хранение была
минимальной, а спрос на изделия – всегда удовлетворен. Объемы
спроса по месяцам составляют mi (i = 1,.., N) изделий (при решении
принять: 2000, 3000, 3000 и 2000). Начальные запасы готовых изделий составляют C0 = 2000. Размер производимых партий не может превышать p = 4000 изделий. Затраты, связанные с выпуском
партий изделий объемом vt (i = 1,.., N) штук (принять: 1000, 2000,
3000 и 4000), определяются величинами zi (i = 1,.., N) (соответственно 13, 15, 17 и 19 усл.ед.).
30
Товар в количестве C = 100 ед. может реализовываться на трех
рынках по ценам p1, p2 и p3 за единицу продукции. Определить оптимальное распределение товара между рынками при следующих
зависимостях цены от объема предлагаемой продукции xi на данном рынке:
40 – 20 x1 при 0 < x1 < 20.
50 – 0.5 x2 при x2 > 30,
p1(x1) = 0 при x1 > 20,
p2(x2) = 30 при 0 < x2 < 30 p3(x3) = 30 – 0.3x3
17
31
Используя уравнения Беллмана, составить расчетную схему
решения задачи максимизации суммарной прибыли от работы k
цехов, выпускающих изделия разных видов. Прибыль от выпуска x изделий j-го вида (он производятся j-м цехом) определяется
значением Pj(x) (табл. 1.8). Изготовление одного изделия j-го вида
требует определенного количества сырья m типов, а именно Cj1, ...,
Cjm. Запасы этого сырья, общие для всех цехов, составляют z1, ...,
zm. Решить задачу при следующих данных: K = 3, m = 2, расходы
сырья для изделия первого типа: C11 = 2, C12 = 4 ; второго: C21 =4,
C22 = 2; третьего: C31 = 1, C32 = 3; а запасы составляют z1 = 10, z2 = 12.
Таблица 1.8
Значения прибыли P (x)
PJ(X)
j
X
1
2
3
4
5
6
1
2
3
8
7
10
15
14
18
21
20
24
26
26
26
30
31
28
32
34
30
32
Имеется некоторое производство, которое ежедневно обеспечивается поставками сырья в количествах Р1, Р2, …, Pn. Излишки сырья хранятся на складе емкостью E. Начальное количество сырья
на складе задано и составляет E0. Обозначим X1, X2, …, Xn – объемы сырья, ежедневно забираемые на производство. Общее количество перерабатываемого за N дней сырья известно и равно A. По
известному графику поставок сырья Р1, Р2, …, Pn составить график
его потребления X1, X2, …, Xn, минимизирующий неритмичность
производства, понимаемую как
q=∑(xi – A/N)2.
Сырье следует считать штучным. Решить задачу при N = 5,
E0 = 2, E0 = 5 E0 = 10, Р1 = 1, Р2 = 1, Р3 = 1, Р4 = 6, Р5 = 7.
33
Предприятие функционирует N лет. Начальный капитал равен
a. Каждый год некоторая часть и* имеющейся суммы пускается в
оборот с условием возврата в кассу в конце года суммы в размере
рj(и*). Кроме того, из дохода выплачивается сумма fj(и*) в качестве
вознаграждения работникам. Найти оптимальные значения U1, U2,
..., Un, максимизирующие сумму выплаченных вознаграждений.
18
Выполнить расчет при N = 3, f1(u) = 0.1и2,
f2(u) = 0.2и, р2(и) = 0.3и, f3(u) = и, р3(u) = 0.
р1(u) = 0.7и,
34
Газы из сопла ракеты вылетают с постоянной скоростью C. Сопло подвешено на оси, и направление выброса газов можно регулировать. В предположениях, что движение ракеты является плоским,
происходит в безвоздушном пространстве и вектор ускорения
свободного падения g является постоянным, найти оптимальное
управление тягой ракеты (a(t); и(t)), 0 < и(t) < A, максимизирующее: а) дальность полета ракеты; б) высоту подъема ракеты. Здесь
a(t) – угол между горизонтом и прямой, вдоль которой происходит
выброс газов в момент времени t.
35
Телевизионная компания намерена арендовать телевизионные
линии связи для объединения части своих станций в единую сеть.
Телевизионные линии связи существуют между любыми двумя
станциями, и известна стоимость их аренды, которая, вообще говоря, различна для различных пар станций.. Показать, что для
создания сети с минимальными затратами следует среди еще не
включенных в сеть линий связи выбирать ту, арендная плата за которую минимальна и которая не замыкает кольца уже работающих
линий.
36
Догоняющий находится в i-й клетке из 5 клеток, образующих
круг. За один такт он с вероятностью р = 1/2 перемещается по часовой стрелке в соседнюю клетку, с вероятностью q = 1/3 перемещается против часовой стрелки в соседнюю клетку, с вероятностью
r = 1/6 остается на месте. Убегающий находится в j-й клетке и на
каждом такте может выбрать одну из трех стратегий поведения: (a)
переместиться по часовой стрелке в соседнюю клетку; (b) остаться на месте; (с) переместиться против часовой стрелки в соседнюю
клетку. Расстояние между догоняющим и убегающим определяется по формуле d = i – j. Определить стратегию убегающего на три
такта вперед, максимизирующую сумму расстояний между догоняющим и убегающим.
37
Состояние продуктивности земли, используемой фермером, может быть (a) хорошим,(b) удовлетворительным, (с) плохим. Вероятности перехода продуктивности земли из одного состояния в другое
19
без проведения агротехнических мероприятий за один сезон заданы
матрицей P1. Однако фермер может провести комплекс агротехнических мероприятий, и тогда вероятности перехода продуктивности земли из одного состояния в другое за один сезон будут заданы
матрицей P2. Матрицы доходов для двух стратегий поведения: D1,
D2 – табл. 1.9. Найти оптимальную стратегию фермера на 4 сезона.
Таблица 1.9
0.2 0.5 0.3
0.3 0.6 0.1
P1 0.0 0.5 0.5 P2 0.2 0.6 0.2 D1
0.0 0.0 1.0
0.1 0.5 0.4
7
0
0
6
5
0
3
1
1
D2
6
5
4
5
4
3
–
–1
–2
38
Студент уже сдал один экзамен на 4, но ему предстоит сдать еще
три экзамена. При подготовке к экзаменам он из-за недостатка времени может выбрать одну из следующих двух стратегий: либо выучить часть материала довольно хорошо, либо пройтись быстро по
всему материалу. Определить оптимальную в смысле набранных
баллов стратегию поведения студента на оставшиеся три экзамена, если матрицы вероятностей получения оценок 5, 4, 3, 2 в зависимости от предыдущей оценки для двух стратегий имеют вид
(табл. 1.10).
Таблица 1.10
0.2
0.1
0.3
0.3
0.3
0.4
0.2
0.2
0.0
0.0
0.3
0.3
0.4
0.3
0.3
04
P (1)
0.1
0.0
0.3
0.3
0.5
0.6
0.1
0.1
0.0
0.0
0.2
0.1
0.7
0.8
0.1
0.1
P (2)
39
Электростанция имеет L агрегатов. Предположим, что производительность одного агрегата за неделю равна C, а единица произведенной электроэнергии продается по цене b. График оплачиваемого производства электроэнергии по неделям задан: Р1, Р2,..., Pn, и
нарушаться не должен. Избыточно произведенная электроэнергия
не оплачивается. Затраты на поддержание в рабочем состоянии 1
агрегатов в течение недели равны r(1), затраты на консервацию D1
агрегатов составляют Pk(D1). Затраты на пуск равны Pп(D1). Составить рекуррентные уравнения Беллмана для определения оптимального графика эксплуатации агрегатов.
20
40
Составить рекуррентные уравнения Беллмана для предыдущей
задачи при следующем изменении ее условий. Вначале в фонд развития вносится сумма денег A. Средства на покупку сырья берутся
из фонда развития. Кирпич производится не для личного использования, а для продажи по цене B за штуку (в ценах стартовой недели). При этом 50% получаемой от продажи суммы добавляется
к оставшимся в фонде средствам, а остальные 50% используются
на оплату рабочим, налоги и потребление. Необходимо составить
рекуррентные уравнения Беллмана, позволяющие решить задачу
об оптимальном выделении средств на закупку сырья для максимизации суммы денег в фонде развития к концу N-й недели.
41
Господин M, желая построить коттедж, одолжил у своего друга
на N недель мини-установку по производству дешевого кирпича с
функцией производительности f (X) штук в неделю, где X – количество использованного сырья. Следует считать, что производная
функции f(X) положительна и убывает при увеличении x.
Перед началом производства имелась сумма денег A. Стоимость
единицы сырья в ценах стартовой недели равна C. Коэффициент
инфляции за неделю равен а > 1. Сырье покупается еженедельно
в количествах X1, X2, ..., Xn. По окончании N-й недели на оставшиеся неистраченные деньги покупается готовый более дорогой
кирпич по цене B за штуку (в ценах стартовой недели). Необходимо
составить рекуррентные уравнения Беллмана для определения оптимальных размеров закупки сырья, приводящих к максимизации
общего количества полученного кирпича.
42
Ракета с массой m движется по прямой вне поля силы тяжести.
Реактивный двигатель работает в импульсном режиме. Сообщаемая величина импульса U ∈ [–V, V], а затраты топлива пренебрежимо малы по сравнению с массой корабля. Считать, что порция топлива сгорает мгновенно. Найти значения U1, U2, ..., Un, при которых ракета из состояния покоя перейдет в другое состояние покоя,
максимально удаленное от начального. Принять, что приращение
скорости, полученное в k-й момент времени, начинает оказывать
влияние на приращение координаты только в следующий (k +1)-й
момент времени. Решить задачу при N = 3 и N = 5; m = 1, V = 10. Интервал между импульсами принять равным единице.
Указание: сообщение системе импульса U изменяет ее количество движения (произведение массы на скорость) на величину U.
21
43
Ракета-носитель с N ступенями имеет общую массу M, включающую массу m выводимого на орбиту космического аппарата и топливо. Вес оболочек ступеней считается равным нулю. Обозначим
вес топлива в ступенях ракеты через U1, U2, ..., Un. Будем считать,
что прирост скорости ракеты при сгорании k-ой ступени пропорционален отношению Ukj(m + Un + ... + Uk).
Требуется определить оптимальное распределение топлива по
ступеням ракеты. Выполнить расчеты при N = 3, M = 64, m = 1.
44
Составить оптимальный план ежегодного распределения
средств между двумя предприятиями в течение N лет, если начальная сумма средств равна A, доходы от вложения средств x1 и x2 в
предприятия составляют f1(x1) и f2 (x2). Вложенные средства возвращаются в общую кассу для перераспределения в размере 60%
от x1 для первого и 20% от x2 для второго предприятия. Каждый
год все имеющиеся в общей кассе средства полностью перераспределяются с точностью до остатка, меньшего А; x1 и x2 выбираются
кратными А. Решить задачу при N = 3, A = 400, А = 50 и значениях
функций f1(x) и f2(x2) из табл. 1.11.
Таблица 1.11
Значения функций f1(x1) и f2(x2)
x
50
100
150
200
250
300
350
400
f1(x1)
6
10
15
26
28
38
45
49
f2(x2)
8
12
20
28
35
40
46
48
45
Технологическая цепочка изготовления изделия включает N
операций, выполняемых на автоматизированных участках конвейерной обработки. Устройство, выполняющее операции на i-м
участке, имеет вероятность работы без отказа р^ и стоимость cj. Для
повышения надежности на участке можно установить mi дублеров,
повысив надежность участка до значения Pi(mi) = 1 – (1 – Pi)1+mi.
Средства, выделенные на установку устройств-дублеров, ограничены значением C. Решить задачу о выборе оптимального количества
дублеров, приводящем к максимизации надежности всей технологической цепочки. При решении принять N = 3, C = 17, P1 = 0.5,
P2 = 0.3, С1 = 6, С2 = 4, С3 = 4. Для упрощения расчетов принять приближенные значения функций Pi (m) из табл. 1.12.
22
Таблица 1.12
Значения функции Pi (m)
m
0
1
2
3
4
P1(m)
0.5
0.8
0.9
0.9
1
P2 (m)
0.3
0.5
0.7
0.8
0.8
P3(m)
0.4
0.6
0.9
0.9
1
46
Решено одновременно заменить все осветительные электрические лампочки в рабочем помещении. Обозначим через а издержки
от замены электролампочек, а через g(x)– потери, которые вызваны
недостаточностью освещения, когда между двумя заменами проходит время х. Пусть принято решение заменять лампочки в течение
интервала Т в следующие моменты времени: х1, х1 + х2, ..., x1 + x2
+ … +xn = Т, где число п определено заранее.
Эффективность такой программы действий измеряется средней
суммой потерь
n
∑ (a + g(xi ))
F (x1, x2 ,..., xn ) =
i =1
T
.
Каким должно быть оптимальное поведение?
47
Следователь, устанавливающий личность убийцы, имеет N
свидетелей различной степени надежности, причем один из них
является убийцей. Обозначим через pi вероятность того, что i-й
свидетель ответит правду в любой момент на любой обращенный к
нему вопрос. Следователь допрашивает свидетелей в некотором порядке. При этом первому из допрашиваемых он задает некоторый
вопрос, а каждому следующему задает либо прямой вопрос, либо
вопрос относительно истинности показаний предыдущих свидетелей. Предполагая, что следователю разрешается при каждом допросе задавать один вопрос и что i-му свидетелю для ответа на вопрос требуется время указать, в каком порядке свидетели должны
допрашиваться и какие вопросы им следует задать, чтобы максимизировать вероятность обнаружения убийцы в течение заданного
промежутка времени Т.
23
48
На каждом шаге некоторой последовательности действий мы
вправе выбрать один из двух вариантов возможных образов действий. При выборе первого варианта мы с вероятностью р1 получаем единицу прибыли, с вероятностью р2 – две единицы прибыли и
с вероятностью р3 процесс заканчивается. При втором варианте эти
вероятности соответственно равны р’1, р’2, р’3. Указать последовательность выборов, максимизирующую вероятность получения по
крайней мере п единиц прибыли до завершения процесса.
49
Имеется n, вообще говоря, не одинаковых изделий, которые
должны быть обработаны на ряде установок различных типов (числом т). Порядок, в котором эти установки должны использоваться,
имеет существенное значение, так как некоторые процессы обработки должны быть выполнены раньше других. При заданном времени аij (i= 1, 2, ... п; j=1,2, т), необходимом для обработки i-го
изделия на j-й установке, требуется определить порядок, в котором
эти изделия должны запускаться в обработку, чтобы общее время,
необходимое для выпуска готовой продукции, было минимальным.
50
Для исправления ошибки, обнаруженной на i-й стадии производственного процесса, требуется время ti, а связанные с этим исправлением расходы равны сi. Определить сумму, которую целесообразно выделить на приобретение контрольной аппаратуры, а
также распределение последней между операциями, если известны величина заработной платы и стоимость работы оборудования,
приходящиеся на одно изделие, а также убытки от выработки дефектного изделия (скажем, z).
51
Владелец ресторана располагает двумя различными способами
стирки салфеток; при быстром способе стирка занимает q дней и
обходится в с центов за штуку; медленный же способ стирки требует р > q дней и обходится в d <с центов за штуку. Предполагая,
что владелец ресторана заранее знает число посетителей, которых
он должен будет обслужить в любой из дней N-дневного периода,
и что он должен обеспечить салфеткой каждого посетителя. Определить, сколько салфеток он должен купить и как должен отдавать их в стирку, чтобы минимизировать общие расходы в течение
N-дневного периода. Рассмотреть сначала случаи, когда p = q + 1 и
p = q + 2.
24
52
Имеется ряд „источников” или “пунктов отправления”, S1 S2,
…, Sm и ряд «стоков“, или „пунктов назначения», T1 Т2, ..., TN. В
каждом источнике Si имеется некоторое количество материала xi,
которое должно быть перевезено в различные пункты назначения,
причем так, чтобы общее количество материала, доставляемое в
пункт Tj, равнялось заданному требованию yj на него в этом пункте. Предполагается, что
∑ xi = ∑ yj . При данных расстояниях dij
i
j
между пунктами отправления и пунктами назначения и в предположении, что стоимость перевозки единицы количества материала
между пунктами Si и Tj равна dij определить план перевозок, минимизирующий общую стоимость удовлетворения требований. Показать, что рассмотренная выше задача эквивалентна минимизации
линейной формы C = ∑ dij xij при ограничениях:
i,j
∑ xij = xi , ∑ xij = yj ,
j
i
xij ≥ 0
25
РАЗДЕЛ 2. ЗАДАЧИ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ
Замкнутое и одновременно ограниченное множество в метрическом пространстве (в пространстве Rn с заданным на нем понятием расстояния) называется компактным. Компактное множество B ⊂ R n называется выпуклым, если для любых x1, x2 ∈ B [ax1 + (1 − a)x2 ] ∈ B , 0 ≤ a ≤ 1. То есть выпуклое множество В кроме
всех своих точек содержит и все их выпуклые комбинации. Это означает, что вместе с допустимыми x1 и x2 допустимы и их смеси.
Гладкой называется функция, которая в области своего определения имеет производные, то есть является дифференцируемой.
Функция f дважды дифференцируема, если для всех i,j=1,…,n
существуют частные производные от частных производных, то есть
 ∂2 f

2
 ∂x1
 2
 ∂ f
2
 ∂x2∂x1
∇ f=

 ...
 2
 ∂ f
 ∂x ∂x
 n 1
∂2 f
∂x1∂x2
∂2f
∂x22
...
∂2f
∂xn ∂x2
∂2 f 

∂x1∂xn 

∂2f 
...
∂x2∂xn 

...
... 

∂2f 
...
∂xn2 
...
Симметричная относительно диагонали n×n-матрица ∇2f называется матрицей Гессе. Задача нахождения максимального или
минимального значения заданной функции на заданном множестве называется экстремальной. Имеется два вида экстремальных
задач – задача на максимум и задача на минимум. Символически
они записываются так:
f (x) → max(min)
(2.1)
x∈X
Оптимальным решением задач (2.1) называется пара (x*, f(x*)),
где x* – точка максимума (минимума), а f(x*) – значение функции
f в этой точке, то есть ее максимальное (минимальное) значение на
множестве Х.
Решение задачи (2.1) требует разрешения трех проблем: 1) проблему существования оптимального решения; 2) проблему установления необходимых и достаточных признаков оптимальности
(то есть характерных свойств, присущих точкам максимума и минимума); 3) проблему численного вычисления оптимальных ре26
шений. В задачах (2.1) применяются экстремальные точки двух
видов: локальный максимум (минимум) и глобальный максимум
(минимум). Точка x0 ∈ X называется точкой локального максимума (минимума), если
f(x0) ≥ f(x) (f(x0) ≤f(x)) для всех x ∈ Oε (x0 ),
0
где Oε (x0 ) – ε-окрестность точки x0. Точка x ∈ X называется точкой глобального максимума (минимума), если эти неравенства выполняются для всех x∈X. Достаточное условие существования оптимальных решений задач (2.1) содержится в следующем утверждении.
Теорема (Вейерштрасса). Для того, чтобы в задаче (2.1) существовала точка глобального максимума (минимума), достаточно,
чтобы допустимое множество X было компактно в Rn, а целевая
функция f непрерывна на X. Ввиду сложности проверки ограниченности множества X, применяется следствие из этой теоремы.
Следствие (теоремы Вейерштрасса). Если функция f непрерывна
на Rn и


lim f (x) = +∞  lim f (x) = −∞ ,
x →∞
 x →∞
 то f достигает своего глобального минимума в любом замкнутом
подмножестве X пространства Rn.
Признаки оптимальности приведем в случае, когда X ≡ R n . В
этом случае задачи (2.1) принимают вид:
f (x) → max(min)
(2.2)
x∈R n
и называются задачами безусловной оптимизации.
Чтобы точка x0 ∈ R n была точкой локального экстремума в задачах (2.2) необходимо, чтобы
∇f ( x 0 ) =
0
(2.3)
Все точки x0, удовлетворяющие условию (2.3), называются стационарными точками (точки подозрительные на экстремум).
Чтобы x0 была точкой локального максимума (минимума) в задаче (2.2) необходимо и достаточно, чтобы
(
)
∇2 f ( x 0 ) =
0 и 〈∇2f (x0 )α, α〉 ≤ 0 〈∇2f (x0 )α, α〉 ≥ 0 (2.4)
27
для всех α ∈ R n . Здесь ∇2f (x0 ) матрица Гессе функции f в точке x0,
а 〈.,.〉 - скалярное произведение.
Известно, что дважды дифференцируемая на выпуклом множестве Х функция f вогнута (выпукла) тогда и только тогда, когда для
любых векторов x0 ∈ X и α ∈ R n справедливо условие (2.4). Матрица ∇2 f (x) будет отрицательно (положительно) полуопределенной в
точке x0, если
(
)
(−1)k  ∇2f (x0 ) k ≥ 0  ∇2f (x0 ) k ≤ 0
(2.5)
для всех k =1,…, n. Здесь символом  ∇2f (x0 ) k обозначен минор
k-го порядка матрицы ∇2f (x0 ) :
∂2 f
=
 ∇2f (x0 ) k
∂x12
...
2
∂ f
∂xk x1
...
∂2 f
∂x1xk
...
...
, k 1,...,n,
=
...
∂2 f
∂xk2
x = x0
где . x = x0 – определитель порядка k * k, вычисляемый в точке x0.
Если в (2.5) неравенства строгие, то получаем необходимое и достаточное условие отрицательной (положительной) определенности матрицы Гессе в точке x0. Условие (2.5) называется критерием
Сильвестра для знакоопределенных матриц.
Поскольку условия (2.4) труднопроверяемы, то при проверке
необходимых условий оптимальности в задачах (2.2) применяют
критерий Сильвестра.
Следовательно, при помощи условий (2.3)–(2.5) можно предложить следующий алгоритм решения задач (2.2) :
– вычислить все стационарные точки (найти все решения уравнения (2.3));
– выяснить характер экстремума стационарных точек (с использованием условий (2.4)–(2.5)), для чего применить критерий Сильвестра;
– среди всех точек локального максимума (минимума) найти
точки глобального максимума (минимума), сравнивая значение
функции f в этих точках.
28
Пример решения
Определить максимальное значение функции двух переменных
и оптимальные значения переменных
f(x,y) = x3 + y2 – 6xy – 39x + 18y +100.
Берём производные по переменным, приравниваем их значения
нулю и решаем систему
fx’ = 3x2 – 6y – 39 = 0;
fy’ = 2y – 6x + 18 = 0;
x2 – 2y – 13 = x2 – (6x – 18) – 13 = x2 – 6x + 5 = 0
x1 = 1, y1 =–6; x2 = 5, y2 = 6;
A = fxx″ = 6x; B = fyy″ = 2; C = fxy″ = –6;
Если A*B – C2 < 0, то анализируемая точка – точка перегиба.
Если A*B – C2 > 0 и А > 0, то в анализируемой точке функция
минимальна.
Если A*B – C2 > 0 и А < 0, а B > 0, то в анализируемой точке
функция максимальна.
В примере точка М = (1,–6) – точка перегиба, так как A*B –
C2 = 6*1*2 – 36 < 0; а точка М = (5, 6) – точка минимума, так как
A*B – C2 = 6*5*2 – 36 > 0;
Варианты заданий
1. 2x3 + 2y2 – 9xy – 27x + 12y +100
2. x3 + 3y2 – 6xy – 28x + 21y +150
3. 2 x3 + 4y2 – 9xy – 21x + 18y +100
4. x3 + 5y2 – 6xy – 39x + 21y +150
5. x3 + 2y2 – 9xy – 27x + 12y +100
6. 2x3 + y2 – 9xy – 29x + 21y +150
7. x3 + 2y2 – 6xy – 21x + 18y +100
8. 2x3 + y2 – 6xy – 39x + 12y +100
9. x3 + y2 – 9xy – 27x + 18y +150
10. 2x3 + y2 – 6xy – 21x + 21y +100
11. x3 +2 y2 – 9xy – 39x + 18y +100
12. 2x3 + y2 – 9xy – 27x + 21y +150
13. x3 + y2 – 6xy – 21x + 18y +100
14. 2x3 + 2y2 – 9xy – 27x + 21y +100
15. x3 + 2y2 – 6xy – 39x + 18y +100
29
16. 2x3 + y2 – 9xy – 21x + 21y +150
17. x3 + 2y2 – 6xy – 27x + 18y +100
18. x3 + 2y2 – 9xy – 27x + 18y +100
19. 2x3 + y2 – 6xy – 39x + 21y +150
20. x3 + 2y2 – 9xy – 39x + 18y +100
21. x3 + 2y2 – 6xy – 27x + 21y +150
22. 2x3 + y2 – 9xy – 27x + 18y +100
23. x3 + 2y2 – 6xy – 39x + 21y +100
24. 2x3 + 3y2 – 6xy – 39x + 21y +150
25. x3 + 4y2 – 7xy – 39x + 21y +200
26. x3 + 2y2 – 8xy – 39x + 21y +100
27. 2x3 + 2y2 – 9xy – 39x + 21y +150
28. x3 + 3y2 – 7xy – 39x + 21y +200
29. 2x3 + 2y2 – 9xy – 39x + 21y +100
30. x3 + 2y2 – 6xy – 39x + 21y +150
31. x3 + 2y2 – 6xy – 39x + 21y +200
32. x3 + 2y2 – 6xy – 39x + 21y +100
33. x3 + 2y2 – 6xy – 39x + 21y +150
34. x3 + 4y2 – 8xy – 39x + 21y +200
35. 2x3 + y2 – 6xy – 39x + 21y +100
36. x3 + 2y2 – 6xy – 39x + 21y +150
37. x3 + 3y2 – 9xy – 39x + 21y +200
38. 2x3 + 4y2 – 6xy – 39x + 21y +100
39. x3 + 5y2 – 6xy – 39x + 21y +150
40. x3 + 6y2 – 6xy – 39x + 21y +200
41. x3 + 5y2 – 9xy – 39x + 21y +100
42. 2x3 + 4y2 – 6xy – 39x + 21y +150
43. x3 + 6y2 – 9xy – 39x + 21y +200
44. 2x3 + 6y2 – 6xy – 39x + 21y +100
45. x3 + 6y2 – 9xy – 39x + 21y +150
46. x3 + 4y2 – 6xy – 39x + 21y +200
47. x3 + 3y2 – 6xy – 39x + 21y +100
48. 2x3 + 6y2 – 9xy – 39x + 21y +150
49. x3 + 6y2 – 6xy – 39x + 21y +200
50. 2x3 + 5y2 – 9xy – 39x + 21y +100
51. x3 + 6y2 – 6xy – 39x + 21y +150
52. x3 + 4y2 – 9xy – 39x + 21y +200
30
РАЗДЕЛ 3. ЗАДАЧИ УСЛОВНОЙ ОПТИМИЗАЦИИ
Рассмотрим задачу условной оптимизации, когда множество
допустимых решений задается с помощью системы неравенств и
уравнений:
f (x) → max(min)
при ограничениях (3.1)
gi (x) ≤ 0, i =
1,..., k,
hj (=
x) 0=
, j 1,...,m,
где gi и hj называются функциями ограничения. Если среди всех
функций f, gi, hj имеется хотя бы одна нелинейная функция, то
(3.1) называется задачей нелинейного программирования. В противном случае это есть задача линейного программирования. Считая задачу (3.1) гладкой составим для нее функцию Лагранжа, зависящую от n+k+m переменных
(x1,..., xn ; λ1,..., λ k ,µ1,...,µm )
:
k
L(x, λ,=
µ) f (x) + ∑ λ i gi (x) + ∑ µ j hj (x) (3.2)
i =1
где λ = (λ1,..., λ k ) – вектор множителей Лагранжа для неравенств, а
µ = (µ1,...,µm ) – вектор множителя Лагранжа для равенств.
В формулировке необходимых признаков применяется градиент функции L по x :
k
∇ x L(x, λ,µ) =∇f (x) + ∑ λ i ∇gi (x) + ∑ µ j ∇hj (x).
i =1
Рассматриваются
регулярные
задачи,
когда
векторы
∇ g1,...,∇gk ,∇h1,...,∇hm линейно независимы.
Теорема (необходимое условие Куна-Такера). Пусть задача гладкая. Для того, чтобы точка x0∈Rn была точкой локального минимума (максимума) в задаче (3.2) необходимо выполнение следующих
условий:
1. Стационарности:
L(x0 , λ,µ) =0 (3.3)
31
2. Дополняющей нежесткости:
k
0, i 1,..., k
∑ λi gi (x0 ) ==
i =1
(3.4)
3. Неотрицательности:
(3.5)
λ i ≥ 0, i =
1,..., k Причем все множители Лагранжа λ i и µi одновременно не могут
быть равны нулю.
С помощью условий этой теоремы можно составить следующий
алгоритм решения задачи (3.2), который называется методом множителей Лагранжа:
1. Убедиться в существовании экстремальных точек (теорема
Вейерштрасса и ее следствие);
2. Составить функцию Лагранжа (3.2) ;
3. Выписать все необходимые условия (3.3)-(3.5) ;
4. Вычислить все стационарные точки, то есть найти все решения уравнений (3.2) ;
5. Определить характер экстремума стационарных точек.
Оптимальному решению задачи соответствует (единственная) совокупность λ10 ,..., λ k0 ,µ10 ,...,µm0 множителей Лагранжа.
Поэтому для вычисления стационарных точек x0 из уравнения
(3.3) требуется предварительно найти значения всех множителей
Лагранжа. Таким образом, имеется всего n+k+m неизвестных
x10 ,..., xn0 , λ10 ,..., λ k0 ,µ10 ,...,µm0 . Для их нахождения (n – уравнений) присоединяют k-ограничений–неравенств и m – ограниченийравенств.
Введение функции Лагранжа, по существу, сводит задачу условной оптимизации к задаче безусловной оптимизации. Поэтому необходимые условия II порядка и достаточные условия для функции
Лагранжа являются обобщениями соотношения:
(
)
∇2 f ( x 0 ) =
0 〈∇2f (x0 )α, α〉 < 0 〈∇2f (x0 )α, α〉 > 0 .
и
Пример решения
Найти условный экстремум функции Z = x + 3y при ограничении x2 + y2 = 10.
Составим функцию Лагранжа
L(x,y,λ) = x + 3y + λ*(x2 + y2 – 10).
32
Определим первые производные от переменных и приравняем
их нулю.
Lx′ = 1 + 2λx = 0;
Ly′ = 3 + 2λy = 0;
Lλ′ = x2 + y2 – 10 = 0.
Определим значения переменных, удовлетворяющие системе из
трёх уравнений.
x = – 1/(2λ); y = – 3/(2λ); 1/(4λ2) + 9/(4λ2) – 10 = 0;
1/λ2 = 4; λ = ± 1/2.
Определим координаты двух точек для двух значений множителя λ.
Для λ = 1/2 x = –1; y = –3; m0(–1,–3).
Для λ = –1/2 x = 1; y = 3; m0(1,3).
Определим детерминант матрицы Гессе
j′x (m0 ) j′y (m0 )
0
′′
′′
∆ = − j′x (m0 )
Lxx
Lyx
′′
′′
j′y (m0 )
Lxy
Lyy
j′x(m0) = 2x; j′y(m0) = 2y; L″xx = 2λ; L″xy = L′yx = 0; L″yy = 2λ.
Для λ = 1/2 x = –1; y = –3; m0(–1,–3) детерминант матрицы Гессе
равен
0 −2 −6
∆ = − −2 1 0 = 40 .
−6 0 1
Минимальное значение целевой функции Zmin = x + 3y = 1*(-1) +
3*(–3) = –10.
Для λ = 1/2 x = 1; y = 3; m0(1,3) детерминант матрицы Гессе равен
0 2 6
∆ = − 2 −1 0 = −40 .
6 0 −1
Максимальное значение целевой функции Zmax = x + 3y = 1*(1)
+ 3*(3) = 10.
33
Варианты заданий
1. z = 2x + 4y при 2x2 + y2 = 15
2. z = 3x + 4y при 3x2 + y2 = 20
3. z = 4x + 5y при x2 + 2y2 = 10
4. z = 5x + 2y при x2 + 3y2 = 15
5. z = 2x + 3y при x2 + y2 = 20
6. z = 3x + 2y при 2x2 + y2 = 10
7. z = 4x + 3y при 3x2 + y2 = 15
8. z = 5x + 3y при x2 + 2y2 = 20
9. z = 7x + 5y при x2 + 3y2 = 25
10. z = 4x + 2y при x2 + y2 = 15
11. z = 5x + 6y при 2x2 + y2 = 20
12. z = 2x + 6y при 3x2 + y2 = 10
13. z = 3x + 5y при x2 + 2y2 = 15
14. z = 4x + 6y при x2 + 3y2 = 20
15. z = 5x + 7y при x2 + y2 = 10
16. z = 2x + 7y при 2x2 + y2 = 15
17. z = 3x + 6y при 3x2 + y2 = 20
18. z = 4x + 7y при x2 + 2y2 = 10
19. z = 5x + 8y при x2 + 3y2 = 15
20. z = 2x + 8y при 2x2 + y2 = 20
21. z = 3x + 7y при 3x2 + y2 = 10
22. z = 4x + 8y при x2 + 2y2 = 15
23. z = 5x + 9y при x2 + 2y2 = 20
24. z = 6x + 3y при 2x2 + y2 = 10
25. z = 7x + 3y при x2 + 2y2 = 15
26. z = 8x + 3y при x2 + 2y2 = 20
27. z = 9x + 3y при x2 + 2y2 = 25
28. z = 10x + 3y при x2 + 2y2 = 10
29. z = 2x + 9y при x2 + 2y2 = 15
30. z = 3x + 6y при x2 + 2y2 = 20
31. z = 4x + 7y при x2 + 2y2 = 25
32. z = 5x + 8y при x2 + 2y2 = 10
33. z = 6x + 9y при x2 + 2y2 = 15
34. z = 7x + 10y при x2 + 2y2 = 20
35. z = 2x + 9y при x2 + 2y2 = 25
36. z =8x + 3y при x2 + 2y2 = 10
37. z = 9x + 2y при x2 + 2y2 = 15
38. z = 2x + 4y при x2 + 2y2 = 20
39. z = 3x + 5y при x2 + 2y2 = 25
34
40. z = 4x + 6y при x2 + 2y2 = 10
41. z = 5x + 6y при x2 + 2y2 = 15
42. z = 6x + 6y при x2 + 2y2 = 20
43. z = 7x + 6y при x2 + 2y2 = 25
44. z = 8x + 9y при x2 + 2y2 = 10
45. z = 9x + 6y при x2 + 2y2 = 15
46. z = 2x + 6y при x2 + 2y2 = 20
47. z = 3x + 6y при x2 + 2y2 = 25
48. z = 4x + 5y при x2 + 2y2 = 10
49. z = 5x + 6y при x2 + 2y2 = 15
50. z = 6x + 6y при x2 + 2y2 = 20
51. z = 7x + 6y при x2 + 2y2 = 25
52. z = 8x + 6y при x2 + 2y2 = 15
35
РАЗДЕЛ 4. ОПТИМИЗАЦИЯ ЗАДАЧ ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ
Задача условной оптимизации называется задачей линейного
программирования (ЛП), если все функции – целевая и ограничений – являются линейными:
f (x)= c1x1 + c2 x2 + ... + cn xn → max
при ограничениях
a11x1 + a12 x2 + ... + a1n xn ≤ b1
a21x1 + a22 x2 + ... + a2n xn ≤ b2
...........................................
ak1x1 + ak2 x2 + ... + akn xn ≤ bk
x1 ≥ 0,..., xn ≥ 0,
(4.1)
где ci , bi , aij − const . Это – стандартная форма задачи ЛП. В общем
случае ограничения могут иметь знак « ≥ » или «=». Однако, умножая неравенство на –1 и заменяя равенство двумя неравенствами,
можно придти к стандартной форме. Кроме того, взяв вместо f(x)
функцию –f(x), можно получить задачу на минимум. Приведем основные свойства задачи ЛП.
Допустимое множество решений задачи ЛП либо пусто, либо
является выпуклым многогранником в Rn (как пересечение полупространств, описываемых ограничениями-неравенствами). Оно
может быть как ограниченным, так и неограниченным; в любом
случае это замкнутый многогранник.
Если допустимое множество не пусто, а целевая функция ограничена сверху (для задачи максимизации, а для задачи минимизации – ограничена снизу) на этом множестве, то задача ЛП имеет
оптимальное решение.
Оптимальные решения задачи ЛП (если они существуют) всегда
находятся на границе допустимого множества. Точнее, если существует единственное оптимальное решение, то им является какаялибо вершина многогранника допустимых решений; если две или
несколько вершин являются оптимальными решениями, то любая
их выпуклая комбинация также является оптимальным решением
(т. е. существует бесконечно много точек максимума или минимума).
36
Универсальный метод решения задач ЛП называется симплексметодом. Применение этого метода и его наиболее часто встречающейся модификации – двухфазного симплекс-метода мы поясним
на примерах. Идея симплекс-метода заключается в следующем.
Сначала нужно найти некоторую (начальную) вершину многогранника допустимых решений (начальное допустимое базисное решение). Затем нужно проверить это решение на оптимальность. Если
оно оптимально, то решение найдено; если нет, то перейти к другой
вершине многогранника и вновь проверить на оптимальность. Ввиду конечности вершин многогранника (следствие конечности ограничений задачи ЛП) за конечное число «шагов» мы найдем искомую
точку минимума или максимума. Надо заметить, что при переходе
от одной вершины к другой значение целевой функции убывает (в
задаче на минимум) или возрастает (в задаче на максимум).
Для ускорения решения необходимо при переходе от одной вершины к другой двигаться по такому ребру многогранника, при
перемещении по которому изменение значения целевой функции
максимально.
Пример решения 4.1
Решить следующую задачу ЛП в канонической форме симплексметодом, изображенную на рис. 4.1. Составим систему линейных
неравенств, образующих допустимое множество решений.
x2
9
8
7
6
5
B
C
D
x2opt
fmax=2x1opt+3x2opt=34
Допустимое множество E
решений
4
F
Целевая функция
3
f=2x1+3x2=6
2
G
1
0A
x1
0
1
2
3
4
5
6
7 8 9
x1opt
10 11
Рис. 4.1. Задача линейного программирования
37
Заменим обозначение целевой функции f(x) на обозначение переменной X0, приравняем её значение нулю и перенесём её переменные 2X1 и 3X2 влево от знака равно со знаком минус.
X0 – 2X1 – 3X2 = 0.
Выпишем ограничительные неравенства в виде системы.
0
X0 −2X1 −3X2 =
X1
X1
X1
2X1
X1
X2
3X2
2X2
X2
X2
≤8
≤ 27
≤ 20
≤ 14
≤ 24
≤ 11
В каждое неравенство введём по одной положительной переменной X3, …, X8, дополняющей значение левой части каждого неравенств до равенства правой части.
X0
−2X1
−3X2
X2
X1
+3X2
X1
X1
2X1
X1
+2X2
+ X2
+ X2
=
0
=
8
+ X3
+ X4
=
27
+ X5
+ X6
+ X7
+ X8
=
20
=
14
=
24
=
11
Для однозначного решения системы из шести уравнений с восемью переменными присвоим двум переменным X1 и X2 значение,
равное нулю. Остальные (базисные) переменные станут равными
значениям правых частей уравнений. Решение системы соответствует вершине А выпуклого многоугольника (симплекса) допустимых решений системы, совпадающей с началом координат (см.
рис. 4.2). Такой вид системы, в которой целевая функция выражена через переменные с нулевыми значениями (X1 и X2), а в остальных ограничительных уравнениях по одной ненулевой переменной
(X3, …, X8), называется базисным. Он позволяет определить значение целевой функции в вершине симплекса A и ребро многоугольника, при движении по которому значение целевой функции увеличивается максимально. Это ребро совпадает с X2. Переместимся
по нему до следующей вершины B. Значение X2 определяем, как
38
x2
9
8 B x2=8
C
7
6
x2opt
x1+3x2=27
D
x1+2x2=20
E
fmax=2x1opt+3x2opt=34
5
x1+x2=14
F
2x1+x2=24
4
3
2 Целевая функция
f=2x1+3x2=6
1
0
A 0
G
x1=11
x1
1
2
3
4
5
6
7
8 9
x1opt
10 11
Рис. 4.2. Значение целевой функции в оптимальной точке (8, 6)
минимальное отношение правой части в каждом уравнении к коэффициенту при переменной X2.
X2 = min (8/1, 27/3, 20/2, 14/1, 24/1, 11/0) = 8
Уравнение, которому соответствует минимальное отношение,
называется опорным и выделяется цветом. Умножая его на соответствующее число и складывая с целевой функцией или с каждым из
остальных уравнений, добиваемся того, чтобы в них коэффициент
при X2 был равен нулю. Тогда система снова примет базисный вид
для следующей вершины симплекса B и по знакам коэффициентов
в целевой функции можно будет определить, оптимальная ли эта
вершина, или нет. Для оптимальной вершины все коэффициенты
в целевой функции будут положительными и задача будет решена.
Если коэффициенты отрицательны, то выбирается отрицательный
коэффициент, наибольший по абсолютной величине. Ему соответствует ребро симплекса, при перемещении по которому значение
целевой функции увеличивается максимально. В нашем случае это
переменная Х1 (ребро ВС). По аналогии с X2 определяется минимальное значение X1, при котором текущая точка перемещается в
следующую вершину С. Выделяется соответствующее ей опорное
уравнение и с помощью него обнуляются коэффициенты при X1
в целевой функции и в остальных ограничительных уравнениях.
Получив тем самым базисный вид системы для этой вершины симплекса, определяем по виду целевой функции, оптимальна ли эта
вершина. И если нет, повторяем выбор переменной с отрицатель39
ным коэффициентом, исключая её из числа нулевых (небазисных)
в системе до тех пор, пока в уравнении целевой функции все переменные не будут с положительными коэффициентами.
Первое преобразование системы в базисную форму для вершины
B.
24
X0 −2X1
+3X3
=
X2
X1
+ X3
−3X3
−2X3
− X3
− X3
X1
X1
2X1
X1
8
=
3
=
+ X4
+ X5
+ X6
+ X7
+ X8
4
=
7
=
16
=
11
=
X1 = min (8/0, 3/1, 4/1, 7/1, 16/2, 11/1) = 3
Второе преобразование системы в базисную форму для вершины
C.
X0
X2
X1
−3X3
+ X3
−3X3
X3
+2X4
2X3
5X3
3X3
− X4
−2X4
− X4
+ X4
− X4
30
=
8
=
3
=
1
=
+ X5
+ X6
+ X7
+ X8
4
=
10
=
8
=
X3 = min (8/1, 3/–3, 1/1, 4/2, 10/5, 8/3) = 1
Третье преобразование системы в базисную форму для вершины
D.
X0
X2
X1
X3
− X4
+ X4
−2X4
− X4
2X4
+3X5
− X5
+3X5
+ X5
−2X5
3X4
2X4
−5X5
−3X5
33
=
7
=
6
=
1
=
2
=
+ X6
+ X7
+ X8
X4 = min (7/1, 6/–2, 1/–1, 2/2, 5/3, 5/2) = 1
40
5
=
5
=
Четвёртое преобразование системы в базисную форму для вершины E.
X0
+2X5 +0,5X6
=
34
X1
+2X5 +3X6
=
8
X2
− X6
=
6
Это последнее преобразование системы в базисную форму, потому что в уравнении целевой функции коэффициенты при нулевых
переменных X5 и X6 – положительны. Максимальное значение целевой функции равно 34, а оптимальные значения перменных X1 и
X2 равны соответственно 8 и 6.
Этим значениям, полученным аналитически, соответствуют
значения X0, X1 и X2, полученные графически (см.рис. 4.2)
Преобразования системы уравнений в базисную форму удобно
выполнять в приложении Excel.
На рис. 4.3 показана исходная система уравнений. Нулевую переменную X2 изменяем до 8.
Рис. 4.3. Значение целевой функции в точке (0, 0)
На рис. 4.4 показано первое преобразование системы в канонический вид для следующей вершины.
Нулевую переменную X1 увеличиваем до 3.
Рис. 4.4. Значение целевой функции в точке (0, 8)
41
На рис. 4.5 показано второе преобразование системы в канонический вид для следующей вершины.
Нулевую переменную X3 увеличиваем до 1.
Рис. 4.5. Значение целевой функции в точке (3, 8)
На рис 4.6 показано третье преобразование системы в канонический вид для следующей вершины.
Нулевую переменную X4 увеличиваем до 1.
Рис. 4.6. Значение целевой функции в точке (6, 7)
На рис. 4.7 показано последнее преобразование системы в канонический вид для следующей вершины.
Коэффициенты при нулевых переменных X5 и X6 – положительны. Значит целевая функция – максимальна, а переменные X1 и X2
– оптимальны и равны соответственно 8 и 6.
Рис. 4.7. Значение целевой функции в оптимальной точке (8, 6)
42
Варианты заданий для этого примера приведены в приложении
4.1
Пример 4.2
Решить задачу ЛП в канонической форме симплекс-методом.
f (x) =x1 + 9x2 + 5x3 + 3x4 + 4x5 + 14x6 → min
x1 + x4 =
20
x2 + x5 =
50
x3 + x6 =
30
x4 + x5 + x6 =
60
xi ≥ 0, i =
1,...,6
(4.2)
Задача ЛП имеет каноническую форму, если все ограничения
(кроме условий неотрицательности переменных) имеют вид строгих равенств, а все свободные члены неотрицательны.
Чтобы найти начальное допустимое базисное решение, систему
(2.4.6) нужно привести к «диагональному» виду. В данном примере легче всего назначить нулевые значения переменным x1 и x3, а
значения остальных выразить через них.
+ x1
+ x1
−x1
x2
x4
x5
x6
−x3
+ x3
=
40
=
20
=
10
=
30
(4.3)
Подставив их в уравнение целевой функции выразим её через x1
и x3.
f(x) +7x1 +14x3 =880
Теперь составляем начальную симплекс-таблицу (табл. 4.1).
Таблица 4.1
x0 (f)
x2
x4
x5
x6
880
40
20
10
30
x1
x2
x3
x4
x5
x6
7
1
1
–1
0
0
1
0
0
0
14
1
0
–1
1
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
43
В нулевую строчку записаны коэффициенты соответствующих
переменных при целевой функции. Так как все переменные неотрицательны, то целевая функция тем меньше, чем меньше эти коэффициенты. Отсюда критерий оптимальности: допустимое базисное решение (д.б.р.) (x0) оптимально, если в нулевой строчке нет ни
одного строго положительного числа (не считая значения целевой
функции (880)).
В нулевом столбике записаны значения базисных переменных.
Они обязательно должны быть неотрицательными. От первой по
четвертую строки написаны коэффициенты переменных из системы.
Так как x0 неоптимальное, то надо перейти к другой вершине
многогранника допустимых решений (построить новое д.б.р.). Для
этого нужно найти ведущий элемент и провести симплексное преобразование (таково требование симплекс-метода).
Ведущий элемент таблицы стоит в пересечении ведущего столбика (столбец с наибольшей положительной оценкой) и ведущей
строки (строки, соответствующей минимальному соотношению
элементов нулевого столбика к соответствующим элементам (строго положительным) ведущего столбика).
В табл. 4.1 ведущий столбик – третий столбик, и ведущая строка – четвертая строка (min{40/1,30/1}=30/1). Ведущий элемент
показывает, что базисную переменную x6 нужно заменить на небазисную x3. Тогда новыми базисными переменными будут x2, x3, x4,
x5, а небазисными –x1, x6. Это и означает переход к новой вершине
многогранника допустимых решений. Чтобы найти значения координат д.б.р. x00 нужно строить новую симплекс-таблицу и провести
в ней элементарные преобразования:
а) все элементы ведущей строки поделить на ведущий элемент,
превратив этим самым ведущий элемент в 1 (для простоты выкладок);
б) с помощью ведущего элемента (равного 1) все элементы ведущего столбика превратить в нули (аналогично методу исключения
неизвестных);
В результате в нулевом столбце получены значения новых базисных переменных x2, x3, x4, x5, (см. табл. 4.2) – базисные компоненты новой вершины x00 (небазисные компоненты x1=0, x6=0).
Как показывает табл. 4.2, новое базисное решение x00=(0, 10,
30, 20, 40, 0) неоптимально (в нулевой строке есть неотрицательная
оценка 7). Поэтому с ведущим элементом 1 (см. табл. 4.2) строим
новую симплекс-таблицу, т. е. строим новое д.б.р.
44
Таблица 4.2
x0 (f)
x2
x4
x5
x6
460
40
20
10
30
x1
x2
x3
x4
x5
x6
7
1
1
–1
0
0
1
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
1
0
–14
–1
0
1
1
Таблица 4.3
x0 (f)
x1
x4
x5
x6
390
10
10
50
30
x1
x2
x3
x4
x5
x6
0
1
0
0
0
–7
1
–1
1
0
0
0
0
0
1
0
0
1
0
0
0
0
0
1
0
–7
–1
1
0
1
Табл. 4.3 соответствует д.б.р. x000=(10,0,30,10,50,0) и оно оптимально, т.к. в нулевой строчке нет положительных оценок. Поэтому f(x000)=390 есть минимальное значение целевой функции.
Ответ: x000=(10, 0, 30, 10, 50, 0) – точка минимума, f(x000)=390.
Симплексные преобразования новых базисных решений удобно
выполнять в приложении Excel.
На рис. 4.8 показана таблица коэффициентов для исходной системы в базисном виде для вершины (x1 = 0, x3 =0). Коэффициенты
при нулевых переменных x1 и x3 – положительны. Значит целевая
функция – не минимальна. Выбираем перемещение по ребру x3 до
следующей вершины симплекса, в которой Х3 = 30.
Рис. 4.8. Значение целевой функции в вершине (x1 = 0, x3 =0)
На рис. 4.9 показана таблица коэффициентов для следующей
системы в базисном виде для вершины (x1 = 0, x6 =0).
45
Рис. 4.9. Значение целевой функции в вершине (x1 = 0, x6 =0)
На рис. 4.10 показана таблица коэффициентов для последней
системы в базисном виде для вершины (x2 = 0, x6=0).
Рис. 4.10. Значение целевой функции в вершине (x2 = 0, x6 =0)
Отрицательность коэффициентов при нулевых переменных
(x2 = 0, x6=0) в целевой функции f(x) свидетельствует о достижении
её минимального значения в этой вершине симплекса.
Варианты заданий для этого примера приведены в приложении 4.2
Пример 4.3
Решить следующую задачу ЛП в неканонической форме симплекс-методом:
f(x) = x1 – x2 – 3x3 → min
при ограничениях
2x1
−4x1
3x1
−x2
+2x2
+ x3
−x3
+ x3
≤1
≤2
≤5
Умножая обе части на –1 и прибавляя в левые части системы дополнительные (или слабые) переменные x4 ≥ 0, x5 ≥ 0, x6 ≥ 0, получим каноническую форму (слабые переменные на целевую функцию не влияют):
f(x) = x1 – x2 – 3x3 → min
при ограничениях
46
2x1
−4x1
3x1
−x2
+2x2
+ x3
− x3
+ x3
+ x4
+ x5
+ x6
=
1
=
2
=
5
x1,…, x6 ≥ 0.
Так как все слабые переменные входят со знаком «+», то их можно взять в качестве базисных и составить н.д.б.р. x0=(0,0,0,1,2,5).
В данном случае исключать базисные переменные из целевой функции нет надобности (так как они в ней отсутствуют), поэтому целевую функцию записываем сразу в виде
f (x) − x1 + x2 + 3x3 =
0
(требование симплекс-метода). С помощью н.д.б.р. x0 и ограничений составим начальную симплекс-табл. 4.4 (здесь f(x0)=0).
Таблица 4.4
f
x4
x.5
X6
0
1
2
5
x1
–1
2
–4
3
x2
1
–1
2
0
x3
3
1
–1
1
x4
0
1
0
0
x5
0
0
1
0
x6
0
0
0
1
Так как x0 неоптимален (в нулевой строке есть положительные числа 1 и 3), то с обозначенным ведущим элементом строим
новое д.б.р. И так далее. На четвертой итерации (шаге) получаем
табл. 4.5.
Таблица 4.5
f
x3
x.2
x1
–43/3
4
11/3
1/3
x1
x2
x3
x4
x5
x6
0
0
0
1
0
0
1
0
0
1
0
0
–19/3
2
–1/3
–1/2
–11/3
1
1/3
–1/3
–1/3
0
2/3
1/3
На рис. 4.11 показана таблица коэффициентов для исходной системы в базисном виде для вершины (x1 = 0, x2 = 0, x3 = 0).
Коэффициенты при нулевых переменных x2 и x3 – положительны. Значит целевая функция – не минимальна. Выбираем перемещение по ребру x3 до следующей вкршины симплекса, в которой
x3 = 1.
47
Рис. 4.11. Значение целевой функции в вершине (x1 = 0, x2 = 0, x3 = 0)
На рис. 4.12 показана таблица коэффициентов для следующей
системы в базисном виде для вершины (x1 = 0, x2 =0, x4 =0).
Рис. 4.12. Значение целевой функции в вершине (x1 = 0, x2 = 0, x4 =0)
На рис. 4.13 показана таблица коэффициентов для следующей
системы в базисном виде для вершины (x1 = 0, x4 =0, x5 =0).
Рис. 4.13. Значение целевой функции в вершине (x1 = 0, x4 = 0, x5 =0)
На рис. 4.14 показана таблица коэффициентов для последней
системы в базисном виде для вершины (x4 = 0, x5 =0, x6 =0).
Рис. 4.14. Значение целевой функции в вершине (X4 = 0, X5 =0, X6 =0)
Как видно из последней таблицы, оптимальным решением задачи является x0000=(1/3, 11/3, 4) и f(x0000)=–46/3.
Варианты заданий для этого примера приведены в приложении
4.3.
Алгоритм симплекс-метода:
1. Привести задачу к канонической форме:
2. Привести систему ограничений к диагональной форме и определить базисные переменные;
48
3. Исключить базисные переменные из целевой функции;
4. Построить симплекс-таблицу;
5. Проверить найденное д.б.р. на оптимальность: если оно оптимально, то решение закончить; если нет, то идти к пункту 6;
6. Вычислить ведущий элемент таблицы;
7. Провести симплексное преобразование;
8. Построить новое д.б.р. и идти к пункту 5.
Если в ведущем столбике нет ни одного строго положительного элемента, то задача не имеет оптимального решения, а целевая
функция не ограничена снизу (в задаче на минимум) или не ограничена сверху (в задаче на максимум).
Несовместимость системы ограничений (в канонической форме)
обнаруживается при построении начального д.б.р. (оно не существует).
Симплекс-метод за конечное число итераций либо приводит к
оптимальному решению, либо устанавливает неразрешимость задачи (см. пп. 1,2,3).
На каждой итерации симплекс-метод сохраняет допустимость
базисного решения, т. е. неотрицательность элементов нулевого
столбика – следствие правила выбора ведущей строки.
На каждой итерации целевая функция убывает (в задаче на минимум) или возрастаем (в задаче на максимум); это свойство нарушается только в случае зацикливания (см. примечания 11,12).
В качестве ведущего столбика можно выбирать любой столбик
с положительной оценкой (в задаче на минимум), однако максимальность оценки ведущего столбика ведет к сокращению числа
итераций (целевая функция быстро убывает).
Приложение 4.1
Варианты заданий для примера 4.1
01
F(x)=(2,0;0,3), Ограничения: (0,0;0,8;3,8;6,7;9,4;10,2;10,0)
02
F(x)=(2,0;0,3), Ограничения: (0,0;0,8;4,8;8,7;10,5;11;3;11,0)
03
F(x)=(2,0;0,3), Ограничения: (0,0;0,6;3,6;6,5;8,4;10,2;10,0)
49
04
F(x)=(2,0;0,3), Ограничения: (0,0;0,7;2,7;6,6;8,4;9,2;9,0)
05
F(x)=(2,0;0,3), Ограничения: (0,0;0,7;4,7;7,6;9,5;10,4;11,2;11,0)
06
F(x)=(2,0;0,3), Ограничения: (0,0;0,8;2,8;6,7;9,6;10,5;11,2;11,0)
07
F(x)=(2,0;0,3), Ограничения: (0,0;0,9;3,9;6,8;8,7;9,6;10,3;10,0)
08
F(x)=(2,0;0,3), Ограничения: (0,0;0,9;3,9;6,8;8,7;9,6;10,4;10,0)
09
F(x)=(2,0;0,3), Ограничения: (0,0;0,9;4,9;7,8;9,6;10,310,0)
10
F(x)=(2,0;0,3), Ограничения: (0,0;0,9;4,9;8,8;10,7;11,5;11,0)
11
F(x)=(5,0;0,2), Ограничения: (0,0;0,6;3,6;6,5;8,4;9,3;10,1;10,0)
12
F(x)=(5,0;0,2), Ограничения: (0,0;0,8;3,8;6,7;8,5;10,2;10,0)
13
F(x)=(4,0;0,3), Ограничения: (0,0;0,9;5,9;10,8;13,7;14,6;15,3;15,0)
14
F(x)=(4,0;0,3), Ограничения: (0,0;0,7;4,7;8,6;11,5;12,4;13,2;13,0)
15
F(x)=(4,0;0,3), Ограничения: (0,0;0,9;5,9;10,8;12,7;13,6;14,3;14,0)
16
F(x)=(6,0;0,5), Ограничения: (0,0;0,10;4,10;8,9;10,8;12,6;13,3;13,0)
17
F(x)=(4,0;0.3), Ограничения: (0,0;0,7;5,7;10,6;12,5;13,4;14,2;14,0)
18
F(x)=(4,0;0,5), Ограничения: (0,0;0,10;4,10;8,9;11,7;12,6;14,3;14,0)
19
F(x)=(6,0;0,5), Ограничения: (0,0;0,10;4,10;8,9;11,7;12,6;14,3;14,0)
20
F(x)=(8,0;0,5), Ограничения: (0,0;0,10;4,10;8,9;11,7;12,6;14,3;14,0)
50
21
F(x)=(3,0;0,5), Ограничения: (0,0;0,10;4,10;8,9;10,8;12,6;13,3;13,0)
22
F(x)=(4,0;0,5), Ограничения: (0,0;0,10;5,10;10,9;12,8;14,3;14,0)
23
F(x)=(2,0;0.5), Ограничения: (0,0;0,10;5,10;10,9;12,8;14,5;14,0)
24
F(x)=(7,0;0,5), Ограничения: (0,0;0,10;5,10;10,9;12,7;13,5;14,2;14,0)
25
F(x)=(7,0;0,5), Ограничения: (0,0;0,10;6,10;9,9;12,6;14,3;14,0)
26
F(x)=(4,0;0,5), Ограничения: (0,0;0,10;6,10;9,9;12,6;14,2;14,0)
27
F(x)=(3,0;0,4), Ограничения: (0,0;0,8;3,8;9,7;12,6;13,5;14,3;14,0)
28
F(x)=(3,0;0,4), Ограничения: (0,0;0,9;4,9;8,8;10,7;13,4;14,2;14,0)
29
F(x)=(3,0;0,4), Ограничения: (0,0;0,10;3,10;9,9;12,8;13,6;14,3;14,0)
30
F(x)=(3,0;0,5), Ограничения: (0,0;0,10;3,10;9,9;12,8;13,5;14,1;14,0)
31
F(x)=(8,0;0,5), Ограничения: (0,0;0,10;3,10;8,9;12,8;13,6;14,3;14,0)
32
F(x)=(8,0;0,5), Ограничения: (0,0;0,8;5,8;10,7;12,6;13,5;14,3;14,0)
33
F(x) = (6,0;0,4); Ограничения: (0,0;0,14;6,14;12,12;18,8;20,4;20,0)
34
F(x) = (6,0;0,4); Ограничения: (0,0;0,14;4,14;12,12;18,8;20,6;22,2;22,0)
35
F(x) = (6,0;0,8); Ограничения: (0,0;0,14;4,14;12,12;18,8;20,6;22,2;22,
0)
36
F(x) = (6,0;0,8); Ограничения: (0,0;0,16;4,16;12,14;16,12;20,8;22,4;
22,0)
51
37
F(x) = (6,0;0,4); Ограничения: (0,0;0,16;4,16;12,14;16,12;20,8;22,4;
22,0)
38
F(x) = (8,0;0,6); Ограничения: (0,0;0,16;4,16;12,14;16,12;20,8;22,4;
22,0)
39
F(x) = (6,0;0,8); Ограничения: (0,0;0,16;4,16;12,14;16,12;20,8;22,4;
22,0)
40
F(x) = (6,0;0,10); Ограничения: (0,0;0,16;4,16;12,14;16,12;20,8;22,4;
22,0)
41
F(x) = (4,0;0,10); Ограничения: (0,0;0,16;4,16;12,14;16,12;20,8;22,4;
22,0)
42
F(x) = (10,0;0,4); Ограничения: (0,0;0,16;4,16;12,14;16,12;20,8;22,4;
22,0)
43
F(x) = (10,0;0,4); Ограничения: (0,0;0,16;6,16;12,14;16,12;20,8;22,4;
22,0)
44
F(x) = (8,0;0,10); Ограничения: (0,0;0,16;6,16;12,14;16,12;20,8;22,4;
22,0)
45
F(x) = (6,0;0,4); Ограничения: (0,0;0,16;6,16;12,14;16,12;20,8;22,4;
22,0)
46
F(x) = (4,0;0,6); Ограничения: (0,0;0,16;6,16;12,14;16,12;20,8;22,4;
22,0)
47
F(x) = (4,0;0,8); Ограничения: (0,0;0,16;6,16;12,14;16,12;20,8;22,4;
22,0)
48
F(x) = (4,0;0,10); Ограничения: (0,0;0,16;6,16;12,14;16,12;20,8;22,4;
22,0)
52
49
F(x) = (4,0;0,10); Ограничения: (0,0;0,16;8,16;14,14;18,12;20,8;22,2;
22,0)
50
F(x) = (6,0;0,8); Ограничения: (0,0;0,16;8,16;14,14;18,12;20,8;22,2;
22,0)
51
F(x) = (8,0;0,6); Ограничения: (0,0;0,16;8,16;14,14;18,12;20,8;22,2;
22,0)
52
F(x) = (8,0;0,4); Ограничения: (0,0;0,16;8,16;14,14;18,12;20,8;22,2;
22,0)
Приложение 4.2
Варианты заданий для примера 4.2
01
f(x) = x1 + 7x2 + 5x3 + 5x4 + 4x5 + 13x6 → min
x1 + x4 = 40
x2 + x5 = 50
x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
02
f(x) = x1 + 9x2 + 7x3 + 3x4 + 4x5 + 12x6 → min
x1 + x4 = 70
x2 + x5 = 50
x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
03
f(x) = x1 + 9x2 + 5x3 + 7x4 + 4x5 + 15x6 → min
x1 + x4 = 20
x2 + x5 = 50
x3 + x6 = 30
x4 + x5 + x6 = 70
xi ≥ 0, i =1,…,6
53
04
f(x) = x1 + 5x2 + 5x3 + 3x4 + 4x5 + 11x6 → min
x1 + x4 = 20
x2 + x5 = 50
x3 + x6 = 40
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
05
f(x) = x1 + 9x2 + 5x3 + 3x4 + 4x5 + 18x6 → min
x1 + x4 = 50
x2 + x5 = 30
x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
06
f(x) = x1 + 9x2 + 7x3 + 3x4 + 4x5 + 10x6 → min
x1 + x4 = 20
x2 + x5 = 50
x3 + x6 = 60
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
07
f(x) = x1 + 9x2 + 5x3 + 3x4 + 4x5 + 19x6 → min
x1 + x4 = 20
x2 + x5 = 50
x3 + x6 = 90
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
08
f(x) = 2x1 + 11x2 + 5x3 + 7x4 + 4x5 + 14x6 → min
x1 + x4 = 40
x2 + x5 = 50
x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
09
f(x) = x1 + 9x2 + 9x3 + 3x4 + 5x5 + 14x6 → min
x1 + x4 = 20
54
x2 + x5 = 50
x3 + x6 = 40
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
10
f(x) = x1 + 9x2 + 5x3 + 3x4 + 4x5 + 12x6 → min
x1 + x4 = 50
x2 + x5 = 50
x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
11
f(x) = x1 + 9x2 + 5x3 + 3x4 + 9x5 + 14x6 → min
x1 + x4 = 20
x2 + x5 = 50
x3 + x6 = 70
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
12
f(x) = x1 + 9x2 + 5x3 + 5x4 + 4x5 + 14x6 → min
x1 + x4 = 40
x2 + x5 = 50
x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
13
f(x) = 3x1 + 9x2 + 5x3 + 3x4 + 4x5 + 12x6 → min
x1 + x4 = 40
x2 + x5 = 50
x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
14
f(x) = x1 + 9x2 + 5x3 + 7x4 + 4x5 + 14x6 → min
x1 + x4 = 80
x2 + x5 = 50
x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
55
15
f(x) = x1 + 9x2 + 5x3 + 4x4 + 4x5 + 14x6 → min
x1 + x4 = 60
x2 + x5 = 50
x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
16
f(x) = x1 + 11x2 + 5x3 + 3x4 + 4x5 + 14x6 → min
x1 + x4 = 20
x2 + x5 = 90
x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
17
f(x) = x1 + 9x2 + 5x3 + 3x4 + 8x5 + 14x6 → min
x1 + x4 = 80
x2 + x5 = 50
x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
18
f(x) = 2x1 + 9x2 + 3x3 + 3x4 + 4x5 + 14x6 → min
x1 + x4 = 40
x2 + x5 = 50
x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
19
f(x) = x1 + 9x2 + 5x3 + 5x4 + 4x5 + 14x6 → min
x1 + x4 = 60
x2 + x5 = 50
x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
20
f(x) = x1 + 9x2 + 5x3 + 3x4 + 4x5 + 19x6 → min
x1 + x4 = 90
x2 + x5 = 50
56
x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
21
f(x) = x1 + 9x2 + 5x3 + 7x4 + 4x5 + 14x6 → min
x1 + x4 = 20
x2 + x5 = 20
x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
22
f(x) = x1 + 9x2 + 5x3 + 3x4 + 14x5 + 14x6 → min
x1 + x4 = 20
x2 + x5 = 50
x3 + x6 = 70
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
23
f(x) = x1 + 9x2 + 5x3 + 13x4 + 4x5 + 14x6 → min
x1 + x4 = 20
x2 + x5 = 50
x3 + x6 = 70
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
24
f(x) = x1 + 9x2 + 15x3 + 3x4 + 4x5 + 14x6 → min
x1 + x4 = 20
x2 + x5 = 50
x3 + x6 = 90
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
25
f(x) = x1 + 9x2 + 5x3 + 3x4 + 9x5 + 14x6 → min
x1 + x4 = 20
x2 + x5 = 50
x3 + x6 = 80
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
57
26
f(x) = x1 + 9x2 + 5x3 + 3x4 + 4x5 + 10x6 → min
x1 + x4 = 20
x2 + x5 = 50
x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
27
f(x) = x1 + 9x2 + 5x3 + 3x4 + 9x5 + 14x6 → min
x1 + x4 = 50
x2 + x5 = 50
x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
28
f(x) = x1 + 9x2 + 5x3 + 7x4 + 4x5 + 14x6 → min
x1 + x4 = 50
x2 + x5 = 50
x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
29
f(x) = x1 + 9x2 + 5x3 + 8x4 + 4x5 + 14x6 → min
x1 + x4 = 80
x2 + x5 = 50
x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
30
f(x) = 3x1 + 9x2 + 6x3 + 3x4 + 4x5 + 14x6 → min
x1 + x4 = 50
x2 + x5 = 50
x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
31
f(x) = x1 + 9x2 + 5x3 + 7x4 + 4x5 + 14x6 → min
x1 + x4 = 20
x2 + x5 = 50
58
x3 + x6 = 70
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
32
f(x) = x1 + 5x2 + 5x3 + 8x4 + 4x5 + 14x6 → min
x1 + x4 = 70
x2 + x5 = 50
x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
33
f(x) = x1 + 7x2 + 5x3 + 5x4 + 4x5 + 14x6 → min
x1 + x4 = 20
x2 + x5 = 50
x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
34
f(x) = x1 + 9x2 + 5x3 + 3x4 + 4x5 + 14x6 → min
x1 + x4 = 20
x2 + x5 = 50
x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
35
f(x) = x1 + 9x2 + 5x3 + 3x4 + 4x5 + 14x6 → min
x1 + x4 = 20
x2 + x5 = 50
x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
36
f(x) = x1 + 9x2 + 5x3 + 3x4 + 4x5 + 14x6 → min
x1 + 2 x4 = 40
x2 + x5 = 50
2x3 + x6 = 30
x4 + 5x5 + x6 = 60
xi ≥ 0, i =1,…,6
59
37
f(x) = x1 + 9x2 + 5x3 + 3x4 + 4x5 + 14x6 → min
x1 + 2 x4 = 20
x2 + x5 = 50
2x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
38
f(x) = x1 + 9x2 + 5x3 + 3x4 + 4x5 + 14x6 → min
x1 + 2x4 = 20
x2 + x5 = 50
2x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
39
f(x) = x1 + 9x2 + 5x3 + 3x4 + 4x5 + 14x6 → min
x1 + 2x4 = 20
x2 + x5 = 50
2x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
40
f(x) = x1 + 9x2 + 5x3 + 3x4 + 4x5 + 14x6 → min
x1 + 2x4 = 20
x2 + x5 = 50
2x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
41
f(x) = x1 + 9x2 + 5x3 + 3x4 + 4x5 + 14x6 → min
x1 + 2x4 = 20
x2 + x5 = 50
2x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
42
f(x) = x1 + 9x2 + 5x3 + 3x4 + 4x5 + 14x6 → min
x1 + 2x4 = 20
x2 + x5 = 50
60
2x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
43
f(x) = x1 + 9x2 + 5x3 + 3x4 + 4x5 + 14x6 → min
x1 + 2x4 = 20
x2 + x5 = 50
2x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
44
f(x) = x1 + 9x2 + 5x3 + 3x4 + 4x5 + 14x6 → min
x1 + 2x4 = 20
x2 + x5 = 50
2x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
45
f(x) = x1 + 9x2 + 5x3 + 3x4 + 4x5 + 14x6 → min
x1 + 2x4 = 20
x2 + x5 = 50
2x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
46
f(x) = x1 + 7x2 + 5x3 + 3x4 + 4x5 + 13x6 → min
x1 + 2x4 = 40
x2 + x5 = 50
2x3 + x6 = 40
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
47
f(x) = x1 + 7x2 + 5x3 + 3x4 + 4x5 + 14x6 → min
x1 + 2x4 = 50
x2 + x5 = 50
2x3 + x6 = 60
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
61
48
f(x) = x1 + 7x2 + 5x3 + 5x4 + 4x5 + 13x6 → min
x1 + 2x4 = 40
x2 + x5 = 50
2x3 + x6 = 60
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
49
f(x) = x1 + 7x2 + 5x3 + 3x4 + 4x5 + 15x6 → min
x1 + 3 x4 = 40
3x2 + x5 = 50
x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
50
f(x) = x1 + 11x2 + 5x3 + 5x4 + 4x5 + 15x6 → min
x1 + 3x4 = 30
x2 + x5 = 50
3x3 + x6 = 40
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
51
f(x) = x1 + 11x2 + 5x3 + 5x4 + 9x5 + 13x6 → min
x1 + 4x4 = 20
x2 + x5 = 50
3x3 + x6 = 30
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
52
f(x) = x1 + 11x2 + 5x3 + 3x4 + 4x5 + 14x6 → min
x1 + 2x4 = 30
x2 + x5 = 50
3x3 + x6 = 60
x4 + x5 + x6 = 60
xi ≥ 0, i =1,…,6
62
Приложение 4.3
Варианты заданий для примера 4.3
01
F (x) = x1 – 2x2 – 3x3 → min
2x1 – x2 + 3x3 + x4 = 1
–4x1 + 2x2 – 4x3 + x5 = 2
3x1 + x3 + x6 = 5
x1,…, x6 ≥ 0
02
F (x) = 2x1 – x2 – 3x3 → min
2x1 – x2 + x3 + x4 = 1
–4x1 + 2x2 – 4x3 + x5 = 2
3x1 + 5x3 + x6 = 5
x1,…, x6 ≥ 0
03
F (x) = x1 – 3x2 – 3x3 → min
2x1 – x2 + 2x3 + x4 = 1
–4x1 + 2x2 – 4x3 + x5 = 2
3x1 + x3 + x6 = 5
x1,…, x6 ≥ 0
04
F (x) = x1 – x2 – 4x3 → min
2x1 – x2 + 2x3 + x4 = 1
–4x1 + 2x2 – 3x3 + x5 = 3
3x1 + x3 + x6 = 5
x1,…, x6 ≥ 0
05
F (x) = x1 – 2x2 – 5x3 → min
2x1 – 2x2 + x3 + x4 = 1
–4x1 + 2x2 – 3x3 + x5 = 2
3x1 + x3 + x6 = 6
x1,…, x6 ≥ 0
06
F (x) = x1 – 4x2 – 3x3 → min
2x1 – 2x2 + 5x3 + x4 = 1
–4x1 + 2x2 – 4x3 + x5 = 2
63
3x1 + x3 + x6 = 5
x1,…, x6 ≥ 0
07
F(x) = x1 – x2 – 3x3 → min
2x1 – x2 + 3x3 + x4 = 3
–4x1 + 2x2 – 4x3 + x5 = 2
3x1 + x3 + x6 = 5
x1,…, x6 ≥ 0
08
F(x) = x1 – 4x2 – 3x3 → min
2x1 – x2 + x3 + x4 = 2
–4x1 + 2x2 – x3 + x5 = 2
3x1 + 2x3 + x6 = 5
x1,…, x6 ≥ 0
09
F(x) = x1 – 3x2 – 3x3 → min
2x1 – 5x2 + x3 + x4 = 1
–4x1 + 2x2 – 3x3 + x5 = 3
3x1 + x3 + x6 = 5
x1,…, x6 ≥ 0
10
F(x) = x1 – x2 – 3x3 → min
2x1 – x2 + x3 + x4 = 1
–4x1 + 2x2 – x3 + x5 = 3
3x1 + x3 + x6 = 5
x1,…, x6 ≥ 0
11
F(x) = x1 – 2x2 – 3x3 → min
2x1 – x2 + x3 + x4 = 1
–4x1 + 2x2 – x3 + x5 = 3
3x1 + 2x3 + x6 = 5
x1,…, x6 ≥ 0
12
F(x) = x1 – x2 – 3x3 → min
2x1 – x2 + 3x3 + x4 = 1
–4x1 + 2x2 – 4x3 + x5 = 2
3x1 + x3 + x6 = 5
x1,…, x6 ≥ 0
64
13
F(x) = x1 – x2 – 3x3 → min
2x1 – x2 + 3x3 + x4 = 1
–4x1 + 2x2 – 4x3 + x5 = 4
3x1 + x3 + x6 = 5
x1,…, x6 ≥ 0
14
F(x) = x1 – 2x2 – 3x3 → min
2x1 – x2 + x3 + x4 = 1
–4x1 + 2x2 – 2x3 + x5 = 3
3x1 + x3 + x6 = 5
x1,…, x6 ≥ 0
15
F(x) = x1 – x2 – 3x3 → min
2x1 – x2 + 3x3 + x4 = 1
–4x1 + 2x2 – 2x3 + x5 = 2
3x1 + x3 + x6 = 5
x1,…, x6 ≥ 0
16
F(x) = x1 – x2 – 3x3 → min
2x1 – x2 + x3 + x4 = 1
–4x1 + 2x2 – x3 + x5 = 2
3x1 +2x3 + x6 = 5
x1,…, x6 ≥ 0
17
F(x) = x1 – x2 – 3x3 → min
2x1 – x2 + x3 + x4 = 1
–4x1 + 2x2 – x3 + x5 = 2
3x1 + x3 + x6 = 6
x1,…, x6 ≥ 0
18
F(x) = x1 – 2x2 – 3x3 → min
2x1 – x2 + 3x3 + x4 = 2
–4x1 + 2x2 – x3 + x5 = 3
3x1 + x3 + x6 = 5
x1,…, x6 ≥ 0
19
F(x) = x1 – x2 – 3x3 → min
65
2x1 – x2 + 3x3 + x4 = 1
–4x1 + 2x2 – 4x3 + x5 = 2
3x1 + 4x3 + x6 = 5
x1,…, x6 ≥ 0
20
F(x) = x1 – 7x2 – 3x3 → min
2x1 – x2 + 3x3 + x4 = 1
–4x1 + 2x2 – 4x3 + x5 = 4
3x1 + x3 + x6 = 7
x1,…, x6 ≥ 0
21
F(x) = x1 – x2 – 3x3 → min
2x1 – x2 + 3x3 + 4x4 = 1
–4x1 + 2x2 – x3 + x5 = 2
3x1 + x3 + x6 = 5
x1,…, x6 ≥ 0
22
F(x) = x1 – 2x2 – 3x3 → min
2x1 – x2 + x3 + x4 = 1
–4x1 + 2x2 – 4x3 + x5 = 2
3x1 + 4x3 + x6 = 5
x1,…, x6 ≥ 0
23
F(x) = x1 – x2 – 3x3 → min
2x1 – x2 + 3x3 + x4 = 1
–4x1 + 2x2 – x3 + x5 = 2
3x1 + 2x3 + x6 = 5
x1,…, x6 ≥ 0
24
F(x) = x1 – 2x2 – 3x3 → min
2x1 – x2 + 3x3 + x4 = 1
–4x1 + 2x2 – 4x3 + x5 = 7
3x1 + x3 + x6 = 5
x1,…, x6 ≥ 0
25
F(x) = x1 – 2x2 – 3x3 → min
2x1 – x2 + 3x3 + x4 = 1
–4x1 + 2x2 – 3x3 + x5 = 2
66
3x1 + x3 + x6 = 7
x1,…, x6 ≥ 0
26
F(x) = x1 – 2x2 – 3x3 → min
2x1 – x2 + 3x3 + x4 = 3
–4x1 + 2x2 – x3 + x5 = 2
3x1 + x3 + x6 = 7
x1,…, x6 ≥ 0
27
F(x) = x1 – 2x2 – 3x3 → min
2x1 – x2 + 3x3 + x4 = 1
–4x1 + 2x2 – x3 + x5 = 6
3x1 + x3 + x6 = 5
x1,…, x6 ≥ 0
28
F(x) = x1 – 2x2 – 3x3 → min
2x1 – x2 + 2x3 + x4 = 1
–4x1 + 2x2 – 4x3 + x5 = 2
3x1 + x3 + x6 = 5
x1,…, x6 ≥ 0
29
F(x) = x1 – 42x2 – 3x3 → min
2x1 – x2 + 3x3 + x4 = 4
–4x1 + 2x2 – 4x3 + x5 = 2
3x1 + x3 + x6 = 5
x1,…, x6 ≥ 0
30
F(x) = x1 – 2x2 – 3x3 → min
2x1 – x2 + 3x3 + x4 = 1
–4x1 + 2x2 – x3 + x5 = 2
3x1 + 5x3 + x6 = 5
x1,…, x6 ≥ 0
31
F(x) = x1 – 2x2 – 3x3 → min
2x1 – x2 + x3 + x4 = 1
–4x1 + 2x2 – x3 + x5 = 2
3x1 + x3 + x6 = 5
x1,…, x6 ≥ 0
67
32
F(x) = x1 – 2x2 – 3x3 → min
2x1 – x2 + 3x3 + x4 = 2
–4x1 + 2x2 – 4x3 + x5 = 4
3x1 + x3 + x6 = 5
x1,…, x6 ≥ 0
33
F(x) = 2x1 – 2x2 – 3x3 → min
2x1 – x2 + x3 + x4 = 5
–4x1 + 2x2 – 4x3 + x5 = 2
3x1 + x3 + x6 = 5
x1,…, x6 ≥ 0
34
F(x) = x1 – 2x2 – 3x3 → min
2x1 – x2 + x3 + x4 = 3
–4x1 + 2x2 – 4x3 + x5 = 2
3x1 + 2x3 + x6 = 5
x1,…, x6 ≥ 0
35
F(x) = x1 – 4x2 – 3x3 → min
2x1 – x2 + x3 + x4 = 1
–4x1 + 2x2 – x3 + x5 = 2
3x1 + 2x3 + x6 = 5
x1,…, x6 ≥ 0
36
F(x) = 3x1 – 2x2 – 3x3 → min
2x1 – x2 + 3x3 + x4 = 1
–4x1 + 2x2 – 4x3 + x5 = 3
3x1 + x3 + x6 = 5
x1,…, x6 ≥ 0
37
F(x) = x1 – 4x2 – 3x3 → min
2x1 – x2 + 3x3 + x4 = 3
–4x1 + 2x2 – 4x3 + x5 = 2
3x1 + x3 + x6 = 5
x1,…, x6 ≥ 0
38
F(x) = x1 – 2x2 – 3x3 → min
68
2x1 – x2 + 3x3 + x4 = 5
–4x1 + 2x2 – x3 + x5 = 2
3x1 + x3 + x6 = 3
x1,…, x6 ≥ 0
39
F(x) = x1 – 2x2 – 3x3 → min
2x1 – x2 + 3x3 + x4 = 3
–3x1 + 2x2 – 4x3 + x5 = 2
3x1 + 2x3 + x6 = 5
x1,…, x6 ≥ 0
40
F(x) = x1 – 2x2 – 3x3 → min
2x1 – x2 + x3 + x4 = 5
4x1 + 2x2 – 2x3 + x5 = 2
3x1 + x3 + x6 = 5
x1,…, x6 ≥ 0
41
F(x) = x1 – 2x2 – 5x3 → min
2x1 – x2 + 3x3 + x4 = 6
–4x1 + 2x2 – 4x3 + x5 = 2
3x1 + x3 + x6 = 4
x1,…, x6 ≥ 0
42
F(x) = 2x1 – 2x2 – 3x3 → min
2x1 – x2 + 3x3 + x4 = 6
–4x1 + 2x2 – 4x3 + x5 = 2
3x1 + x3 + x6 = 5
x1,…, x6 ≥ 0
43
F(x) = x1 – 2x2 – 3x3 → min
2x1 – x2 + 3x3 + x4 = 5
–4x1 + 2x2 – 4x3 + x5 = 2
3x1 + 2x3 + x6 = 3
x1,…, x6 ≥ 0
44
F(x) = 2x1 – 2x2 – 3x3 → min
2x1 – x2 + 3x3 + x4 = 4
–4x1 + 2x2 – 4x3 + x5 = 6
69
3x1 + x3 + x6 = 5
x1,…, x6 ≥ 0
45
F(x) = x1 – 2x2 – 3x3 → min
2x1 – x2 + 3x3 + x4 = 3
–4x1 + 2x2 – 2x3 + x5 = 6
3x1 + x3 + x6 = 5
x1,…, x6 ≥ 0
46
F(x) = x1 – 2x2 – 3x3 → min
2x1 – x2 + 3x3 + x4 = 3
–4x1 + 2x2 – 3x3 + x5 = 5
3x1 + x3 + x6 = 5
x1,…, x6 ≥ 0
47
F(x) = 2x1 – 2x2 – 3x3 → min
2x1 – x2 + 3x3 + x4 = 4
–4x1 + 2x2 – 4x3 + x5 = 5
3x1 + x3 + x6 = 6
x1,…, x6 ≥ 0
48
F(x) = x1 – 2x2 – 3x3 → min
2x1 – x2 + 3x3 + x4 = 7
–4x1 + 2x2 – 4x3 + x5 = 6
3x1 + x3 + x6 = 5
x1,…, x6 ≥ 0
49
F(x) = x1 – 2x2 – 3x3 → min
2x1 – x2 + 3x3 + x4 = 8
–4x1 + 2x2 – 2x3 + x5 = 7
3x1 + x3 + x6 = 5
x1,…, x6 ≥ 0
50
F(x) = 4x1 – 2x2 – 3x3 → min
2x1 – x2 + 3x3 + x4 = 4
–4x1 + 2x2 – 3x3 + x5 = 3
3x1 + 2x3 + x6 = 5
x1,…, x6 ≥ 0
70
51
F(x) = x1 – 2x2 – 3x3 → min
2x1 – x2 + 3x3 + x4 = 7
–4x1 + 2x2 – 2x3 + x5 = 6
3x1 + 2x3 + x6 = 5
x1,…, x6 ≥ 0
52
F(x) = x1 – 3x2 – 4x3 → min
2x1 – x2 + 3x3 + x4 = 5
–4x1 + 2x2 – x3 + x5 = 4
3x1 + x3 + x6 = 5
x1,…, x6 ≥ 0
71
РАЗДЕЛ 5. ЦЕЛОЧИСЛЕННОЕ РЕШЕНИЕ ЗАДАЧ
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Определить оптимальные целочисленные переменные xj, j = 1,..,
n в области их определения (6), при которых целевая функция F(x)
достигает экстремального значения.
F(x) = Σ сj*xj → max (min)
(5.1)
Σ aij*xj = bj, i = 1,..,m
(5.2)
xj ≥ 0 и целочисленные (5.3)
Алгоритм определения оптимального целочисленного решения
заключается в решении задачи симплекс-методом. Если решение
целочисленное, цель достигнута. В противном случае следует добавить целочисленное ограничение, полученное из уравнения базисной переменной с нецелочисленным значением и повторить решение задачи симплекс-методом.
Вывод вставляемого в систему (5.2) ограничения, отсекающего
нецелочисленное решение. Пусть оптимальное решение (5.1) существует и имеет конечное значение.
Пусть
Σ aj*xj = b (5.4)
сумма нескольких уравнений из (5.2), каждое из которых умножено на некоторое число.
Решение, удовлетворяющее системе (5.2), удовлетворяет и уравнению (5.4).
Решение задачи может быть нецелочисленным. В этом случае
некоторые коэффициенты aj и b – не целочисленные. Чтобы получить целочисленные значения переменных xj, надо значения нецелочисленных коэффициентов aj и правой части b заменить на
целочисленные [aj] и [ b], такие, что aj = [aj] + fj и b = [ b] + f, где
0 ≤ fj , f ≤ 1.
При замене в (5.4) нецелочисленных aj и b на целочисленные [aj]
и [ b] это равенство станет неравенством:
Σ [aj]xj ≤ [b] (5.5)
В самом деле, пусть 7x1 +4.5x2 = 31.5. Заменим 4.5 на 4, а 31.5
на 31.
72
Тогда левая часть 7x1 + 4x2 = 28 станет меньше 31. То есть
7x1 + 4x2 < 31.
Добавим слева в (5.5) переменную x, которая для сохранения
равенства должна быть целочисленной. Получим целочисленное
уравнение
Σ [aj] xj + x = [b],
(5.6)
которое при введении в систему уравнений (5.2), позволит отсечь
нецелочисленное решение. При решении задачи ЦЛП удобнее использовать другую форму этого ограничения, получаемую вычитанием равенства (5.5) из уравнения (5.6). При этом получим:
(Σ [aj]xj + x) – Σ ajxj = [b] – b , или
Σ [–fj]xj + x = –f (5.7)
Приведём вывод отсекающего ограничения (5.7) из уравнения
нецелочисленной базисной переменной. Пусть уравнение базисной
переменной имеет вид:
xk + Σ tijxj = b,
(5.8)
где xk – базисная переменная; i – строка; j – небазисные (с нулевыми значениями) переменные.
Пусть некоторые tij = [tij] + fij и b = [ b] + f – нецелочисленные, тогда добавляется целочисленное ограничение, отсекающее нецелочисленное решение задачи:
(xk + Σ [tij]xj + x) – (xk + Σ tijxj)= [b] – b или
Σ [–fj]xj + x = –f (5.9)
Рассмотрим пример.
21x1 + 11x2 → max
7x1 + 4x2 ≤ 13
Необходимо получить целочисленное решение, максимизирующее цедевую функцию.
Обозначим целевую функцию через x0 и добавим переменную x3
в ограничение
x0
−21x1
7x1
−11x2
+4x2
+ x3
=
0
=
13
73
Выводим переменную x1 из числа нулевых, умножая ограничительное уравнение на три и складывая его с целевой функцией. Получаем базисную систему для следующей вершины симплекса
x0
7x1
+ x2
+4x2
+3x3
+ x3
=
39
=
13
Переменные x2 и x3 равны нулю, но переменная x1 является нецелочисленной и равна 13/7. Делим ограничительное уравнение
на 7 и добавляем уравнение с целочисленной переменной x4, отсекающее нецелочисленное решение x1 = 13/7. Считаем его опорным
и исключаем переменную x2 из нулевых со значением, перемещающим базис в следующую вершину симплекса. Выбор переменной x2 вместо x3 позволяет уменьшить значение целевой функции
x0 = 39 на минимальную величину
+ x2
+4 / 7x 2
−4 / 7x 2
x0
x1
+3x3
+1 / 7x3
−1 / 7x 3
+ x4
=
39
=
13 / 7
=
−6 / 7
При этом получаем базисную систему для следующей вершины
симплекса
+11 / 4x3
x0
x1
x2
+1 / 4x 3
+7 / 4x4
+ x4
−7 / 4x4
=
37.5
=
1
=
1.5
Значение переменной x2 – не целое. Из базисного уравнения с
нецелочисленной x2 выводим следующее отсекающее уравнение с
целочисленной x5 и отсекающее нецелочисленное значение x2 = 1 ½
– 1/4x3 – 1/4x4 + x5 = – 0.5
С помощью этой опорной строки исключаем переменную Х3 из
числа нулевых переменных
x0
x1
x2
x3
−x4
+ x4
−2x4
+ x4
+11x5
+ x5
−4x5
=
32
=
1
=
1
=
2
На рис. 5.1 представлена постановка этой же задачи в Excel
74
Рис. 5.1. Постановка целочисленной задачи в Excel
На рис. 5.2 перемещаемся по Х1 в следующую вершину симплекса, в которой коэффициент при Х1 равен нулю и добавляем
целочисленное уравнение, отсекающее нецелочисленное. решение
Рис. 5.2. Отсечение первого нецелочисленного решения
На рис. 5.3 перемещаемся по Х2 в следующую вершину симплекса, в которой коэффициент при Х2 равен нулю и добавляем
целочисленное уравнение, отсекающее нецелочисленное. решение
Рис. 5.3. Отсечение второго нецелочисленного решения
На рис. 5.4 перемещаемся по Х3 в следующую вершину симплекса, в которой коэффициент при Х3 равен нулю и все переменные стали целочисленными.
Рис. 5.4. Целочисленное решение задачи
Варианты заданий по целочисленному программированию
01
21x1 + 11x2 → max
7x1 + 3x2 + x3 = 15, x1, x2, x3 ≥ 0
75
02
21x1 + 12x2 → max
7x1 + 4x2 + x3 = 16, x1, x2, x3 ≥ 0
03
21x1 + 11x2 → max
7x1 + 3x2 + x3 = 17, x1, x2, x3 ≥ 0
04
21x1 + 11x2 → max
7x1 + 3x2 + x3 = 18, x1, x2, x3 ≥ 0
05
22x1 + 11x2 → max
7x1 + 4x2 + x3 = 19, x1, x2, x3 ≥ 0
06
21x1 + 12x2 → max
7x1 + 4x2 + x3 = 20, x1, x2, x3 ≥ 0
07
21x1 + 11x2 → max
7x1 + 4x2 + x3 = 22, x1, x2, x3 ≥ 0
08
21x1 + 12x2 → max
7x1 + 5x2 + x3 = 23, x1, x2, x3 ≥ 0
09
21x1 + 11x2 → max
7x1 + 4x2 + x3 = 24, x1, x2, x3 ≥ 0
10
21x1 + 12x2 → max
8x1 + 4x2 + x3 = 25, x1, x2, x3 ≥ 0
11
21x1 + 11x2 → max
7x1 + 4x2 + x3 = 26, x1, x2, x3 ≥ 0
12
21x1 + 11x2 → max
7x1 + 4x2 + x3 = 27, x1, x2, x3 ≥ 0
13
21x1 + 13x2 → max
7x1 + 4x2 + x3 = 15, x1, x2, x3 ≥ 0
76
14
23x1 + 11x2 → max
7x1 + 4x2 + x3 = 29, x1, x2, x3 ≥ 0
15
21x1 + 11x2 → max
7x1 + 5x2 + x3 = 30, x1, x2, x3 ≥ 0
16
21x1 + 13x2 → max
7x1 + 4x2 + x3 = 13, x1, x2, x3 ≥ 0
17
21x1 + 12x2 → max
7x1 + 4x2 + x3 = 14, x1, x2, x3 ≥ 0
18
23x1 + 11x2 → max
7x1 + 4x2 + x3 = 15, x1, x2, x3 ≥ 0
19
21x1 + 12x2 → max
7x1 + 4x2 + x3 = 16, x1, x2, x3 ≥ 0
20
21x1 + 15x2 → max
7x1 + 4x2 + x3 = 17, x1, x2, x3 ≥ 0
21
21x1 + 13x2 → max
7x1 + 4x2 + x3 = 18, x1, x2, x3 ≥ 0
22
21x1 + 12x2 → max
6x1 + 4x2 + x3 = 19, x1, x2, x3 ≥ 0
23
21x1 + 10x2 → max
7x1 + 4x2 + x3 = 20, x1, x2, x3 ≥ 0
24
21x1 + 12x2 → max
7x1 + 3x2 + x3 = 22, x1, x2, x3 ≥ 0
25
21x1 + 14x2 → max
7x1 + 4x2 + 2x3 = 23, x1, x2, x3 ≥ 0
77
26
21x1 + 12x2 → max
7x1 + 4x2 + 3x3 = 24, x1, x2, x3 ≥ 0
27
22x1 + 11x2 → max
7x1 + 5x2 + x3 = 25, x1, x2, x3 ≥ 0
28
21x1 + 12x2 → max
9x1 + 4x2 + x3 = 26, x1, x2, x3 ≥ 0
29
21x1 + 11x2 → max
7x1 + 4x2 + x3 = 27, x1, x2, x3 ≥ 0
30
20x1 + 12x2 → max
7x1 + 4x2 + x3 = 28, x1, x2, x3 ≥ 0
31
21x1 + 11x2 → max
7x1 + 4x2 + x3 = 29, x1, x2, x3 ≥ 0
32
21x1 + 10x2 → max
7x1 + 5x2 + x3 = 30, x1, x2, x3 ≥ 0
33
19x1 + 11x2 → max
7x1 + 4x2 + x3 = 31, x1, x2, x3 ≥ 0
34
20x1 + 12x2 → max
7x1 + 4x2 + x3 = 13, x1, x2, x3 ≥ 0
35
21x1 + 13x2 → max
7x1 + 4x2 + x3 = 14, x1, x2, x3 ≥ 0
36
22x1 + 14x2 → max
7x1 + 4x2 + x3 = 15, x1, x2, x3 ≥ 0
37
23x1 + 15x2 → max
7x1 + 4x2 + x3 = 16, x1, x2, x3 ≥ 0
78
38
24x1 + 16x2 → max
7x1 + 4x2 + x3 = 17, x1, x2, x3 ≥ 0
39
25x1 + 17x2 → max
7x1 + 4x2 + x3 = 18, x1, x2, x3 ≥ 0
40
26x1 + 18x2 → max
7x1 + 4x2 + x3 = 19, x1, x2, x3 ≥ 0
41
27x1 + 10x2 → max
7x1 + 4x2 + 2x3 = 20, x1, x2, x3 ≥ 0
42
28x1 + 11x2 → max
7x1 + 4x2 + x3 = 21, x1, x2, x3 ≥ 0
43
29x1 + 12x2 → max
7x1 + 4x2 + x3 = 22, x1, x2, x3 ≥ 0
44
21x1 + 13x2 → max
7x1 + 4x2 + x3 = 23, x1, x2, x3 ≥ 0
45
26x1 + 14x2 → max
7x1 + 4x2 + x3 = 24, x1, x2, x3 ≥ 0
46
21x1 + 15x2 → max
7x1 + 4x2 + x3 = 25, x1, x2, x3 ≥ 0
47
21x1 + 16x2 → max
7x1 + 4x2 + x3 = 26, x1, x2, x3 ≥ 0
48
21x1 + 17x2 → max
7x1 + 4x2 + x3 = 27, x1, x2, x3 ≥ 0
49
21x1 + 18x2 → max
7x1 + 4x2 + x3 = 28, x1, x2, x3 ≥ 0
79
50
21x1 + 10x2 → max
7x1 + 4x2 + x3 = 29, x1, x2, x3 ≥ 0
51
21x1 + 19x2 → max
7x1 + 4x2 + x3 = 30, x1, x2, x3 ≥ 0
52
21x1 + 9x2 → max
7x1 + 4x2 + x3 = 31, x1, x2, x3 ≥ 0
80
РАЗДЕЛ 6. ОПТИМИЗАЦИИ ЗАДАЧ МЕТОДОМ ВЕТВЕЙ
И ГРАНИЦ
Метод ветвей и границ – метод оптимизации переменных целевой функций универсального типа – от аналитического до графоаналитического и алгоритмического. Ниже приведено решение
оптимизационной задачи минимизации времени окончания трёх
процессов на трёх станках методом ветвей и границ. На рис. 6.1
приведен процесс одновременной обработки деталей α, β и γ на
трёх станках A,B и C. Порядок прохождения станков для каждой
детали – разный и указан на графе дугами (линиями со стрелками). Условие невозможности одновременной обработки разных
деталей на одном и том же станке указано на графе рёбрами (линиями без стрелок). Операция обработки детали на станке указана
кружком, а длительность обработки указана числом в условных
единицах (у.е.) над каждым кружком. Конец выполнения всех
трёх процессов указан кружком с буквой E. Числами над последними дугами указана длительность каждого процесса. Числом
справа от E указана максимальная длительность из трёх процессов при условии, что станков каждого типа столько, что все процессы могут выполняться одновременно во времени. Это число,
равное 15, является нижней границей минимального времени выполнения всех процессов. Само минимальное время будет больше
или равно 15 из-за наличия времени ожидания обработки деталей
на станках в реальном случае, когда используется только по одному станку каждого типа. Нижняя граница меняется при изменении очерёдности обработки конфликтующих деталей на станке
одного типа. Это позволяет найти оптимальную очерёдность обработки всех деталей на станках всех типов, выбирая на каждом этапе решения задачи ту очерёдность, которая соответствует минимальному значению нижней границы времени выполнения всех
процессов. С каждым последующим этапом выбираемое значение
нижней границы, во-первых, не уменьшается, а во-вторых. приближается к минимальному значению времени окончания всех
процессов. На последнем этапе нижняя граница становится равной минимальному времени выполнения всех процессов, а соответствующая ей очерёдность обработки всех деталей на всех станках – оптимальной.
Рассмотрим пример решения такой задачи, изображённой на
рис. 6.1, методом ветвей и границ.
81
α
β
γ
4
6
5
4
6
5
A
5
B
3
A
6
A
5
B
2 4 3
A
6
B
6
A
4
C
3
B
6
A
4
A
B
A
15
1
14
E 15
13
3 5
A
Рис. 6.1. Исходная постановка
задачи (Mvg_15)
15
C
6
73
B
14
A
E 17
17
Рис. 6.2. Замена первого ребра
дугою вниз (Mvg1d_17)
На рис. 6.2 все рёбра пронумерованы и должны быть постепенно
заменены дугами, направленными вверх или вниз так, чтобы получить минимальное время выполнения всех процессов. На первом
этапе заменяется дугой вниз или вверх ребро с номером 1.
При замене этого ребра дугою вниз нижний процесс ждёт момента
окончания обработки детали α на станке A. Вместе с ожиданием время выполнения нижнего процесса увеличится на 4 у.е. и станет равным 17 у.е. Для этого случая нижняя граница станет равной 17 у.е.
Если первое ребро заменить дугою вверх (см. рис. 6.3), то ожидать момента окончания обработки детали γ на станке A будет верхний процесс, в результате чего длительность его увеличится на
6 у.е. и станет равной 21 у.е. Эта величина и станет нижней границей времени окончания всех процессов. При выборе этого варианта минимальное время ни в коем случае не будет меньше 21 у.е., в
то время как в предыдущем варианте результат может оказаться
меньше 21 у.е. Поэтому при выполнении следующих этапов первое
ребро заменяется дугою вниз
На следующем этапе заменяется дугою вниз или вверх второе ребро при условии, что первое ребро заменено дугою вниз. На рис. 6.4
второе ребро заменено дугою вниз. Длительность процесса обработ-
4
1
A
5
B
6
A
2
4
6
5
B
3
A
6
A
3
5 4
B
6
C
73
A
21
1
14
E 21
13
Рис. 6.3. Замена первого ребра
дугою вверх (Mvg1v_21)
82
4
6
5
A
5
B
2 4 3
A
6
B
6
A
4
A
3 5
B
6
C
73
A
15
14
E 17
17
Рис. 6.4. Замена второго ребра
дугою вниз (Mvg1d2d_17)
1
4
6
5
A
5
B
2 4 3
A
6
B
6
A
3 5
A
4
6
B
23
C
73
14
E 25
1
25
A
4
6
5
A
5
B
2 4 3
A
6
B
6
A
4
A
Рис. 6.5. Замена второго ребра
дугою вверх (Mvg1d2v_25)
3 5
6
B
C
73
15
15
E 21
21
A
Рис. 6.6. Замена третьего ребра
дугою вниз (Mvg1d2d3d_21)
ки детали β не увеличится, так как станок A освободится на 1 у.е.
раньше, чем закончится обработка детали β на станке B. Поэтому
значение нижней границы в этом случае останется равным 17.
При замене второго ребра дугою вверх (см. рис. 6.5) обработка
детали α на станке A может начаться через (5+3) у.е., а обработка детали γ на станке A может начаться через (5+3+4) у.е. Поэтому
верхний процесс закончится через 23 у.е., а нижний процесс – через 25 у.е. Нижняя граница в этом случае будет равна 25 у.е.
На третьем этапе заменяем третье ребро дугою вниз или вверх
при условии, что первое и второе ребра заменены дугою вниз.
На рис. 6.6 третье ребро заменено дугою вниз, а на рис. 6.7 – дугою вверх. В первом случае обработка детали γ на станке A ждёт
(5+3) у.е. и минимальная граница равна 21 у.е. Во втором случае
обработка детали β на станке A ждёт (4+6) у.е. и процесс обработки
β заканчивается через 19 у.е., обеспечивая минимальную границу
выполнения всех процессов в этом случае равной 19 у.е.
На четвёртом этапе заменам дугами вниз или вверх подвергается четвёртое ребро.
На рис. 6.8 четвёртое ребро заменено дугою вниз, а на рис. 6.9 –
дугою вверх. В первом случае обработка детали β на станке A будет
1
4
6
5
A
5
B
2 4 3
A
6
B
6
A
4
A
3 5
B
C
6
73
A
15
1
19
E 19
17
Рис. 6.7. Замена третьего ребра
дугою вверх (Mvg1d2d3v_19)
4
6
5
A
5
B
2 4 3
A
6
B
6
A
4
A
3 5
B
6
C
73
A
15
24
E 24
17
Рис. 6.8. Замена четвёртого ребра
дугою вниз (Mvg1d2d3v4d_24)
83
1
4
6
5
A
5
B
2 4 3
A
6
B
6
A
4
A
3 5
B
6
C
73
A
16
1
19
E 19
17
4
6
5
A
5
B
2 4 3
A
6
B
6
A
4
3 5
Рис. 6.9. Замена четвёртого ребра
дугою вверх (Mvg1d2d3v4v_19)
C
6
73
B
A
16
19
E 19
17
A
Рис. 6.10. Замена пятого ребра
дугою вниз (Mvg1d2d3v4v5d_19)
ждать (4+6) у.е. и весь процесс закончится через 24 у.е. с минимальной границей, тоже равной 24 у.е. Во втором случае обработка
детали α на станке B будет ждать 5 у.е. и верхний процесс закончится через 16 у.е., а обработка детали β на станке A будет ждать
(4+6) у.е., а весь процесс закончится через 19 у.е., обеспечивая минимальную границу, равную 19 у.е.
Поэтому на пятом этапе замена пятого ребра дугами вниз или
вверх выполняется при условии, что четвёртое ребро заменяется
дугою вверх, а замена первых трёх рёбер дугами остаётся прежней.
На рис. 6.10 пятое ребро заменено дугою вниз, а на рис. 6.11 – дугою вверх. Замена пятого ребра дугою вниз не увеличивает длительность нижнего процесса и нижняя граница остаётся равной
19 у.е. Замена этого ребра дугою вверх вызывает ожидание начала
среднего процесса на (4+6+4) у.е. и ожидание начала обработки детали α на станке B на (4+6+4+5) у.е., что приводит к окончанию
обоих процессов соответственно через 28 и 30 у.е. с нижней границей, равной 30 у.е.
Поэтому на шестом этапе замена шестого ребра дугами вниз или
вверх выполняется при замене пятого ребра дугою вниз с прежними заменами дугами первых четырёх рёбер (см. рис. 6.12, 6.13).
1
4
6
5
A
5
B
2 4 3
A
6
B
6
A
4
A
3 5
B
C
6
73
A
30
28
1
E 30
17
Рис. 6.11. Замена пятого ребра
дугою вверх (Mvg1d2d3v4v5v_30)
84
4
6
5
A
5
B
2 4 3
A
6
B
6
A
4
A
3 5
B
C
6
73
A
16
19
E 19
17
Рис. 6.12. Замена шестого ребра дугою вниз
(Mvg1d2d3v4v5d6d_19)
4
1
6
A
5
2 4 3
B
6
A
4
A
B
3 5
B
5
4
6
5
A
6
A
5
B
2 4 3
A
6
B
6
A
4
C
6
73
A
25
1
19
E 25
17
Рис. 6.13. Замена шестого ребра дугою вверх
(Mvg1d2d3v4v5d6v_25)
3 5
A
16
C
6
73
B
19
A
E 19
17
Рис. 6.14. Замена седьмого ребра дугою вниз
(Mvg1d2d3v4v5d6d7d_19)
4
6
5
Замена шестого ребра дугою вниз
A
B
A
16
вызывает ожидание начала об5 2 4 3
6
1
работки детали γ на станке B на
23
E 23
A
B
C
(5+6) у.е., что вызывает увеличе6
4
3
6
7
3 5
17
ние длительности нижнего проA
B
A
цесса до 18 у.е. При этом нижняя
граница остается равной 19 у.е.
Рис. 6.15. Замена седьмого ребра
Замена шестого ребра дугою
дугою вверх
вверх вызывает ожидание об(Mvg1d2d3v4v5d6d7v_23)
работки детали α на станке B на
(4+6+4) у.е., что приводит к увеличению длительности верхнего процесса и нижней границы до
25 у.е.
Поэтому на седьмом этапе замена седьмого ребра на дугу вниз
или вверх выполняется для замены шестого ребра дугою вниз при
прежних заменах дугами первых пяти ребер (см. рис. 6.14, 6.15).
Замена седьмого ребра на дугу вниз не увеличивает длительность
нижнего процесса. Поэтому нижняя граница осталась равной 19
у.е.
Замена седьмого ребра дугою вверх вызывает ожидание начала
обработки детали β на станке C, равное (4+6+4+3) у.е., что приводит к увеличению среднего процесса и нижней границы до 23 у.е.
Поскольку заменены дугами все ребра, то нижняя граница в обоих
случаях совпадает с временем окончания всех процессов. Из двух
времён выбираем меньшее 19 у.е. Это – наименьшее время обработки всех процессов, а соответствующие ему дуги представляют
оптимальную очерёдность обработки деталей α, β и γ на всех трёх
станках.
85
Варианты заданий по оптимизации очерёдности операций
методом ветвей и границ
01
α(A-6,B-3,A-5), β(B-5,A-5,C-4), γ(A-5,B-4,C-5)
02
α(A-6,B-4,A-5), β(B-5,A-6,C-4), γ(A-4,B-5,C-6)
03
α(A-6,B-4,A-5), β(B-5,A-7,C-4), γ(A-4,B-6,C-5)
04
α(A-6,B-7,A-3), β(B-5,A-7,C-4), γ(A-7,B-5,C-3)
05
α(A-6,B-3,A-7), β(B-5,A-7,C-4), γ(A-7,B-5,C-5)
06
α(A-8,B-3,A-7), β(B-5,A-7,C-4), γ(A-7,B-4,C-5)
07
α(A-8,B-5,A-7), β(B-5,A-7,C-6), γ(A-7,B-6,C-5)
08
α(A-8,B-3,A-7), β(B-5,A-7,C-6), γ(A-7,B-5,C-7)
09
α(A-8,B-4,A-7), β(B-5,A-7,C-6), γ(A-7,B-5,C-7)
10
α(A-8,B-4,A-6), β(B-5,A-7,C-6), γ(A-9,B-5,C-7)
11
α(A-8,B-4,A-5), β(B-6,A-7,C-6), γ(A-9,B-5,C-7)
12
α(A-8,B-4,A-7), β(B-6,A-7,C-8), γ(A-7,B-5,C-9)
13
α(A-8,B-6,A-7), β(B-6,A-7,C-8), γ(A-9,B-5,C-7)
14
α(A-8,B-6,A-7), β(B-7,A-7,C-8), γ(A-9,B-5,C-7)
15
α(A-8,B-6,A-8), β(B-8,A-7,C-5), γ(A-9,B-5,C-7)
16
α(A-7,B-6,A-8), β(B-8,A-7,C-8), γ(A-9,B-7,C-7)
17
α(A-6,B-6,A-9), β(B-8,A-7,C-8), γ(A-9,B-7,C-7)
86
18
α(A-8,B-6,A-9), β(B-8,A-7,C-8), γ(A-9,B-7,C-9)
19
α(A-10,B-6,A-9), β(B-86,A-7,C-7), γ(A-9,B-7,C-9)
20
α(A-7,B-6,A-9), β(B-8,A-9,C-6), γ(A-9,B-7,C-7)
21
α(A-7,B-6,A-9), β(B-8,A-9,C-6), γ(A-9,B-7,C-8)
22
α(A-10,B-6,A-9), β(B-8,A-9,C-10), γ(A-11,B-7,C-9)
23
α(A-10,B-8,A-9), β(B-8,A-9,C-10), γ(A-11,B-7,C-9)
24
α(A-10,B-8,A-9), β(B-9,A-9,C-10), γ(A-11,B-7,C-9)
25
α(A-11,B-6,A-9), β(B-9,A-11,C-6), γ(A-8,B-9,C-11)
26
α(A-9,B-6,A-9), β(B-9,A-6,C-6), γ(A-8,B-9,C-9)
28
α(A-9,B-6,A-7), β(B-4,A-7,C-5), γ(A-7,B-9,C-6)
29
α(A-9,B-6,A-7), β(B-6,A-7,C-5), γ(A-8,B-9,C-6)
30
α(A-9,B-6,A-8), β(B-8,A-7,C-5), γ(A-8,B-9,C-6)
31
α(A-9,B-6,A-7), β(B-8,A-7,C-8), γ(A-8,B-9,C-5)
32
α(A-9,B-6,A-5), β(B-8,A-7,C-8), γ(A-8,B-9,C-6)
33
α(A-9,B-8,A-5), β(B-8,A-7,C-7), γ(A-8,B-9,C-6)
34
α(A-9,B-8,A-5), β(B-8,A-9,C-7), γ(A-7,B-9,C-6)
35
α(A-9,B-8,A-7), β(B-8,A-9,C-8), γ(A-7,B-9,C-6)
36
α(A-9,B-7,A-8), β(B-8,A-9,C-7), γ(A-7,B-9,C-6)
87
37
α(A-9,B-7,A-7), β(B-8,A-9,C-8), γ(A-7,B-9,C-6)
38
α(A-9,B-8,A-7), β(B-8,A-9,C-9), γ(A-8,B-9,C-6)
39
α(A-9,B-8,A-7), β(B-8,A-7,C-9), γ(A-5,B-9,C-6)
40
α(A-9,B-8,A-5), β(B-8,A-7,C-9), γ(A-7,B-9,C-6)
41
α(A-9,B-8,A-5), β(B-9,A-7,C-6), γ(A-7,B-9,C-9)
42
α(A-9,B-8,A-7), β(B-9,A-7,C-6), γ(A-7,B-9,C-5)
43
α(A-5,B-8,A-7), β(B-9,A-7,C-6), γ(A-7,B-9,C-9)
44
α(A-5,B-8,A-7), β(B-9,A-7,C-5), γ(A-7,B-5,C-9)
45
α(A-5,B-8,A-4), β(B-9,A-7,C-5), γ(A-4,B-5,C-9)
46
α(A-5,B-8,A-6), β(B-9,A-7,C-6), γ(A-6,B-5,C-9)
47
α(A-7,B-8,A-7), β(B-7,A-7,C-6), γ(A-6,B-5,C-9)
48
α(A-8,B-8,A-7), β(B-7,A-8,C-6), γ(A-6,B-5,C-8)
49
α(A-9,B-8,A-7), β(B-7,A-9,C-6), γ(A-6,B-5,C-9)
50
α(A-9,B-8,A-5), β(B-7,A-5,C-5), γ(A-6,B-5,C-9)
51
α(A-9,B-8,A-7), β(B-7,A-5,C-7), γ(A-6,B-7,C-9)
52
α(A-4,B-8,A-7), β(B-7,A-5,C-7), γ(A-6,B-7,C-4)
88
РАЗДЕЛ 7. ОПТИМИЗАЦИЯ ЛИНЕЙНЫХ ЗАДАЧ С БИНАРНЫМИ ПЕРЕМЕННЫМИ
Задача решается методом ветвей и границ с использованием частичных решений в качестве ветвей и значений целевой функции в
качестве нижней границы. Решение называется частичным, если
известны значения не всех переменных. Остальные переменные называются свободными. Свободные переменные, которым присвоены
конкретные значения, называют дополнением частичного решения.
Дополнение допустимо, если ограничительные неравенства не нарушаются, а новое значение целевой функции превышает текущее.
Задача оптимизации ставится так: максимизировать (минимизировать) целевую функцию
∑ сj*xj, j = 1,…,n
(7.1)
при ограничениях ∑ aij*xj ≤ bj, i = 1, …, m, где xi = {0,1}, j = 1,…, n
Алгоритм решения в задаче линейного программирования с бинарными переменными состоит из четырёх этапов:
1. Если список частичных решений пуст, задача решена. Иначе
выбрать частичное решение, исключить его из списка и перейти к
шагу 2.
2. Если есть свободная переменная, увеличивающая оценку целевой функции при любом допустимом дополнении, включить её в
частичное решение.
Если нет допустимого дополнения со значением целевой функции, превосходящей текущую оценку целевой функции, вернуться
к шагу 1.
3. Если частичное решение – полное, зафиксировать его с заменой текущей оценки целевой функции новой, соответствующей зафиксированному решению и вернуться к шагу 1. Иначе перейти к
шагу 4.
4. Выбрать свободную переменную xk и внести в список частичных решений два решения со значениями соответственно xk = 0 и
xk = 1. Запомнить текущую оценку целевой функции и вернуться к
шагу 1.
Для текущего частичного решения линейные ограничения надо
представить в следующем виде:
∑aij*xj ≤ bj – ∑aij*xj , i = 1, …, m
своб.перем. част.перем.
89
Для целевой функции (i = 0) a0j = –cj и b0 = –x0t – 1.
Если для заданного частичного решения
∑ min(aij,,0) > bj – ∑aij*xj для любого i = 0,1, …, m (7.2)
своб.перем.
част.перем.
то допустимого дополнения, которому соответствует значение целевой функции, превосходящее нижнюю оценку x0t, не существует.
Если для заданного частичного решения и свободной переменной xk
∑min(aij,,0) + aik  > bj – ∑ aij*xj для любого i = 0,1, …, m (7.3)
своб.перем.
част.перем.
то для aik > 0 переменная xk = 0, а для aik < 0 переменная xk = 1.
Пример решения
Максимизировать
3x1 + 6x2 + 3x3 + 6x4 + 13x5
при ограничениях
– 3x1 – 6x2 + 6x3 + 12x4 + 7x5 ≤ 8, i = 1
6x1 + 12x2 – 3x3 – 6x4 + 7x5 ≤ 8, i = 2
(7.4)
(7.5)
(7.6)
xi = {0,1}, j = 1,…, 5
Примем начальное значение нижней оценки целевой функции
x01 = 0, что соответствует допустимому решению, в котором все переменные равны нулю. Введём в список частичных решений (ЧР)
два решения: ЧР1 (x5 = 1) и ЧР2 (x5 = 0). Выбор объясняется тем,
что при x5 = 1 приращение оценки целевой функции максимально.
На шаге 1 исключаем ЧР1 из списка и отыскиваем для него допустимое дополнение со значением целевой функции, превосходящим оценку x01 = 0, то есть удовлетворяющее условию
–3x1 – 6x2 – 3x3 – 6x4 – 13x5 ≤ –1, i = 0
(7.7)
и двум ограничительным неравенствам (7.5 – 7.6).
На шаге 2 найдём допустимые свободные переменные, применив условие (7.3).
Для i = 1 и k = 4 условие (7.3) примет вид:
–3 – 6 + 12 > 8 – 7x5 = 8 – 7 = 1
(7.8)
90
Для i = 2 и k = 2 условие (7.3) примет тот же вид:
–3 – 6 + 12 > 8 – 7x5 = 8 – 7 = 1
(7.9)
Из (7.8) следует, что неравенство (7.5) нарушается при x4 = 1. Из
(7.9) следует, что неравенство (7.6) нарушается при x2 = 1. Значит
для ЧР1 во всех допустимых дополнениях x2 и x4 должны быть равны нулю. Из ЧР1 следует ЧР11: (x2, x4, x5) = (0, 0, 1). Для ЧР11 снова применим условие (7.3).
Для i = 1 и k = 3 условие (7.3) примет вид:
–3 + 6 > 8 – 7 = 1. (7.10)
Для i = 2 и k = 1 условие (7.3) примет тот же вид:
6 > 8 – 7 = 1. (7.11)
Следовательно, повторное применение условия (7.3) позволяет
получить допустимое полное решение ПР1: (x1,x2,x3, x4, x5) = (0, 0,
0, 0, 1) с текущей оценкой максимума целевой функции x01 =13.
Полагаем x02 = x01 =13 и возвращаемся к шагу 1. Исключаем из
списка ЧР2, где x5 = 0. Применение условия (7.2) для i = 0, 1, 2 не
исключает допустимого дополнения со значением целевой функции, превосходящим x02 = 13. Переходим к шагу 3 и 4, так как
ЧР2 – неполное. Выбираем переменную x1 и расчленяем ЧР2 на
ЧР21 и ЧР22 со значениями (x1,x5) = (1, 0) и (x1,x5) = (0, 0).
На шаге 1 исключаем из списка ЧР21 и полагаем x03 = 13. Проверка условия (7.3) для i = 0, 1 не определяет однозначно ни одну
свободную переменную. Для i = 2 проверка (7.3) даёт x2 = 0 для любого допустимого дополнения: 12 x2 – 3 – 6 > 8 – 6 = 2
(7.12)
Расширяя ЧР21 до ЧР211: (x5,x1,x2) = (0, 1,1) и повторно применяя (7.3) для i = 0 можно убедиться, что допустимого дополнения
не существует:
–3(x3 = 1) – 6(x4 = 1) ≤ –13 + 3 = –10.
(7.13)
Возвращаемся к шагу 1, исключая из списка ЧР22 (x1, x5) = (0,
0) и приняв x04 = 13.
Проверка (7.3) для i = 0 показывает, что для любого допустимого
дополнения
x3 = 1.
–6(x2 = 1) – 3(x3 = 1) – 6(x4 = 1) ≤ –13 (7.14)
Применяя условие (7.3) для i = 1, 2, получаем, что x4 = 0 и x2 = 1.
Для i = 1 имеем
–6(x2 = 1) + 12(x4 = 0) ≤ 8 – 6((x3 = 1)) = 2. (7.15)
91
Для i = 2 имеем
+ 12(x2 = 0) – 6(x4 = 1) ≤ 8 + 3(x3 = 1) = 11. (7.16)
При проверке условия (7.2) для i = 0 получаем, что не существует допустимого дополнения со значением целевой функции, превосходящим
x04 = 13.
3(x1 = 1) + 6(x2 = 0) + 3(x3 = 1) + 6(x4 = 0) + 13(x5 = 0) = 6.
Возвращаясь к шагу 1 прекращаем вычисления, так как все
частичные решения в списке исчерпаны. Максимальное значение
целевой функции равно 13, а оптимальные значения переменных
равны (0, 0, 0, 0, 1).
Варианты заданий для линейных задач
с бинарными переменными
01
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 + 6x3 + 12x4 + 7x5 ≤ 8, i = 1
6x1 + 12x2 – 3x3 – 6x4 + 7x5 ≤ 8, i = 2
xi = {0,1}, j = 1,…, 5
02
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 + 6x3 + 12x4 + 7x5 ≤ 6, i = 1
6x1 + 12x2 – 3x3 – 6x4 + 7x5 ≤ 6, i = 2
xi = {0,1}, j = 1,…, 5
03
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 + 6x3 + 12x4 + 7x5 ≤ 8, i = 1
6x1 + 12x2 – 3x3 – 6x4 + 7x5 ≤ 9, i = 2
xi = {0,1}, j = 1,…, 5
04
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 + 6x3 + 12x4 + 7x5 ≤ 9, i = 1
6x1 + 12x2 – 3x3 – 6x4 + 7x5 ≤ 9, i = 2
xi = {0,1}, j = 1,…, 5
92
05
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 + 6x3 + 12x4 + 7x5 ≤ 7, i = 1
6x1 + 12x2 – 3x3 – 6x4 + 7x5 ≤ 7, i = 2
xi = {0,1}, j = 1,…, 5
06
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 + 6x3 + 12x4 + 7x5 ≤ 7, i = 1
3x1 + 6x2 + 3x3 + 6x4 + 13x5 ≤ 9, i = 2
xi = {0,1}, j = 1,…, 5
07
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 + 6x3 + 12x4 + 7x5 ≤ 9, i = 1
3x1 + 6x2 + 3x3 + 6x4 + 13x5 ≤ 7, i = 2
xi = {0,1}, j = 1,…, 5
08
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 + 6x3 + 12x4 + 7x5 ≤ 3, i = 1
3x1 + 6x2 – 3x3 – 6x4 + 13x5 ≤ 3, i = 2
xi = {0,1}, j = 1,…, 5
09
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 + 6x3 + 12x4 + 7x5 ≤ 13, i = 1
3x1 + 6x2 – 3x3 – 6x4 + 13x5 ≤ 13, i = 2
xi = {0,1}, j = 1,…, 5
10
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 + 6x3 + 12x4 + 7x5 ≤ 10, i = 1
3x1 + 6x2 – 3x3 – 6x4 + 13x5 ≤ 13, i = 2
xi = {0,1}, j = 1,…, 5
93
11
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 + 6x3 + 12x4 + 7x5 ≤ 7, i = 1
3x1 + 6x2 + 13x3 + 6x4 + 5x5 ≤ 13, i = 2
xi = {0,1}, j = 1,…, 5
12
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 + 6x3 + 12x4 + 7x5 ≤ 9, i = 1
3x1 + 6x2 + 3x3 + 6x4 + 13x5 ≤ 9, i = 2
xi = {0,1}, j = 1,…, 5
13
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 + 6x3 + 12x4 + 7x5 ≤ 6, i = 1
3x1 + 6x2 + 3x3 + 6x4 + 13x5 ≤ 12, i = 2
xi = {0,1}, j = 1,…, 5
14
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 + 6x3 + 12x4 + 7x5 ≤ 13, i = 1
3x1 + 10x2 + 3x3 – 6x4 + 10x5 ≤ 9, i = 2
xi = {0,1}, j = 1,…, 5
15
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 + 6x3 + 12x4 + 7x5 ≤ 8, i = 1
3x1 + 10x2 + 3x3 – 6x4 + 10x5 ≤ 12, i = 2
xi = {0,1}, j = 1,…, 5
16
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 + 6x3 + 12x4 + 7x5 ≤ 9, i = 1
3x1 + 10x2 + 3x3 – 6x4 + 10x5 ≤ 9, i = 2
xi = {0,1}, j = 1,…, 5
94
17
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 + 6x3 + 12x4 + 7x5 ≤ 10, i = 1
3x1 + 6x2 + 3x3 + 6x4 – 13x5 ≤ 12, i = 2
xi = {0,1}, j = 1,…, 5
18
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 + 6x3 + 12x4 + 7x5 ≤ 10, i = 1
3x1 + 6x2 + 3x3 + 6x4 – 13x5 ≤ 5, i = 2
xi = {0,1}, j = 1,…, 5
19
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при + 3x1 – 6x2 – 6x3 + 12x4 + 7x5 ≤ 12, i = 1
3x1 + 6x2 + 3x3 + 6x4 + 13x5 ≤ 6, i = 2
xi = {0,1}, j = 1,…, 5
20
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при 3x1 – 6x2 – 6x3 + 12x4 + 7x5 ≤ 6, i = 1
3x1 + 6x2 + 3x3 + 6x4 + 13x5 ≤ 9, i = 2
xi = {0,1}, j = 1,…, 5
21
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при –3x1 – 6x2 – 6x3 + 12x4 + 7x5 ≤ 8, i = 1
–3x1 + 6x2 + 3x3 – 6x4 + 13x5 ≤ 13, i = 2
xi = {0,1}, j = 1,…, 5
22
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при –3x1 – 6x2 – 6x3 + 12x4 + 7x5 ≤ 8, i = 1
–3x1 + 6x2 + 3x3 – 6x4 + 13x5 ≤ 12, i = 2
xi = {0,1}, j = 1,…, 5
95
23
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при –3x1 – 6x2 – 6x3 + 12x4 + 7x5 ≤ 8, i = 1
–3x1 + 6x2 + 3x3 – 6x4 + 13x5 ≤ 11, i = 2
xi = {0,1}, j = 1,…, 5
24
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при –3x1 – 6x2 – 6x3 + 12x4 + 7x5 ≤ 8, i = 1
–3x1 + 6x2 + 3x3 – 6x4 + 13x5 ≤ 10, i = 2
xi = {0,1}, j = 1,…, 5
25
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при –3x1 – 6x2 – 6x3 + 12x4 + 7x5 ≤ 8, i = 1
–3x1 + 6x2 + 3x3 – 6x4 + 13x5 ≤ 9, i = 2
xi = {0,1}, j = 1,…, 5
26
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при –3x1 – 6x2 – 6x3 + 12x4 + 7x5 ≤ 8, i = 1
–3x1 + 6x2 + 3x3 – 6x4 + 13x5 ≤ 8, i = 2
xi = {0,1}, j = 1,…, 5
27
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при –3x1 – 6x2 – 6x3 + 12x4 + 7x5 ≤ 8, i = 1
–3x1 + 6x2 + 3x3 – 6x4 + 13x5 ≤ 7, i = 2
xi = {0,1}, j = 1,…, 5
28
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при –3x1 – 6x2 – 6x3 + 12x4 + 7x5 ≤ 8, i = 1
–3x1 + 6x2 + 3x3 – 6x4 + 13x5 ≤ 6, i = 2
xi = {0,1}, j = 1,…, 5
96
29
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при –3x1 – 6x2 – 6x3 + 12x4 + 7x5 ≤ 6, i = 1
–3x1 + 6x2 + 3x3 – 6x4 + 13x5 ≤ 6, i = 2
xi = {0,1}, j = 1,…, 5
30
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при –3x1 – 6x2 – 6x3 + 12x4 + 7x5 ≤ 7, i = 1
–3x1 + 6x2 + 3x3 – 6x4 + 13x5 ≤ 6, i = 2
xi = {0,1}, j = 1,…, 5
31
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при –3x1 – 6x2 – 6x3 + 12x4 + 7x5 ≤ 8, i = 1
–3x1 + 6x2 + 3x3 – 6x4 + 13x5 ≤ 6, i = 2
xi = {0,1}, j = 1,…, 5
32
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при –3x1 – 6x2 – 6x3 + 12x4 + 7x5 ≤ 9, i = 1
–3x1 + 6x2 + 3x3 – 6x4 + 13x5 ≤ 6, i = 2
xi = {0,1}, j = 1,…, 5
33
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 – 6x3 + 12x4 + 7x5 ≤ 10, i = 1
–3x1 + 6x2 + 3x3 – 6x4 + 13x5 ≤ 6, i = 2
xi = {0,1}, j = 1,…, 5
34
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 – 6x3 + 12x4 + 7x5 ≤ 11, i = 1
–3x1 + 6x2 + 3x3 – 6x4 + 13x5 ≤ 6, i = 2
xi = {0,1}, j = 1,…, 5
97
35
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 – 6x3 + 12x4 + 7x5 ≤ 12, i = 1
–3x1 + 6x2 + 3x3 – 6x4 + 13x5 ≤ 6, i = 2
xi = {0,1}, j = 1,…, 5
36
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 – 6x3 + 12x4 + 7x5 ≤ 8, i = 1
–3x1 + 6x2 + 3x3 – 6x4 + 13x5 ≤ 7, i = 2
xi = {0,1}, j = 1,…, 5
37
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 – 6x3 + 12x4 + 7x5 ≤ 9, i = 1
–3x1 + 6x2 + 3x3 + –x4 + 13x5 ≤ 7, i = 2
xi = {0,1}, j = 1,…, 5
38
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 – 6x3 + 12x4 + 7x5 ≤ 10, i = 1
–3x1 + 6x2 + 3x3 – 6x4 + 13x5 ≤ 7, i = 2
xi = {0,1}, j = 1,…, 5
39
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 –- 6x3 + 12x4 + 7x5 ≤ 11, i = 1
–3x1 + 6x2 + 3x3 – 6x4 + 13x5 ≤ 7, i = 2
xi = {0,1}, j = 1,…, 5
40
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 – 6x3 + 12x4 + 7x5 ≤ 12, i = 1
–3x1 + 6x2 + 3x3 – 6x4 + 13x5 ≤ 7, i = 2
xi = {0,1}, j = 1,…, 5
98
41
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 – 6x3 + 12x4 + 7x5 ≤ 13, i = 1
–3x1 + 6x2 + 3x3 – 6x4 + 13x5 ≤ 7, i = 2
xi = {0,1}, j = 1,…, 5
42
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 – 6x3 + 12x4 + 7x5 ≤ 14, i = 1
–3x1 + 6x2 + 3x3 – 6x4 + 13x5 ≤ 7, i = 2
xi = {0,1}, j = 1,…, 5
43
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 – 6x3 + 12x4 + 7x5 ≤ 9, i = 1
–3x1 + 6x2 + 3x3 – 6x4 + 13x5 ≤ 8, i = 2
xi = {0,1}, j = 1,…, 5
44
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 – 6x3 + 12x4 + 7x5 ≤ 10, i = 1
–3x1 + 6x2 + 3x3 – 6x4 + 13x5 ≤ 8, i = 2
xi = {0,1}, j = 1,…, 5
45
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 – 6x3 + 12x4 + 7x5 ≤ 11, i = 1
–3x1 + 6x2 + 3x3 – 6x4 + 13x5 ≤ 8, i = 2
xi = {0,1}, j = 1,…, 5
46
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 – 6x3 + 12x4 + 7x5 ≤ 12, i = 1
–3x1 + 6x2 + 3x3 – 6x4 + 13x5 ≤ 8, i = 2
xi = {0,1}, j = 1,…, 5
99
47
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 – 6x3 + 12x4 + 7x5 ≤ 13, i = 1
–3x1 + 6x2 + 3x3 – 6x4 + 13x5 ≤ 8, i = 2
xi = {0,1}, j = 1,…, 5
48
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 – 6x3 + 12x4 + 7x5 ≤ 14, i = 1
–3x1 + 6x2 + 3x3 – 6x4 + 13x5 ≤ 8, i = 2
xi = {0,1}, j = 1,…, 5
49
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 – 6x3 + 12x4 + 7x5 ≤ 10, i = 1
–3x1 + 6x2 + 3x3 – 6x4 + 13x5 ≤ 9, i = 2
xi = {0,1}, j = 1,…, 5
50
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 – 6x3 + 12x4 + 7x5 ≤ 11, i = 1
–3x1 + 6x2 + 3x3 – 6x4 + 13x5 ≤ 9, i = 2
xi = {0,1}, j = 1,…, 5
51
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 – 6x3 + 12x4 + 7x5 ≤ 11, i = 1
–3x1 + 6x2 + 3x3 – 6x4 + 13x5 ≤ 10, i = 2
xi = {0,1}, j = 1,…, 5
52
Максимизировать 3x1 + 6x2 + 3x3 + 6x4 + 13x5
при – 3x1 – 6x2 – 6x3 + 12x4 + 7x5 ≤ 12, i = 1
–3x1 + 6x2 + 3x3 – 6x4 + 13x5 ≤ 10, i = 2
xi = {0,1}, j = 1,…, 5
100
РАЗДЕЛ 8. МНОГОКРИТЕРИАЛЬНАЯ ОПТИМИЗАЦИИ
СЛОЖНЫХ ОБЪЕКТОВ
На рис. 8.1 приведено непрерывное замкнутое множество допустимых вариантов сложного объекта с одинаковыми значениями
технических характеристик, различающихся cтоимостью изготовления Си и интенсивностью отказов Λ.
На рис. 8.2 приведено множество эффективных вариантов сложного объекта с минимальной cтоимостью изготовления Си min (Λ),
зависящей от значения интенсивности его отказа Λ.
На рис. 8.3 представлено множество эффективных вариантов
сложного объекта, для которых определены их стоимости эксплуатации Сэ (Λ) за весь срок их использования.
На рис. 8.4 представлена зависимость суммарных затрат (Си +
Сэ) на изготовление и эксплуатацию эффективных вариантов объекта от значения их интенсивности отказов Λ, минимальное значение этих затрат и соответствующий ему оптимальный вариант объекта с оптимальной стоимостью изготовления Сиopt и оптимальной
интенсивностью его отказа Λopt.
На рис. 8.5 представлена структурная схема объекта А0, состоящего из одной сборки А12 и компонента А3. Сборка А12 состоит из
компонентов А1 и А2.
Для каждого из компонентов А1, А2 и А3 можно определить эффективные варианты их исполнения, но невозможно определить
зависимость стоимости их эксплуатации Сэ(Λ) от интенсивности
Си
Си
A
Cи min(Λ)
B
Lamb
Рис. 8.1. Множество допустимых
вариантов сложного объекта
Λ Lamb
Рис. 8.2. Парето-множеств эффективных вариантов сложного
объекта
101
Си
(Си+Сэ)1
A
(Си+Сэ)4
Си
(Си+Сэ)3
(Си+Сэ)2
Сэ
D
B
Lamb
Lamb opt
Рис. 8.3. Стоимость эксплуатации
эффективных вариантов объекта
Cэ Си
A
(Си+Сэ)
(Си+Сэ)min
Cиопт
Си
D
Сэ
B
Lamb
Lamb opt
Рис. 8.4. Оптимальный вариант объекта
с минимальными суммарными затратами (Си+Сэ)min
отказов, поскольку каждый компонент – не автономен и по отдельности не может эксплуатироваться.
Составной объект А0 – автономен. Поэтому он может автономно
эксплуатироваться и для него можно определить зависимость стоимости эксплуатации Сэ(Λ) от интенсивности отказов. Для определения оптимального варианта объекта А0 необходимо найти его эффективные варианты, то есть получить зависимость минимальной
стоимости его изготовления Сиmin(Λ) от интенсивности его отказов.
Поскольку стоимость и интенсивность отказов нескольких компонентов складываются из стоимостей и интенсивностей отказов
102
C0
CЭ
0
V
A0
A3
A12
C3
C 3min
A2
A1
C2
V
3
C 2min
C1min
V
1
V
C1
2
Рис. 8.5. Постановка задачи оптимизации составного объекта
каждого компонента, то для определения эффективных вариантов
объектов А12 и А0 из эффективных вариантов компонентов А1, А2
и А3 можно воспользоваться аппаратом динамического программирования [11]. Сначала определяются эффективные варианты
объекта А12 по эффективным вариантам компонентов А1 и А2. Затем можно определить эффективные варианты объекта А0 по эффективным вариантам объекта А12 и компонента А3. Для эффективных вариантов объекта А0 известна зависимость минимальной
стоимости его изготовления Сиmin(Λ) от интенсивности его отказов.
Складывая эту зависимость с функцией стоимости эксплуатации
Сэ(Λ) этих же вариантов, можно определить оптимальный эффективный вариант объекта А0opt и соответствующий ему оптимальные значения стоимости изготовления Cиopt, эксплуатации Cэopt и
интенсивности отказов Λopt.
На рис. 8.6 представлены эффективные варианты сканера,
принтера и монитора
На рис. 8.7 представлено графическое построение методом динамического программирования эффективного варианта безотказной
пары из сканера и принтера.
На рис. 8.8 представлено графическое построение методом динамического программирования эффективного варианта одноотказной пары из сканера и принтера.
103
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
Цены
Найти оптимальное УВВ
и его комплектующие
Монитор
Принтер
Сканер
0
1
2
5 Отказы
4
3
Рис. 8.6. Эффективные варианты трёх компонентов
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
5
4
3
2
1
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
1
2
3
4
5
0
1
2
3
Рис. 8.7. Эффективный вариант безотказной пары сканер-принтер
104
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
4
3
2
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0
1
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
1
2
4
3
5
0
1
2
3
Рис. 8.8. Эффективный вариант одноотказной пары сканер-принтер
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
4
3
2
1
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
1
2
3
4
5
0
1
2
3
4
5
Рис. 8.9. Эффективный вариант двухотказной пары сканер-принтер
На рис. 8.9 представлено графическое построение методом динамического программирования эффективного варианта двухотказной пары из сканера и принтера.
На рис. 8.10 представлено графическое построение методом динамического программирования эффективного варианта трёхотказной пары из сканера и принтера.
105
На рис. 8.11 представлено графическое построение методом динамического программирования эффективного варианта четырёхотказной пары из сканера и принтера.
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
3
2
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0
1
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
1
2
3
4
5
0
1
2
3
4
5
Рис. 8.10. Эффективный вариант трёхотказной пары
сканер-принтер
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
3
2
1
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
1
2
3
4
5
0
1
2
3
4
5
Рис. 8.11. Эффективный вариант четырёхотказной пары
сканер-принтер
106
2
1
15 15
15
14 14
13 13
12 12
14
13
12
11
10
9
8
11
10
9
8
11
10
9
8
7
6
7
6
7
6
5
4
3
2
1
5
4
3
2
1
5
4
3
2
1
0
1
2
3
4
5
0
1
2
3
4
5
Рис. 8.12. Эффективный вариант пятиотказной пары сканер-принтер
На рис. 8.12 представлено графическое построение методом динамического программирования эффективного варианта пятиотказной пары из сканера и принтера.
Зная эффективные варианты пары сканер-принтер и эффективные варианты монитора можно аналогично определить эффективные варианты тройки сканер-принтер-монитор. Предлагается выполнить построение для тройки компонентов по представленному
выше алгоритму самостоятельно.
На рис. 8.13 представлен окончательный результат – оптимальные устройства УВВ по критерию минимальных затрат на изготовление и эксплуатацию.
Пример определения оптимальных вариантов
комплектующих ПК
На рис. 8.14 представлен состав персонального компьютера с известными ценами новых (безотказных за три года) комплектующих
для него и ценами бывших в употреблении (БУ) (семиотказных за
три года) комплектующих. Цены указаны в тысячах рублей. В последнем столбце указана стоимость ремонта нового компьютера и
компьютера, состоящего из БУ комплектующих.
107
Цены
15
14
ни
Мо
10
Пр
7
ин
те
р
6
Опт сканер
2
1
0
Скан
1
ер
2
Опт монитор
4
3
Опт принтер
5
3
Опт принтер
8
Оптимальное УВВ
р
то
9
4
Опт сканер
11
Опт монитор
13
12
Отказы
5
Рис. 8.13. Оптимальные эффективные варианты
устройств ввода-вывода (УВВ)
Рис. 8.14. Исходные данные для определения
оптимальных комплектующих ПК
108
На рис. 8.15–8.17 показан способ заполнения цен комплектующих для промежуточных значений отказа во всех строках таблицы
по закону геометрической прогрессии.
На рис. 8.18 и 8.19 показана проверка правильности заполнения
столбцов.
На рис. 8.20 и 8.21 показана вставка пустого столбца для построения эффективных вариантов разноотказных пар сканер-принтер.
На рис. 8.21 – 8.28 представлена процедура ввода формул для определения эффективных вариантов разноотказных пар сканер-принтер от безотказной до семиотказной.
На рис. 8.29 и 8.30 показана проверка правильности введённых
формул для определения эффективных разноотказных пар сканерпринтер. На рис. 8.31–8.33 представлена вставка пустого столбца
для копирования в него формул по определению эффективных пар
сканер-принтер.
На рис. 8.34–8.36 представлено копирование эффективных пар
сканер-принтер в столбец УВВ для получения эффективной тройки
её комплектующих и проверка правильности расчёта.
На рис. 8.37, 8.38 показано копирование формульных значений цен для эффективных вариантов тройки комплектующих УВВ
в численные значения в этот же столбец, но ниже. Это нужно для
получения эффективных вариантов частей компьютера на уровне
блоков.
Рис. 8.15. Заполнение строк таблицы числами по закону прогрессии
109
110
Рис. 8.16. Выбор геометрической прогрессии
111
Рис. 8.17. Результат заполнения таблицы ценами комплектующих ПК
112
Рис. 8.18. Проверки правильности заполнения цен в столбцах сканера и ремонта
113
Рис. 8.19. Проверки правильности заполнения цен в столбцах сканера и ремонта
114
Рис. 8.20. Вставка пустого столбца для построения эффективных пар сканер-принтер
115
Рис. 8.21. Ввод формулы для эффективной безотказной пары сканер-принтер
116
Рис. 8.22. Ввод формулы для эффективной одноотказной пары сканер-принтер
117
Рис. 8.23. Ввод формулы для эффективной двухотказной пары сканер-принтер
118
Рис. 8.24. Ввод формулы для эффективной трёхотказной пары сканер-принтер
119
Рис. 8.25. Ввод формулы для эффективной четырёхотказной пары сканер-принтер
120
Рис. 8.26. Ввод формулы для эффективной пятиотказной пары сканер-принтер
121
Рис. 8.27. Ввод формулы для эффективной шестиотказной пары сканер-принтер
122
Рис. 8.28. Ввод формулы для эффективной семиотказной пары сканер-принтер
123
Рис. 8.29. Настройка проверки правильности вычисления эффективных пар сканер-принтер
124
Рис. 8.30. Проверка правильности вычисления эффективных пар сканер-принтер
Рис. 8.31. Выбор столбца для вставки пустого
Рис. 8.32. Вставка пустого столбца
125
Рис. 8.33. Ввод названия УВВ для пустого столбца
Рис. 8.34. Копирование формул столбца сканер-принтер
и вставка их в столбец УВВ
126
127
Рис. 8.35. Выделение столбцов для УВВ
128
Рис. 8.36. Проверка правильности вычисления эффективных компонентов УВВ
129
Рис. 8.37. Копирование значений эффективных УВВ в отдельный столбец
Рис. 8.38. Вставка значений эффективных УВВ в отдельный столбец
На рис. 8.39 показаны эффективные варианты УВВ, материнской платы, накопителей и всего компьютера в виде формул и в
виде числовых значений.
На рис. 8.40–8.43 показано вычисление суммарных затрат на
изготовление и ремонт разноотказных компьютеров, а также определение оптимального компьютера с минимальными суммарными
затратами.
Рис. 8.39. Вставка значений эффективных комплектующих
и блоков персонального компьютера
130
Рис. 8.40. Суммарные затраты на изготовление
и эксплуатацию безотказного компьютера
Рис. 8.41. Суммарные затраты на изготовление и эксплуатации всех
вариантов компьютера
131
132
Рис. 8.42. Выделение столбцов изготовления, ремонта и суммарных затрат компьютера
133
Рис. 8.43. Определение оптимального компьютера, ремонта и минимальных затрат
134
Рис. 8.44. Определение оптимальных накопителей и остальной части компьютера
135
Рис. 8.45. Определение оптимальных вариантов материнской платы и УВВ
136
Рис. 8.46. Определение оптимальных вариантов накопителей
137
Рис. 8.47. Оптимальные варианты процессора и остальных комплектующих материнской платы
138
Рис. 8.48. Оптимальные варианты видеокарты и остальных комплектующих материнской платы
139
Рис. 8.49. Определение оптимальных вариантов всех комплектующих материнской платы
140
Рис. 8.50. Определение оптимальных вариантов комплектующих УВВ
141
Рис. 8.51. Оптимальные варианты всех комплектующих персонального компьютера
На рис. 8.44–8.51 представлен процесс определения оптимальных комплектующих на основе известных оптимальных вариантов
блоков компьютера: накопителей, материнской платы и УВВ.
Варианты заданий многокритериальной оптимизации
сложного объекта
01. Максимальное число отказов за пять лет 5
8
1
7
2
20
2
8
1
10
3
13
1
9
1
7
1
7
1
0,01
18
7
1
8
2
0,01
17
7
1
8
1
0,01
16
02. Максимальное число отказов за пять лет 6
5
1
8
2
12
1
9
2
8
1
12
2
7
2
03. Максимальное число отказов за пять лет 7
5
1
8
2
12
4
9
3
8
3
12
3
7
2
04. Максимальное число отказов за пять лет 5
6
9
16
9
8
13
8
7
9
0,01
1
2
1
2
1
2
2
1
2
15
7
1
8
1
0,01
14
7
1
9
2
0,01
13
7
1
8
1
0,01
12
8
1
6
2
0,01
11
05 Максимальное число отказов за пять лет 6
5
1
8
2
12
2
9
1
8
3
12
1
7
1
06. Максимальное число отказов за пять лет 7
6
1
9
2
16
1
9
2
8
1
13
2
8
2
07. Максимальное число отказов за пять лет 5
5
1
8
2
12
2
9
1
8
3
12
1
7
1
08. Максимальное число отказов за пять лет 6
4
1
142
8
2
13
1
9
2
7
1
11
2
5
2
09. Максимальное число отказов за пять лет 7
5
1
8
2
12
2
9
1
8
3
12
1
7
1
7
1
8
1
0,01
10
7
1
9
2
0,01
9
7
1
8
1
0,01
8
7
1
7
2
0,01
7
7
1
8
1
0,01
6
7
1
9
2
0,01
18
7
1
8
1
0,01
17
7
1
7
2
0,01
16
7
1
8
1
0,01
15
7
1
9
2
0,01
14
10. Максимальное число отказов за пять лет 5
6
1
9
2
16
1
9
2
8
1
13
2
8
2
11. Максимальное число отказов за пять лет 6
5
1
8
2
12
2
9
1
8
3
12
1
7
1
12. Максимальное число отказов за пять лет 7
8
1
7
2
20
1
8
2
10
1
13
2
9
2
13. Максимальное число отказов за пять лет 5
5
1
8
2
12
2
9
1
8
3
12
1
7
1
14. Максимальное число отказов за пять лет 6
6
1
9
2
16
1
9
2
8
1
13
2
8
2
15. Максимальное число отказов за пять лет 7
5
1
8
2
12
2
9
1
8
3
12
1
7
1
16. Максимальное число отказов за пять лет 5
8
1
7
2
20
1
8
2
10
1
13
2
9
2
17. Максимальное число отказов за пять лет 6
5
1
8
2
12
2
9
1
8
3
12
1
7
1
18. Максимальное число отказов за пять лет 7
6
1
9
2
16
1
9
2
8
1
13
2
8
2
143
19. Максимальное число отказов за пять лет 5
5
1
8
2
12
4
9
3
8
3
12
3
7
2
7
1
8
1
0,01
13
7
1
7
2
0,01
12
7
1
8
1
0,01
11
7
1
9
2
0,01
10
7
1
8
1
0,01
9
7
1
8
2
0,01
8
7
1
8
1
0,01
7
7
1
9
2
0,01
6
7
1
8
1
0,01
18
7
1
9
2
0,01
17
20. Максимальное число отказов за пять лет 6
8
1
7
2
20
1
8
2
10
1
13
2
9
2
21. Максимальное число отказов за пять лет 7
5
1
8
2
12
2
9
1
8
3
12
1
7
1
22. Максимальное число отказов за пять лет 5
6
1
9
2
16
1
9
2
8
1
13
2
8
2
23. Максимальное число отказов за пять лет 6
5
1
8
2
12
2
9
1
8
3
12
1
7
1
24. Максимальное число отказов за пять лет 7
6
1
7
2
15
1
8
2
8
1
10
2
6
2
25. Максимальное число отказов за пять лет 5
5
1
8
2
12
2
9
1
8
3
12
1
7
1
26. Максимальное число отказов за пять лет 6
6
1
9
2
16
1
9
2
8
1
13
2
8
2
27. Максимальное число отказов за пять лет 7
5
1
8
2
12
2
9
1
8
3
12
1
7
1
28. Максимальное число отказов за пять лет 5
8
1
144
7
2
12
1
8
2
8
1
16
2
6
2
29. Максимальное число отказов за пять лет 6
5
1
8
2
12
4
9
3
8
3
12
3
7
2
7
1
8
1
0,01
16
7
1
9
2
0,01
15
7
1
8
1
0,01
14
7
1
7
2
0,01
13
30. Максимальное число отказов за пять лет 7
6
1
9
2
16
1
9
2
8
1
13
2
8
2
31. Максимальное число отказов за пять лет 5
5
1
8
2
12
2
9
1
8
3
12
1
7
1
32. Максимальное число отказов за пять лет 6
7
1
7
2
12
1
8
2
8
1
14
2
6
2
33. Максимальное число отказов за пять лет 7
5
8
12
9
8
12
7
7
8
0,01
1
2
2
1
3
1
1
1
1
12
7
1
9
2
0,01
11
7
1
8
1
0,01
10
7
1
7
2
0,01
9
7
1
8
1
0,01
89
7
1
9
2
0,01
7
34. Максимальное число отказов за пять лет 5
6
1
9
2
16
1
9
2
8
1
13
2
8
2
35. Максимальное число отказов за пять лет 6
5
1
8
2
12
4
9
3
8
3
12
3
7
2
36. Максимальное число отказов за пять лет 7
8
1
7
2
20
1
8
2
10
1
13
2
9
2
37. Максимальное число отказов за пять лет 5
5
1
8
2
12
2
9
1
8
3
12
1
7
1
38. Максимальное число отказов за пять лет 6
6
1
9
2
16
1
9
2
8
1
13
2
8
2
145
39. Максимальное число отказов за пять лет 7
5
1
8
2
12
4
9
3
8
3
12
3
7
2
7
1
8
1
0,01
6
7
1
7
2
0,01
18
7
1
8
1
0,01
17
7
1
9
2
0,01
16
7
1
8
1
0,01
15
7
1
7
2
0,01
14
7
1
8
1
0,01
13
7
1
9
2
0,01
12
7
1
8
1
0,01
11
7
1
7
2
0,01
10
40. Максимальное число отказов за пять лет 5
8
1
7
2
20
1
8
2
10
1
13
2
9
2
41. Максимальное число отказов за пять лет 6
5
1
8
2
12
2
9
1
8
3
12
1
7
1
42. Максимальное число отказов за пять лет 7
6
1
9
2
16
1
9
2
8
1
13
2
8
2
43. Максимальное число отказов за пять лет 5
5
1
8
2
12
4
9
3
8
3
12
3
7
2
44. Максимальное число отказов за пять лет 6
8
1
7
2
20
1
8
2
10
1
13
2
9
2
45. Максимальное число отказов за пять лет 7
5
1
8
2
12
2
9
1
8
3
12
1
7
1
46. Максимальное число отказов за пять лет 5
6
1
9
2
16
1
9
2
8
1
13
2
8
2
47. Максимальное число отказов за пять лет 6
5
1
8
2
12
1
9
3
8
3
12
3
7
2
48. Максимальное число отказов за пять лет 7
8
1
146
7
2
20
1
8
2
10
1
13
2
9
2
49. Максимальное число отказов за пять лет 5
5
1
8
2
12
1
9
3
8
3
12
3
7
2
7
1
8
1
0,01
9
7
1
9
2
0,01
8
7
1
8
1
0,01
7
7
1
9
2
0,01
6
50. Максимальное число отказов за пять лет 6
6
1
9
2
16
1
9
2
8
1
13
2
8
2
51. Максимальное число отказов за пять лет 7
5
1
8
2
12
1
9
3
8
3
12
3
7
2
52. Максимальное число отказов за пять лет 5
6
1
9
2
16
1
9
2
8
1
13
2
8
2
Библиографический список
1. Лебедев А. А. Введение в анализ и синтез систем: учеб. пособие. М.
Машиностроение. 2001. 351 с.
2. Данилов Н. Н. Введение в математическую экономику. Новосибирск,
2004. 431 с.
3. Методы оптимизации в примерах и задачах: учеб.-метод. пособие /
Бирюков Р. С., Городецкий С. Ю., Григорьева С. А. и др. Нижний Новгород: Нижегородский госуниверситет, 2010. 101 с.
4. Гайкович А. И. Основы теории проектирования сложных технических систем СПб.: Моринтех, 2001. 432 с.
5. Сергиенко И. В. Математические модели и методы решения задач
дискретной оптимизации. Киев: Наукова Думка, 1988. 472 с.
6. Зеленский В. А. Проектирование сложных систем. Электрон. учеб.
пособие / Минобрнауки России. Самар.гос.аэрокосм. ун-т им. С. П. Королева Самара 2012. 96 с.
7. Афанасьева О. В., Голик Е. С., Первухин Д. А. Теория и практика моделирования сложных систем: учеб. пособие. СПб.: СЗТУ, 2005. 131 с.
8. Печерских И. А., Семёнов А. Г. Математические модели в экономике:
учеб. пособие / КТИПП. Кемерово, 2011. 191 с.
9. Ковалёв М. Я. Модели и методы календарного планирования: курс
лекций. Минск, БГУ, 2004. 63 с.
10. Вагнер Г. Основы исследования операций. Т. 2. М.: Мир, 1973. 488 с.
11. Лотов А. В., Поспелова И. И. Многокритериальные задачи принятия решений: учеб. пособие. М.: МАКС Пресс, 2008. 197 с.
12. Беллман Р. Динамическое программирование. М.: ИИЛ, 1960. 400 с.
13. Смирнов О. Л. Автоматизация технологического проектирования:
учеб. пособие / СПб.: ГУАП, СПб., 2001. 66 с.
147
СОДЕРЖАНИЕ
Предисловие................................................................. 3
Раздел 1. Составление математических
моделей........................................................................ 4
Раздел 2. Задачи безусловной оптимизации....................... 26
Раздел 3. Задачи условной оптимизации........................... 31
Раздел 4. Оптимизация задач линейного
программирования......................................................... 36
Раздел 5. Целочисленное решение задач
линейного программирования ......................................... 72
Раздел 6. Оптимизации задач методом ветвей
и границ ...................................................................... 81
Раздел 7. Оптимизация линейных задач с бинарными
переменными................................................................ 89
Раздел 8. Многокритериальная оптимизации сложных
объектов....................................................................... 101
Библиографический список............................................. 147
148
Документ
Категория
Без категории
Просмотров
2
Размер файла
8 764 Кб
Теги
snirnov
1/--страниц
Пожаловаться на содержимое документа