Решебник_МО
.pdf
3.Сделаем загрузку клетки (2,3) с помощью построения цикла
(рис. 14).
х23 |
700 |
|
х23 100 |
600 |
|
|||||||||||
«+» |
|
|
|
|
|
|
|
«–» |
«+» |
|
|
|
|
|
|
«–» |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
К= in(700,100)=100 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
«+» |
f = sij*K=(–1)*100=–100 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
«–» |
|
|
|
|
|
|
|
«–» |
|
|
|
|
|
«+» |
||
|
|
|
|
|
|
|
|
|
|
|
|
|||||
100 |
400 |
|
0 |
|
|
500 |
|
|||||||||
ПолучаемРисновую. 14. Перераспределениераспределительнуюперевозоктаблицув примере 36
Получим новую распределительную матрицу (табл. 17). Таблица 17
|
|
В1 |
В2 |
В3 |
аi |
|
|
|
|
|
|
|
|
|
А1 |
3 |
5 |
6 |
800 |
|
|
|
800 |
* |
* |
|
|
|
|
|
|
|
|
|
|
А2 |
7 |
2 |
4 |
700 |
|
|
|
* |
600 |
100 |
|
|
|
|
|
|
|
|
|
|
А3 |
4 |
3 |
5 |
1000 |
|
|
|
200 |
* |
800 |
|
|
|
|
|
|
|
|
|
|
А4 |
6 |
4 |
7 |
500 |
|
|
|
* |
500 |
* |
|
|
|
|
|
|
|
|
|
|
bj |
1000 |
1100 |
900 |
|
|
|
|
|
|
|
|
|
4. Составим |
систему |
уравнений |
для новой таблицы: u1+v1 = 3, |
|||
u2+v2 = 2, u2+v3 = 4, u3+v1 = 4, u3+v3 = 5, u4+v2 = 4. |
||||||
Полагая v1 = 0, тогда u1 = 3, u3 = 4, v3 = 1, u4 = 5, v2 = –1, u2 = 3. 5. Вычислим оценки sij = сij–(ui+νj) для всех свободных клеток:
s12 |
= 5–(3+(–1)) = 3, s13 = 6–(3+1) = 2, s21 = 7–(3+0) = 4, |
s32 |
= 3–(4+(-1)) = 0, s41 = 6–(5+0) = 1, s43 = 7–(5+1) = 1. |
Полученный план оптимален, так как все sij ≥ 0. Этот план вырожденный, так как все s32 = 0, т.е. это один из оптимальных планов, дающих целевой функции значение:
Z(X*)=3*800+2*600+4*100+4*200+5*800+4*500=10800 усл.ед.
ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ
1.Оптимизационную задачу относят к линейному программированию, если
141
а) целевая функция и функции ограничений линейны;
b) целевая функция вогнута, а функции ограничений образуют
|
выпуклое множество; |
|
|
c) целевая функция линейна, а функции ограничений образуют |
|
|
выпуклое множество; |
|
|
d) целевая функция вогнута, а функции ограничений линейны; |
|
|
e) целевая функция вогнута и нет ограничений. |
|
2. |
Какие задачи ЛП можно решить графическим методом? |
|
3. |
Решением задачи f(x1,x2) = 2x1+x2→max, если 2x1+3x2 ≤ 6, x1 ≤ 2, |
|
|
x1 ≥ 0, x2 ≥ 0, является: |
|
|
а) X* = (0,2); f* = 2; |
б) X* = (2,2/3); f* = 14/3; |
|
в) X* = (0,0); f* = 0; |
г) X* = (2,0); f* = 4. |
4. |
Для задачи f(x1,x2) = 3x1+2x2→max если 4x1+5x2 ≤ 20, 3x+x2 ≤ 6, |
|
|
x2 ≤ 3, x1 ≥ 0, x2 ≥ 0 решением является: |
|
|
а) X* = (1,3); f* = 9; |
б) X* = (0,3); f* = 6; |
|
в) X* = (0,0); f* = 0; |
г) X* = (2,0); f* = 6. |
5.Как осуществляется приведение задачи ЛП к каноническому виду?
6.Как осуществляется построение допустимого (опорного) плана, оптимального плана задачи ЛП симплекс-методом?
7.Какие задачи ЛП называются вырожденными?
8.Что понимают под двойственностью в ЛП?
9.Какая существует связь между решениями прямой и двойственной задачами ЛП?
10.Двойственной для задачи f = x1+x3+x5→max, если xj ≥ 0, j = 1,…, 5, x1+2x2+3x3–x4–x5 ≤ 6, x1–x2–2x3+x4+x5 ≤ 5, является задача:
а) g = 5y1+6y2→max при y1+y2 ≥ 1, 2y1–y2 ≥ 0, 3y1–2y2 ≥ 1, –y1+y2 ≥ 0,
–y1+y2 ≥ 1, y1 ≥ 0, y2 ≥ 0;
б) g = 5y1+6y2→min при y1+y2 ≥ 1, 2y1–y2 ≥ 0, 3y1–2y2 ≥ 1, –y1+y2 ≥ 0,
–y1+y2 ≥ 1, y1 ≥ 0, y2 ≥ 0;
в) g = 6y1+5y2→max при y1+y2 ≤ 1, –y1+2y2 ≤ 0, –2y1+3y2 ≤ 1, y1–y2 ≤ 0, y1–y2 ≤ 1, y1 ≥ 0, y2 ≥ 0;
г) g = 6y1+5y2→min при y1+y2 ≥ 1, y1–y2 ≥ 0, 3y1–2y2 ≥ 1, –y1+y2 ≥ 0,
–y1+y2 ≥ 1, y1 ≥ 0, y2 ≥ 0.
11.Какую ЗЛП называют транспортной задачей?
12.Как строится допустимый план транспортной задачи?
13.В чем состоит идея метода потенциалов?
142
УПРАЖНЕНИЯ
1.Найдите область решений системы неравенств х1–1 0; x2–1 0; х1+х2–3 0; –6х1–7х2+42 0.
2.Найдите область решений системы неравенств xl 0, х1+х2-2 0;
|
x1-x2+l 0; x1 2. |
3. |
Решите задачу графическим способом: f(x1,x2) = 3x1+2x2→max, если |
|
4x1+5x2 ≤ 25; 3x1+x2 ≤ 8; x1 ≥ 0; 2 ≤ x2 ≤3. |
4. |
Найдите максимальное значение функции L=х1+3х2 при |
|
ограничениях 3x1+4х2 4; 3x1+х2 6; x1 ≥–1, х2 2. |
5. |
Минимизируйте функцию L = х1–x2 при ограничениях 3 x1+х2 7; |
|
1 х2 4; х 4. |
6. |
Найдите максимум функции L = x1+2х2+3х3 при ограничениях |
|
x1+х2 3; 3x1+х2–х3 0; 3x1+3х2–х3 0; х1 3. |
7.Определите максимальные неотрицательные решения, минимизирующие линейную форму L=х1–x2+х3+x4+х5–x6 при
|
ограничениях х1+х4+6х6 = 9; 3х1+х2–4х3–2х6 = 2; х1+2х3+х5+2х6 = 6. |
||||
8. |
Минимизируйте |
линейную |
форму |
L = 12х1+x2+3х3 |
при |
|
ограничениях 4х1+3х2+х3 = 180; 4х2+9х3+12х4 = 900; хi 0, i = l, 2, 3. |
||||
9. |
Максимизируйте |
линейную |
форму L = –x1–2x2–3x3 |
при |
|
|
ограничениях x1–2x2+3x3 –1; 2x1–x2–x3 1; x1, x2, x3 0. |
|
|||
10.Для изготовления изделий №1 и 2 склад может отпустить металла не более 80 кг, причем на изделие №1 расходуется 2 кг, а на изделие №2 – 1кг металла. Требуется спланировать производство так, чтобы была обеспечена наибольшая прибыль, если изделий №1 требуется изготовить не более 30 шт., а изделий №2 – не более 40шт., причем одно изделие № 1 стоит 5 руб., изделие №2 – 3 руб. Определите число изделий №1 и 2, выпуск которых позволит получить максимальную прибыль. Определите максимальную прибыль.
11.Дана исходная задача: найдите неотрицательные значения x1, х2,
максимизирующие линейную функцию L = 5xl+4х2 при системе ограничений 4х1+3х2 24; 3х1+4х3 24. Составьте двойственную задачу к исходной и решите ее графическим способом.
143
12. Дана исходная задача: найдите неотрицательные значения x1, х2, минимизирующие функцию L = 3x1+2х2 при ограничениях
7х1+2х2 14; 4х1+5х2 20.
13. Решите следующую задачу ЛП при помощи графического анализа двойственной задачи: Z = 4х1–18х2–30х3–5х4 max, x1, x2, x3, x4 0; 3x1+x2–4x3–x4 –3; –2x1–4x2–x3+x4 –3.
14.Для строительства четырех объектов используется кирпич, изготовляемый на трех заводах. Ежедневно каждый из заводов может изготовлять 100, 150 и 55 усл. ед. кирпича. Ежедневные потребности в кирпиче на каждом из строящихся объектов равны соответственно 95, 80, 60 и 70 усл. ед. Стоимости перевозок 1 усл. ед. кирпича с каждого завода к каждому из строящихся объектов
задается матрицей С: с11=15, с12=20, с13=15, с14=26, с21=10, с22=34, с23=81, с24=40, с31=45, с32=58, с33=34, с34=20. Составьте оптимальный план перевозки кирпича с заводов на объекты.
15.На трех хлебокомбинатах ежедневно производится 110, 190 и 90 т муки. Эта мука потребляется четырьмя хлебозаводами, ежедневные потребности которых равны соответственно 80, 60, 170 и 80 т. Тарифы перевозок 1т муки с хлебокомбинатов к каждому из хлебозаводов задаются матрицей С: с11=10, с12=9, с13=5, с14=6,
с21=10, с22=4, с23=8, с24=10, с31=4, с32=8, с33=4, с34=10. Требуется спланировать перевозки так, чтобы их общая стоимость была
минимальной.
16.На трех базах А1, А2,А3 находится однородный груз в количестве 150, 100, 25 т. Этот груз необходимо развести пяти потребителям В1 ,В2 ,В3 ,В4 ,В5, потребности которых в данном грузе составляют 140, 100, 40, 60, 160 т соответственно. Стоимость перевозок
задается матрицей С: с11=15, с12=9, с13=8, с14=11, с15=7, с21=10, с22=4,
с23=5, с24=7, с25=8, с31=6, с32=3, с33=4, с34=15, с35=18, с41=6, с42=4,
с43=7, с44=20, с45=15. Требуется спланировать перевозки так, чтобы их общая стоимость была минимальной.
144
ЗАКЛЮЧЕНИЕ
Оптимальное решение проблемы порой имеет для нас немаловажное значение. Диапазон задач оптимизации в технике настолько широк, что найти между ними что-нибудь общее кажется невозможным. Однако математическая природа многих задач одна и та же, следовательно, умению находить оптимальные решения можно научиться, как и другим навыкам, необходимым в профессиональной и повседневной жизни.
Любые методы, которые помогают лучше понять желаемые цели и оценить имеющиеся ресурсы, являются полезными. Над такими методами работают математики, инженеры, экономисты, юристы, военные. Однако проблемы поиска оптимальных решений необходимо ставить и рассматривать с единых позиций, в независимости от областей конкретного приложения. Несомненна связь методов оптимизации с теорией принятия решений, с исследованием операций, информатикой, искусственным интеллектом. В тоже время методы оптимизации имеют свою, отличную от прочих направлений, логику развития.
Одна из целей данного решебника состояла в том, чтобы помочь студентам овладеть навыками практического использования наиболее распространенных математических методов, широко используемых при решении оптимизационных задач в различных областях человеческой деятельности. На его основе можно осуществить эффективный процесс обучения, отличающийся минимально необходимым временем аудиторных занятий при максимально возможной мотивации самостоятельной работы.
Авторы будут считать свою задачу выполненной, если после изучения решебника хотя бы один из будущих или действующих специалистов сочтет возможным и полезным использовать методы оптимизации на практике.
145
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1.Галлеев Э.М., Тихомиров В.М. Оптимизация: теория, примеры, задачи. – М.: Эдиториал УРСС, 2000. – 320 с.
2.Джонс М.Т. Программирование искусственного интеллекта в приложениях: Пер. с англ. – М.: ДМК Пресс, 2006. – 312 с.
3.Измаилов А.Ф., Солодов М.В. Численные методы оптимизации: Уч. пособие. – М.: Физматлит, 2005. – 304 с.
4.Карманов В.Г. Математическое программирование: Уч. пособие.
–М.: Физматлит, 2004. – 264 с.
5.Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации: Уч. пособие. – М.: Физматлит, 2005. – 368 с.
6.Таха Хэмди А. Введение в исследование операций. – М.: Изд. дом
«Вильямс», 2005. – 912 с.
7.Карелин В.П., Родзин С.И. Поисковая оптимизация: Уч. пособие.
–Таганрог: Изд-во ТРТУ, 1999. – 80 с.
8.Родзин С.И., Ковалев С.М. Информационные технологии: интеллектуализация обучения, моделирование эволюции, распознавание речи. – Ростов-на-Дону: Изд-во СКНЦ ВШ, 2002.
–224 с.
9.Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы. – М.: Горячая линия –
Телеком, 2004. – 383 с.
Интернет-источники
10.Балдин К.В. и др. Математическое программирование [Электронный ресурс]. – М.: Дашков и К, 2012. – 219 с. Режим доступа: http://www.biblioclub.ru/book/112201/.
11.Курейчик В.М., Курейчик В.В., Родзин С.И. Теория эволюционных вычислений [Электронный ресурс]. – М.: Физматлит, 2012. – 260 с. Режим доступа: http://www.rfbr.ru/rffi/ru/books/o_1780980#1.
12.Ларин Р.М. и др. Методы оптимизации. Примеры и задачи: Уч. пособие [Электронный ресурс]. Режим доступа:
http://math.nsc.ru/LBRT/k5/Plyasunov/opt-2.html.
146
13.Лунгу К.Н. Линейное программирование. Руководство к решению задач [Электронный ресурс]. – М.: Физматлит, 2009. - 132 с. Режим доступа: http://www.biblioclub.ru/book/82255/.
14.Методы оптимизации (вводный курс) [Электронный ресурс].
Режим доступа: http://sapr.mgsu.ru/biblio/ optimiz/opt.htm.
15.Пантелеев А.В. Методы оптимизации: Практический курс [Электронный ресурс]. – М.: Логос, 2011. – 424 с. Режим доступа: http://www.biblioclub.ru/book/84995/.
16.Симплекс-метод [Электронный ресурс]. Режим доступа: http://imcs.dvgu.ru/lib/nurmi/finmath/node45.html.
17.Струченков В.И. Методы оптимизации в прикладных задачах [Электронный ресурс]. - М.: Солон-Пресс, 2009. - 315 с. Режим доступа: http://www.biblioclub.ru/book/117856/.
18.Data Mining, Web Mining, Knowledge Discovery [Электронный ресурс]. Режим доступа: http://www.kdnuggets.com.
19.MatLab – Optimization Toolbox http://matlab.exponenta.ru/optimiz/.
20.Библиотека для реализации генетических алгоритмов в .NET Framework 2.0 [Электронный ресурс]. Режим доступа: http://jenyay.net/index.php?n=Programming.Genetic.
21.Koza J.R. Genetic Programming [Электронный ресурс]. Cambridge: MA:MIT Press, 1992. Режим доступа: http://www.ru.lv/~peter/zinatne/ebooks/MIT%20-%20Genetic%20
Programming.pdf.
147