Министерство образования Республики Беларусь БЕЛОРУССКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра «Высшая математика № 3» МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ Программные вопросы, контрольные задания и методические указания Минск БНТУ 2013 1 Министерство образования Республики Беларусь БЕЛОРУССКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра «Высшая математика № 3» МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ Программные вопросы, контрольные задания и методические указания для студентов-заочников строительных специальностей экономического профиля Минск БНТУ 2013 2 УДК 51(075.4) ББК 221я7 М34 Составители: Т. Н. Гурина, О. А. Мороз Рецензенты: А. Д. Корзников, Т. С. Яцкевич Издание содержит перечень программных вопросов по математическо- му программированию. В нем приводятся тексты контрольных задач, соот- ветствующих программе, и методические указания по их выполнению. Издание предназначено для студентов-заочников строительных спе- циальностей экономического профиля. © Белорусский национальный технический университет, 2013 3 ВВЕДЕНИЕ Общий курс математики является фундаментом математического образования специалиста, в рамках которого проводится ориенти- рование на приложение математических методов в профессиональ- ной деятельности. Студенты экономических специальностей в чет- вертом семестре изучают математическое программирование, по- скольку в последующей практической деятельности будут встречаться с математическими методами оптимизации. При выполнении контрольной работы необходимо строго при- держиваться указанных ниже правил. 1. Каждая работа должна быть выполнена в отдельной тетради в клетку чернилами любого цвета, кроме красного и зеленого. Необ- ходимо оставлять поля шириной 4-5 см. для замечаний рецензента. 2. В заголовке на обложке тетради должны быть ясно написаны фамилия студента, его инициалы, учебный номер (шифр), название дисциплины; здесь же следует указать название учебного заведения, дату отсылки работы в институт и адрес студента. В конце работы следует поставить дату ее выполнения и подпись студента. 3. Решение задач надо располагать в порядке возрастания их но- меров, указанных в заданиях. 4. Перед решением каждой задачи надо полностью написать ее условие. В случае общей формулировки задач условие должно быть сформулировано с конкретными данными соответствующего номе- ра варианта. 5. Решение задач следует излагать подробно и аккуратно, объяс- няя и мотивируя все действия по ходу решения и делая необходи- мые чертежи. 6. После полученной прорецензированной контрольной работы, как недопущенной, так и допущенной к собеседованию, студент должен исправить все отмеченные рецензентом ошибки и недочеты в той же тетради под заголовком «Работа над ошибками», выпол- нить все рекомендации рецензента, после чего работа должна быть возвращена на повторное рецензирование 4 ПРОГРАММА КУРСА Раздел 1. Линейное программирование 1. Предмет и задачи математического программирования. Ос- новные определения. 2. Постановка и различные формы записи задач линейного про- граммирования и их эквивалентность. 3. Основная теорема линейного программирования. 4. Геометрический метод решения задачи линейного программи- рования. 5. Основная идея симплекс-метода. Симплекс-таблица. 6. Признак оптимальности опорного плана задачи линейного программирования. 7. Улучшение начального опорного плана задачи линейного про- граммирования с помощью симплексных преобразований. 8. Признак неограниченности целевой функции задачи линейно- го программирования. 9. Признак бесконечности множества оптимальных планов зада- чи линейного программирования. 10. Двойственная задача линейного программирования и ее по- строение для задачи линейного программирования в симметриче- ской форме. 11. Построение двойственной задачи для задачи линейного про- граммирования в канонической форме. 12. Соответствие между переменными взаимодвойственных за- дач и решение двойственной задачи. 13. Основное неравенство теории двойственности и его эконо- мическая интерпретация. 14. Достаточный признак оптимальности взаимодвойственных задач линейного программирования. 15. Теоремы двойственности и их экономическая интерпретация. 16. Двойственные оценки как мера дефицитности сырья. Теоре- ма об оценках. 17. Постановка и математическая модель транспортной задачи. 18. Признак разрешимости транспортной задачи. 19. Открытая и закрытая модели транспортной задачи их связь. 20. Построение начального опорного плана транспортной задачи. 5 21. Признак оптимальности опорного плана транспортной задачи. 22. Улучшение опорного плана транспортной задачи. 23. Дополнительные ограничения в постановке транспортной за- дачи и методы решения таких задач. Раздел 2. Элементы теории матричных игр 24. Решение матричной игры двух лиц с нулевой суммой в чи- стых стратегиях. 25. Смешанные стратегии игроков и их свойства. 26. Критерий оптимальности смешанных стратегий в матричной игре. 27. Упрощение матричной игры. 28. Сведение матричной игры к паре взаимодвойственных задач. 29. Игры с природой. Платежная матрица игры, матрица тисков. 30. Критерии Байеса, Лапласа, Вальда, Сэвиджа, Гурвица для определения оптимальных стратегий в играх с природой. Раздел 3. Оптимизация на сетях 31. Основные определения и понятия теории графов. 32. Алгоритм Фалкерсона для упорядочения вершин графа. 33. Транспортная задача в сетевой постановке и ее решение. 34. Постановка задачи о максимальном потоке на сети, ее мате- матическая модель. 35. Поток на сети, его свойства. Разрез на сети, его свойства. 36. Теорема Форда–Фалкерсона о максимальном потоке на сети. 37. Алгоритм Форда–Фалкерсона о построении минимального разреза на сети. 38. Методы «списков» и «меток» для решения задачи о макси- мальном потоке на сети. 39. Основные определения и принципы построения сетевых гра- фиков. 40. Постановка задачи о минимальной продолжительности ком- плекса работ. 41. Временные характеристики событий сетевого графика. 42. Временные характеристики работ сетевого графика. 6 Раздел 4. Динамическое программирование 43. Многошаговые процессы в оптимизационных задачах. Метод динамического программирования. Уравнения Беллмана. 44. Задача о распределении ресурсов. 45. Задача о замене оборудования. ЛИТЕРАТУРА 1. Красс, М.С. Математика в экономике / М.С. Красс. – М.: ИД ФБК – ПРЕСС, 2005. 2. Кузнецов, А.В. Высшая математика. Математическое про- граммирование / А.В. Кузнецов, В.А. Сакович, Н.И. Холод. – Минск: Вышэйшая школа, 2001. 3. Кузнецов, А.В. Руководство к решению задач по математиче- скому программированию / А.В. Кузнецов, Н.И. Холод, Л.С. Кос- тевич. – Минск: Вышэйшая школа, 2001. 4. Сакович, В.А. Исследование операций / В.А. Сакович. – Минск: Вышэйшая школа, 1985. 5. Сборник задач и упражнений по высшей математике. Матема- тическое программирование / под ред. А.В. Кузнецов.– Минск: Вышэйшая школа, 1995. 6. Красс, М.С. Математика для экономического бакалавриата / М.С. Красс, Б.П. Чупрынов. – М.: Дело, 2005. 7. Математические методы и модели исследования операций / под ред. В.А. Колемаева. – М.: ЮНИТИ, 2008. 8. Общий курс высшей математики для экономистов: учебник / под ред. Ермакова. – М.: ИНФРА, 2006. 7 КОНТРОЛЬНЫЕ ЗАДАНИЯ Задания 1–10. Решить графически задачу линейного програм- мирования. 1.          .0,40,1 ,102 ,1256 min352 321 321 21 321 xxx xxx xx xxxf 2.          .0,0,0,100 ,52 ,222 max2 4321 321 4321 421 xxxx xxx xxxx xxxf 3.             .0,0,0,0 ,8 ,0 ,62 min32 4321 41 21 321 4321 xxxx xx xx xxx xxxxf 4.             .0,0,0 ,42 ,0 ,632 min 321 21 21 321 321 xxx xx xx xxx xxxf 5.             .0,0,20 ,42 ,03 ,1 max3 321 21 21 321 31 xxx xx xx xxx xxf 6.             .0,0,0 ,02 ,12 ,2 min3 321 21 21 321 321 xxx xx xx xxx xxxf 7.          .0,1,0 ,02 ,42 max 321 21 321 321 xxx xx xxx xxxf 8.          .0,0,10 ,13 ,2 max4 321 21 321 321 xxx xx xxx xxxf 8 9.             .0,0,100 ,03 ,42 ,3 min 321 21 21 321 321 xxx xx xx xxx xxxf 10.          .0,40,1 ,1223 ,0 min24 321 21 321 321 xxx xx xxx xxxf Задания 11−20. Предприятие ежемесячно имеет отходы (ресур- сы) трех типов В1, В2, В3, объемы которых определяются величина- ми b1 , b2 , b3 (усл.ед.) Из этих отходов предприятие может орга- низовать производство четырех видов изделий А1, А2, А3, А4, при- чем продукция может производиться в любых соотношениях (сбыт обеспечен). Расход ресурсов i -го типа на производство единицы изделия j-го типа определяется величиной )4,1,3,1(  jiaij (усл.ед.) , а стоимость единицы продукции j-го типа – величиной )4,1(, jc j (усл.руб.). Значения jij ca , приведены в таблицах. Требуется: 1. Составить модель задачи определения ассортиментного плана производства, при котором расход ресурсов не превысит имеюще- гося количества, а суммарная стоимость произведенной продукции будет максимальной. 2. Привести полученную задачу линейного программирования к каноническому виду. Объяснить экономический смысл введенных балансовых переменных. 3. Найти симплекс-методом оптимальный ассортиментный план производства. Дать экономическую интерпретацию полученного результата. 4. Составить двойственную задачу для исходной. Оценить каж- дый из ресурсов, чтобы при заданных объемах ресурсов и величи- нах стоимости единицы продукции суммарная стоимость сырья бы- ла минимальной, а оценка ресурсов, необходимых для производства единицы продукции, была не меньше стоимости единицы продук- ции данного вида. 9 5. Определить меру дефицитности сырья и увеличение стоимо- сти продукции при изменении объема сырья на единицу. 6. Оценить целесообразность введения в план производства но- вого вида изделий А5, нормы затрат ресурсов на производство еди- ницы продукции и стоимость от реализации единицы продукции которого приведены в таблице. № 11 Расход сырья на производство единицы продукции Объем сырья bi А1 А2 А3 А4 А5 В1 2 2 1 2 3 3000 В2 2 1 1 0 1 1000 В3 1 2 1 1 2 2500 Стоим. jc 4 5 2 3 3 № 12 Расход сырья на производство единицы продукции Объем сырья bi А1 А2 А3 А4 А5 В1 2 1 3 2 1 1500 В2 2 2 0 2 2 1700 В3 0 3 1 1 3 700 Стоим. jc 3 2 3 4 2 № 13 Расход сырья на производство единицы продукции Объем сырья bi А1 А2 А3 А4 А5 В1 2 4 3 1 3 3000 В2 2 0 1 2 1 400 В3 1 1 2 2 1 1000 Стоим. jc 3 2 4 3 2 10 № 14 Расход сырья на производство единицы продукции Объем сырья bi А1 А2 А3 А4 А5 В1 2 2 1 0 2 1500 В2 2 3 2 2 2 3000 В3 0 1 2 1 1 500 Стоим. jc 3 3 2 2 3 № 15 Расход сырья на производство единицы продукции Объем сырья bi А1 А2 А3 А4 А5 В1 2 3 2 1 3 3000 В2 3 4 1 2 1 4200 В3 2 1 1 0 1 500 Стоим. jc 3 4 2 2 3 № 16 Расход сырья на производство единицы продукции Объем сырья bi А1 А2 А3 А4 А5 В1 1 2 1 2 3 2500 В2 2 1 2 0 2 1000 В3 3 2 2 3 2 3000 Стоим. jc 3 5 3 4 4 № 17 Расход сырья на производство единицы продукции Объем сырья bi А1 А2 А3 А4 А5 В1 0 1 1 1 1 1000 В2 2 2 2 1 2 2000 В3 3 2 2 0 2 2400 Стоим. jc 3 2 3 2 3 11 № 18 Расход сырья на производство единицы продукции Объем сырья bi А1 А2 А3 А4 А5 В1 1 3 2 3 1 2400 В2 2 2 1 2 0 1500 В3 2 1 3 0 2 600 Стоим. jc 3 5 3 4 2 № 19 Расход сырья на производство единицы продукции Объем сырья bi А1 А2 А3 А4 А5 В1 2 2 3 2 3 3000 В2 0 1 1 2 1 1000 В3 3 1 1 0 2 1200 Стоим. jc 3 2 4 3 4 № 20 Расход сырья на производство единицы продукции Объем сырья bi А1 А2 А3 А4 А5 В1 2 2 2 1 2 3000 В2 1 0 1 2 3 800 В3 1 2 2 1 4 2800 Стоим. jc 4 3 5 4 5 Задания 21–30. Производственное объединение имеет в своем составе три фирмы )3,1( iAi , которые производят однородную продукцию в объемах ia . Готовая продукция поставляется потреби- телям  3,1jB j , спрос которых определяется, соответственно, ве- личинами jb . Известны стоимости перевозки единицы продукции  3,1,3,1  jicij от поставщика )3,1( iAi к потребителю  3,1jB j , которые приведены в таблицах. Задача 1. Составить математическую модель задачи определе- ния плана перевозки готовой продукции от поставщиков )3,1( iAi 12 потребителям  4,1jB j , чтобы запасы поставщиков были вывезе- ны, спрос всех потребителей был удовлетворен, а суммарные транспортные издержки были минимальными. Методом потенциа- лов найти оптимальный план перевозки продукции от поставщиков к потребителям. Указать запасы оставшейся продукции у постав- щиков. Задача 2. Методом потенциалов найти оптимальный план пере- возки при дополнительном условии, что продукция пункта произ- водства )3,1( iAi , в котором себестоимость  3,1ici производи- мой продукции наименьшая, должна быть распределена полностью, а суммарные затраты, вызванные производством и доставкой про- дукции, были бы минимальными. Задача 3. Методом потенциалов найти оптимальный план пере- возки продукции при дополнительном условии, что перевозка от поставщика nA к потребителю kB запрещена. Задача 4. Методом потенциалов найти оптимальный план пере- возки продукции при дополнительном условии, что перевозка от поставщика mA к потребителю lB ограничена d единицами. Задача 5. Методом потенциалов найти оптимальный план пере- возки продукции при выполнении обязательной перевозки от по- ставщика rA к потребителю sB в объеме не менее p единиц. Во всех задачах вычислить величину наименьших суммарных затрат и сравнить с затратами начального плана перевозок. № 21 1B 2B 3B Запа- сы ia 1A 4 3 4 100 К задаче 2: 5,9,7 321  ccc 2A 3 2 5 70 К задаче 3: n=1, k=1 3A 5 4 4 80 К задаче 4: m=1, l=1, d=50 Спрос jb 90 80 50 К задаче 5: r=3, s=1, p=40 13 № 22 1B 2B 3B Запа- сы ia 1A 3 4 5 40 К задаче 2: 4,5,6 321  ccc 2A 5 3 4 90 К задаче 3: n=2, k=2 3A 4 4 5 70 К задаче 4: m=2, l=2, d=30 Спрос jb 60 80 40 К задаче 5: r=1, s=3, p=30 № 23 1B 2B 3B Запа- сы ia 1A 3 5 4 80 К задаче 2: 5,4,6 321  ccc 2A 4 4 5 60 К задаче 3: n=1, k=1 3A 5 3 3 100 К задаче 4: m=1, l=1, d=40 Спрос jb 90 50 70 К задаче 5: r=1, s=2, p=40 № 24 1B 2B 3B Запа- сы ia 1A 3 1 4 60 К задаче 2: 2,4,6 321  ccc 2A 5 2 3 70 К задаче 3: n=1, k=2 3A 2 4 5 90 К задаче 4: m=2, l=3, d=50 Спрос jb 50 40 80 К задаче 5: r=3, s=2, p=20 № 25 1B 2B 3B Запа- сы ia 1A 9 7 6 180 К задаче 2: 4,5,3 321  ccc 2A 5 10 4 60 К задаче 3: n=1, k=3 14 3A 3 8 2 50 К задаче 4: m=3, l=1, d=20 Спрос jb 100 120 60 К задаче 5: r=1, s=1, p=80 № 26 1B 2B 3B Запа- сы ia 1A 7 4 9 90 К задаче 2: 4,6,3 321  ccc 2A 8 5 3 80 К задаче 3: n=2, k=3 3A 4 6 5 50 К задаче 4: m=1, l=2, d=30 Спрос jb 60 70 50 40 К задаче 5: r=3, s=2, p=30 № 27 1B 2B 3B Запа- сы ia 1A 3 9 7 100 К задаче 2: 4,6,5 321  ccc 2A 5 4 3 60 К задаче 3: n=1, k=1 3A 6 8 3 80 К задаче 4: m=3, l=3, d=20 Спрос jb 70 40 60 К задаче 5: r=1 ,s=2, p=30 № 28 1B 2B 3B Запа- сы ia 1A 1 3 4 60 К задаче 2: 4,7,9 321  ccc 2A 2 5 1 50 К задаче 3: n=1, k=1 3A 4 5 3 70 К задаче 4: m=2, l=3, d=20 Спрос jb 40 90 30 К задаче 5: r=3, s=1, p=30 15 № 29 1B 2B 3B Запа- сы ia 1A 6 7 8 80 К задаче 2: 5,4,7 321  ccc 2A 9 10 4 100 К задаче 3: n=2, k=3 3A 3 5 9 70 К задаче 4: m=3, l=1, d=30 Спрос jb 60 90 80 К задаче 5: r=1, s=3, p=60 № 30 1B 2B 3B Запа- сы ia 1A 4 8 10 120 К задаче 2: 7,6,4 321  ccc 2A 5 3 9 60 К задаче 3: n=2, k=2 3A 6 7 4 90 К задаче 4: m=1, l=1, d=50 Спрос jb 100 50 80 К задаче 5: r=2, s=3, p=40 Задания 31–40. Две отрасли А и В могут вкладывать денежные средства в строительство четырех объектов, причем отрасль А рас- полагает a = 70 млн.усл.руб., а отрасль В – b = 56 млн.усл.руб. С учетом особенностей вкладов и местных условий прибыль отрасли А в зависимости от объема финансирования выражается элемента- ми матрицы C. Будем предполагать, что убыток отрасли В при этом равен при- были отрасли А. Требуется: 1. Выявить игроков и описать их стратегии. 2. Проверить, имеет ли игра решение в чистых стратегиях. 3. Упростить матричную игру, исключив доминируемые страте- гии игроков. 4. Составить экономико-математическую модель данной кон- фликтной ситуации для каждого игрока. 5. Найти оптимальные стратегии игроков. 6. На основании полученного результата распределить денежные средства между объектами. 16 31.              571311 8977 46109 910812 С 32.              7868 5652 4463 9575 С 33.              54133 7811 9723 12845 С 34.              48109 3478 7532 10789 С 35.              91155 8943 2156 3467 С 36.              651211 43910 5611 9742 С 37.              7635 6124 4357 6568 С 38.              10893 1362 8937 91158 С 39.              4356 1243 2321 8572 С 40.              89129 5683 3754 12975 С Задания 41−50. Объем реализации товара за рассматриваемый период времени колеблется в зависимости от уровня покупатель- ского спроса в пределах от k 1 до k 2 тыс. ед. Прибыль торгового предприятия от единицы реализованного товара равна l ден.ед. Ес- ли запасенного товара окажется недостаточно для полного удовле- творения спроса, можно заказать дополнительное количество това- ра, что потребует новых затрат на доставку в размере m ден.ед. в расчете на единицу товара. Если же запасенный товар полностью реализовать не удастся, то расходы на содержание и хранение остатка составят n ден.ед. в расчете на единицу товара. Предполага- 17 ется, что дополнительно заказанный товар полностью реализуется за тот же рассматриваемый период времени. Требуется: 1. Придать описанной производственной ситуации игровую схему, выявить игроков и описать их стратегии. 2. Составить платежную матрицу игры. 3. Дать рекомендации об оптимальном уровне запаса товара на торговом предприятии, обеспечивающем ему наивысшую эффек- тивность работы с учетом торговой прибыли и возможных допол- нительных затрат на заказ и доставку товара, содержание и хране- ние остатка, если: а) известны вероятности уровней покупательского спроса, и они, соответственно, равны q 1 , q 2 , q 3 , q 4 ; б) известно, что все уровни покупательского спроса равноверо- ятны; в) никакой дополнительной информации об уровнях покупатель- ского спроса нет (для нахождения оптимальной стратегии приме- нить критерии Вальда, Сэвиджа, Гурвица ). Постоянная λ задана. Числовые данные приведены в таблице: № за- да- ния k1 k2 l m n q1 q2 q3 q4 λ 41 1 4 5 3 1 0,1 0,35 0,4 0,15 0,6 42 3 6 4 2 1 0,15 0,4 0,3 0,15 0,7 43 4 7 7 3 2 0,2 0,45 0,2 0,15 0,8 44 2 5 6 4 2 0,2 0,35 0,35 0,1 0,7 45 5 8 5 2 1 0,15 0,4 0,3 0,15 0,6 46 4 7 4 2 1 0,2 0,25 0,45 0,1 0,8 47 1 4 8 4 3 0,1 0,45 0,25 0,2 0,7 48 3 6 6 3 2 0,15 0,4 0,35 0,1 0,8 49 2 5 7 4 2 0,25 0,4 0,2 0,15 0,7 50 4 7 5 3 2 0,2 0,35 0,25 0,2 0,8 Задания 51–60. Дана сеть с указанными пропускными способно- стями ребер ijr (одинаковы в обоих направлениях). 18 S 1 2 4 3 6 7 5 13 10 9 5 11 1 8 8 6 4 12 9 14 16 2 I S 1 2 4 3 5 7 6 11 5 7 12 8 5 6 2 9 10 6 4 18 3 I 7 S I 1 2 3 5 7 8 7 9 4 8 4 5 6 7 8 9 5 3 6 10 8 4 6 4 Найти: 1) Максимальный поток из источника I в сток S методом меток; 2) Минимальный разрез (указать пунктирной линией на сети). 51. 52. 53. 19 S 1 2 4 3 6 7 5 9 12 15 7 10 6 6 11 13 13 4 18 3 I 8 S 1 2 4 3 6 8 7 16 6 9 12 7 8 5 5 10 10 9 7 I 4 3 8 6 S 1 2 4 3 6 7 5 7 7 11 6 10 8 13 6 5 9 9 10 8 I 7 12 15 4 1 2 4 3 7 5 12 4 7 8 10 2 6 3 5 8 10 6 I 4 5 9 3 6 9 8 S 54. 55. 56. 57. 20 S 1 2 3 4 7 8 7 9 12 8 10 5 6 7 12 8 5 14 6 14 8 10 5 13 I S 1 2 3 8 7 13 13 10 15 14 5 7 12 9 5 14 6 12 8 17 6 11 I 4 S 1 2 3 5 8 7 12 4 16 13 14 4 13 6 9 17 10 11 15 10 8 6 11 I 17 9 58. 59. 60. 21 Задания 61–70. Дан список работ, подлежащих выполнению: 61. 62. Ра- бо- та Непосред- ственно предшест- вующие работы Продолжи- тельность работы а1 - 3 а2 - 7 а3 - 4 а4 - 5 а5 а1 4 а6 а1 2 а7 а2, а6 8 а8 а2, а6 6 а9 а3, а6 9 а10 а3, а4, а6 4 а11 а4 7 а12 а5 6 а13 а5 5 а14 а7, а9, а12, а13 4 а15 а10, а11 3 а16 а12 9 Ра- бо- та Непосред- ственно предшест- вующие работы Продолжи- тельность работы а1 - 4 а2 - 6 а3 - 9 а4 - 8 а5 а4 3 а6 а4 7 а7 а4 2 а8 а3, а7 5 а9 а1 8 а10 а1, а9 4 а11 а1, а9 3 а12 а5 4 а13 а5 9 а14 а2, а6, а8, а11, а13 4 а15 а12 8 22 63. 64. Работа Непосред- ственно предше- ствующие работы Продол- житель- ность работы а1 - 3 а2 - 7 а3 - 4 а4 а1 5 а5 а1 3 а6 а1 9 а7 а3, а6 2 а8 а3, а6 9 а9 а2, а7 6 а10 а4 8 а11 а2, а7, а8 2 а12 а5, а10 4 а13 а2, а7, а8 5 а14 а2, а7, а8 9 а15 а9, а14 7 Рабо- та Непосред- ственно предше- ствующие работы Продолжи- тельность работы а1 - 8 а2 - 4 а3 - 9 а4 а3 5 а5 а3 4 а6 а3 7 а7 а1 2 а8 а1 8 а9 а1 9 а10 а2, а3, а4 9 а11 а7 2 а12 а6 5 а13 а5, а10, а12 7 а14 а5, а10, а12 6 а15 а8, а11, а13 8 а16 а6 4 23 65. 66. Работа Непосред- ственно предше- ствующие работы Продол- житель- ность работы а1 - 7 а2 - 9 а3 - 3 а4 - 4 а5 а1 3 а6 а1 9 а7 а2 9 а8 а5 8 а9 а4, а5, а6 6 а10 а4, а5, а6 2 а11 а4, а5, а6 5 а12 а2, а3 4 а13 а2, а3, а11 6 а14 а8, а9 7 а15 а7, а12 5 Рабо- та Непосред- ственно предше- ствующие работы Продолжи- тельность работы а1 - 3 а2 - 7 а3 - 5 а4 - 5 а5 а3 9 а6 а3 3 а7 а1 9 а8 а4, а5 4 а9 а4, а5 6 а10 а7 3 а11 а1, а2, а6, а9 4 а12 а1, а2, а6, а9 8 а13 а8 2 а14 а10, а12 6 24 67. 68. Работа Непосред- ственно предше- ствующие работы Продол- житель- ность работы а1 - 3 а2 - 7 а3 - 5 а4 а2 5 а5 а2 9 а6 а2 3 а7 а3 9 а8 а3 4 а9 а3 6 а10 а1, а6, а9 3 а11 а5, а8, а10 4 а12 а5, а8, а10 8 а13 а4,, а5, а8, а10 2 а14 а7, а11 6 Рабо- та Непосред- ственно предше- ствующие работы Продолжи- тельность работы а1 - 5 а2 - 8 а3 - 4 а4 - 2 а5 а3 6 а6 а4 9 а7 а4 6 а8 а1, а2, а7 2 а9 а1, а2, а7 9 а10 а2 5 а11 а2 4 а12 а2 3 а13 а5, а12 7 а14 а6, а8 7 а15 а9, а10, а14 6 25 69. 70. Работа Непосред- ственно предше- ствующие работы Продол- житель- ность работы а1 - 6 а2 - 2 а3 - 9 а4 - 4 а5 а1 7 а6 а1 3 а7 а4 6 а8 а4 4 а9 а3, а4 5 а10 а3, а4 8 а11 а2, а6 5 а12 а2, а5, а6 8 а13 а7, а9 4 а14 а7, а9 2 а15 а10, а11, а12, а13 9 Рабо- та Непосред- ственно предше- ствующие работы Продолжи- тельность работы а1 - 8 а2 - 3 а3 - 5 а4 а1 6 а5 а1 2 а6 а1 4 а7 а3 6 а8 а3 8 а9 а2, а4 9 а10 а5, а9 9 а11 а5, а9 7 а12 а5, а9 5 а13 а3, а7, а12 2 а14 а3, а7, а12 3 а15 а3, а7, а12 6 а16 а8, а13 7 Требуется: 1. Построить сетевой график выполнения комплекса работ. 2. Непосредственно на графике вычислить ранние и поздние сроки свершения событий, резервы времени событий. 26 3. Выделить на графике критический путь и найти критический срок. 4. Найти полные и свободные резервы времени работ. Задания 71–80. На строительство четырех предприятий, произ- водящих некоторую однородную продукцию, выделено 6 млн.усл.руб. По каждому из четырех предприятий известен воз- можный объем выпуска продукции   4,1ixgi (усл. ед.) в зависи- мости от капиталовложений  60  xx , выделенных на строи- тельство. Значения   4,1ixgi (усл. ед.) приведены в таблице. Требуется: 1. Составить математическую модель задачи распределения капиталовложений в строительство предприятий, чтобы суммарный объем выпускаемой продукции был максимальным, и найти реше- ние этой задачи. 2. Используя полученное решение, найти: а) оптимальное (в смысле наибольшего объема выпускаемой продукции) распределение 6 млн.усл.руб. между тремя предприяти- ями, б) оптимальное распределение 4 млн.усл.руб. между тремя предприятиями. № 71 1 2 3 4 5 6  xg1 12 14 15 18 23 25  xg2 13 15 16 19 21 24  xg3 14 16 18 21 22 25  xg4 11 13 16 20 22 24 № 72 1 2 3 4 5 6  xg1 27 30 32 35 37 36  xg2 24 28 31 34 36 40  xg3 25 29 30 32 37 42  xg4 29 31 32 36 38 35 27 № 73 1 2 3 4 5 6  xg1 17 20 21 23 25 30  xg2 14 19 22 27 30 26  xg3 16 18 21 25 27 30  xg4 18 22 27 35 31 29 № 74 1 2 3 4 5 6  xg1 10 14 18 25 29 30  xg2 12 13 17 21 25 29  xg3 13 18 22 23 28 25  xg4 12 15 20 21 25 27 № 75 1 2 3 4 5 6  xg1 12 18 22 24 30 35  xg2 15 17 20 24 32 37  xg3 14 20 21 25 29 32  xg4 13 16 20 25 29 32 № 76 1 2 3 4 5 6  xg1 24 28 32 34 37 45  xg2 26 30 37 42 47 38  xg3 27 29 31 36 45 46  xg4 25 30 32 38 41 45 № 77 1 2 3 4 5 6  xg1 25 27 30 35 42 50  xg2 27 29 32 37 42 48  xg3 22 29 34 36 46 45  xg4 20 29 34 41 45 49 28 № 78 1 2 3 4 5 6  xg1 15 17 19 23 27 32  xg2 18 20 25 30 35 27  xg3 17 19 24 27 32 35  xg4 15 20 23 25 30 32 № 79 1 2 3 4 5 6  xg1 12 18 21 28 35 39  xg2 13 17 22 25 30 36  xg3 9 15 18 23 25 30  xg4 13 18 22 27 34 36 № 80 1 2 3 4 5 6  xg1 10 13 17 24 28 35  xg2 9 13 16 20 26 30  xg3 12 16 20 24 27 29  xg4 15 17 22 26 30 34 Задания 81–90. Разработать оптимальную политику замены обо- рудования возраста пяти лет, исходя из условия максимизации ожи- даемой прибыли за плановый период продолжительности десяти лет. Известны стоимость продукции r (t) в усл. ед., производимой в течение года с использованием данного оборудования возраста t лет; ежегодные расходы u (t) в усл. ед., связанные с эксплуатацией этого оборудования; ликвидационная стоимость оборудования s в усл. ед., независящая от его возраста; стоимость p в усл. ед. нового оборудования (сюда же включены расходы, связанные с установ- кой, наладкой и запуском оборудования). Данные приведены в таб- лицах. 29 № 81 Возраст оборудования s p 0 1 2 3 4 5 6 7 8 9 10 r(t) 25 24 23 22 21 20 19 18 17 15 14 3 16 u(t) 4 5 6 7 8 9 10 11 12 13 14 № 82 Возраст оборудования s p 0 1 2 3 4 5 6 7 8 9 10 r(t) 40 39 39 37 37 36 35 34 34 32 30 9 25 u(t) 20 21 22 23 24 25 26 27 28 29 30 № 83 Возраст оборудования s p 0 1 2 3 4 5 6 7 8 9 10 r(t) 38 37 36 35 35 33 31 30 28 27 25 2 15 u(t) 15 15 16 17 18 20 20 21 23 24 25 № 84 Возраст оборудования s p 0 1 2 3 4 5 6 7 8 9 10 r(t) 36 35 35 33 32 30 28 26 26 25 24 3 20 u(t) 12 12 12 15 15 17 18 20 22 24 24 № 85 Возраст оборудования s p 0 1 2 3 4 5 6 7 8 9 10 r(t) 40 39 38 37 36 36 34 33 33 32 30 2 14 u(t) 20 20 22 23 24 25 26 27 28 29 30 30 № 86 Возраст оборудования s p 0 1 2 3 4 5 6 7 8 9 10 r(t) 21 20 19 18 17 16 15 14 13 12 11 1 10 u(t) 4 5 5 6 6 7 8 8 9 10 11 № 87 Возраст оборудования s p 0 1 2 3 4 5 6 7 8 9 10 r(t) 50 48 47 45 40 37 35 34 32 30 29 5 30 u(t) 17 18 20 22 23 24 26 28 28 29 29 № 88 Возраст оборудования s p 0 1 2 3 4 5 6 7 8 9 10 r(t) 26 25 24 23 22 21 20 20 18 18 16 3 16 u(t) 5 5 7 8 9 10 11 13 15 15 16 № 89 Возраст оборудования s p 0 1 2 3 4 5 6 7 8 9 10 r(t) 49 47 45 42 40 38 35 35 33 31 30 5 35 u(t) 10 12 14 16 18 20 23 24 25 27 30 № 90 Возраст оборудования s p 0 1 2 3 4 5 6 7 8 9 10 r(t) 42 42 40 38 37 35 34 34 33 30 30 5 21 u(t) 20 20 20 22 24 24 25 27 27 28 28 31 МЕТОДИЧЕСКИЕ УКАЗАНИЯ К КОНТРОЛЬНОЙ РАБОТЕ Решение задания типа 1–10 Решить графически задачу линейного программирования             .0,0,0 ,02 ,02 ,4 max22 321 21 21 321 321 xxx xx xx xxx xxxf Из первого уравнения выразим 2133 4: xxxx  . Так как 03 x , то первое ограничение равносильно неравенству 04 213  xxx или 421  xx . Исключим переменную 3x из це- левой функции:   8432282422 2121212121  xxxxxxxxxxf . Тогда задача линейного программирования принимает вид:    2 .0,0 ,02 ,02 ,4 1max843 21 21 21 21 21             xx xx xx xx xxf Здесь (1) – целевая функция, (2) – система ограничений. Эта за- дача содержит две переменные, и ее можно решить графически. 32 Для этого построим многоугольник допустимых планов, то есть множество точек плоскости 21Oxx , которые удовлетворяют системе ограничений (2). В неравенствах системы ограничений знаки неравенств заменим на знаки точных равенств и построим в системе координат 21Oxx соответствующие прямые:            ).(0),(0 )(,02 )(,02 )(,4 21 21 21 21 VxIVx IIIxx IIxx Ixx Эти прямые изображены на рис.1. Каждая из построенных пря- мых делит плоскость на две полуплоскости. Координаты точек од- ной полуплоскости удовлетворяют исходному неравенству, а дру- гой полуплоскости – нет. Чтобы определить искомую полуплос- кость, нужно взять какую-нибудь точку, принадлежащую одной из полуплоскостей, и проверить, удовлетворяют ли ее координаты данному неравенству. Если координаты взятой точки удовлетворя- ют данному неравенству, то искомой является та полуплоскость, которой принадлежит эта точка, в противном случае – другая полу- плоскость. Найдем, полуплоскость, определяемую неравенством 421  xx . Для этого построим прямую 421  xx ( на рис.1 это прямая (I)), возьмем, например, точку O(0;0). Координаты этой точки удовле- творяют неравенству: 400  . Значит полуплоскость, которой принадлежит точка O(0;0), определяется неравенством 421  xx . Это показано штрихами на рис. 1. Аналогично поступим с двумя другими неравенствами. 33 Рис. 1 Пересечение полученных таким образом полуплоскостей опре- деляет многоугольник допустимых планов. Как видно из рис. 1 – это треугольник ОАВ. Решить задачу линейного программирования графически – это значит найти точку многоугольника допустимых планов, в которой целевая функция принимает наибольшее значение. Чтобы найти эту точку построим линию уровня целевой функции cxx  21 43 , ко- торая пересекает многоугольник допустимых планов (с – некоторая постоянная). Линия уровня – это множество точек плоскости, в ко- торых функция принимает одно и то же значение с. Так как задача решается на максимум, то нам надо найти линию наивысшего уров- ня. Нормальный вектор линии уровня   gradfn  4;3 , то есть сов- падает с вектором gradf . Вектор gradf указывает направление наибыстрейшего возрастания функции f . Чтобы найти линию 34 наивысшего уровня, будем параллельно перемещать построенную линию в направлении gradf до ее крайней точки при пересечении с многоугольником допустимых планов. Такой точкой на рис.1 явля- ется точка А. В этой точке целевая функция принимает максималь- ное значение. Найдем координаты точки А как точки пересечения прямых (I) и (III), то есть решим систему уравнений:      .02 ,4 21 21 xx xx Получаем , 3 8 , 3 4 21   xx тогда максимальное значение целевой функции рав- но 3 20 8 3 8 4 3 4 3)(max  Aff . Находим 0 3 8 3 4 44 213   xxx . Ответ: . 3 20 max,0, 3 8 , 3 4        fx Замечание. Если задача решается на минимум, то надо найти точку многоугольника допустимых планов, в которой целевая функция принимает наименьшее значение, то есть построить линию наименьшего уровня. Для этого линию уровня параллельно пере- мещают в направлении gradf до ее крайней точки при пересече- нии с многоугольником допустимых планов. В этой точке целевая функция принимает минимальное значение. Решение задания типа 11–20 Предприятие ежемесячно имеет отходы (ресурсы) трех типов В1, В2, В3 объемы которых определяются величинами b1, b2, b3 (усл.ед.). Из этих отходов предприятие может организовать производство че- тырех видов изделий А1, А2, А3, А4, причем продукция может про- изводится в любых соотношениях (сбыт обеспечен). Расход ресур- сов i-го типа на производство единицы продукции j-го типа опреде- ляется величиной )4,1,3,1(  jiaij (усл.ед.) , а стоимость 35 единицы продукции j-го типа – величиной )4,1(, jc j (усл.руб.) . Значения jij ca , приведены в таблице: Расход сырья на производство единицы продукции Объем сырья bi А1 А2 А3 А4 А5 В1 2 2 3 3 2 3000 В2 0 1 1 2 3 600 В3 2 1 2 1 1 1800 Стоим. jc 3 2 5 4 3 Требуется: 1. Составить модель задачи определения ассортиментного плана производства, при котором расход ресурсов не превысит имеюще- гося количества, а суммарная стоимость произведенной продукции будет максимальной. 2. Привести полученную задачу линейного программирования к каноническому виду. Объяснить экономический смысл введенных балансовых переменных. 3. Найти симплекс-методом оптимальный ассортиментный план производства. Дать экономическую интерпретацию полученного результата. 4. Составить двойственную задачу для исходной. Оценить каж- дый из ресурсов, чтобы при заданных объемах ресурсов и величи- нах стоимости единицы продукции суммарная стоимость сырья бы- ла минимальной, а оценка ресурсов, необходимых для производства единицы продукции, была не меньше стоимости единицы продук- ции данного вида. 5. Определить меру дефицитности сырья и увеличение стоимо- сти продукции при изменении объема сырья на единицу. 6. Оценить целесообразность введения в план производства но- вого вида изделий А5, нормы затрат ресурсов на производство еди- ницы продукции и стоимость от реализации единицы продукции которого приведены в таблице. 36 Задание 1. Обозначим через jx объем производимой продукции Aj j-го типа )4,1( j . Тогда стоимость всей произведенной продук- ции будет определяться значением функции 4321 4523 xxxxf  , которая называется целевой функцией и по условию задачи должна стремиться к максимуму. На производство продукции расходуется сырье первого типа В1: 4321 3322 xxxx  , второго типа В2 – 432 2xxx  , третьего типа В3 – 4321 22 xxxx  , объемы которых не должны превышать запасы, соответственно, 3000, 600 и 1800 усл.ед., то есть должны выпол- няться условия:         .180022 ,6002 ,30003322 4321 432 4321 xxxx xxx xxxx Кроме этих ограничений, на переменные в экономических зада- чах, как правило, накладывается условие неотрицательности: 4,1,0  jx j Таким образом, математическая модель задачи будет иметь вид: max4523 4321  xxxxf (1)         .180022 ,6002 ,30003322 4321 432 4321 xxxx xxx xxxx (2) Задача (1)–(2) является задачей линейного программирования, записанной в симметрической форме. Задание 2. Чтобы решить задачу (1) - (2) симплекс-методом, ее необходимо привести к каноническому виду. Для этого введем пе- ременные: ),22(1800 ),2(600 ),3322(3000 43217 4326 43215 xxxxx xxxx xxxxx    которые называются балансовыми. Они определяют остаток сырья соответствующего типа после производства продукции из этого сы- 37 рья, и из ограничений (2) следует, что .0,0,0 765  xxx Введение балансовых переменных не изменяет целевую функцию (1), и зада- ча в канонической форме имеет вид: max4523 4321  xxxxf (3)            .7,1,0 ,180022 ,6002 ,30003322 74321 6432 54321 jx xxxxx xxxx xxxxx j (4) Задание 3. Решим задачу (3) - (4) симплекс методом. Перемен- ные 765 ,, xxx являются базисными переменными (БП). Каждая из этих переменных входит только в одно уравнение с коэффициентом «1» и не входит в целевую функцию, а переменные 4321 ,,, xxxx яв- ляются свободными переменными (СП). Запишем задачу в виде симплекс-таблицы: СП БП x1 x2 x3 x4 1 i x5 2 3 3 3 3000 1000 x6 0 1 1 2 600← 600 x7 2 1 2 1 1800 900 f -3 -2 -5 -4 0 ↑ В столбец базисных переменных (БП) записаны переменные x5, x6, x7 . В первую строку записаны свободные переменные x1, x2, x3, x4. В столбец с «1» в (столбец свободных членов) записаны пра- вые части уравнений ограничений. В последней строке (f-строке) записаны коэффициенты целевой функции с противоположными знаками. Внутри таблицы записаны элементы матрицы системы ограничений. Правый столбец i , носит вспомогательный характер, и его смысл будет выяснен ниже. Чтобы записать опорный план, задаваемый этой таблицей, необ- ходимо свободные переменные положить равными нулю: 38 x1=x2=x3=x4=0, а значения базисных переменных равны значениям, стоящим в столбце свободных членов: x5=3000, x6=600, x7=1800. Начальный опорный план имеет вид X0 = (0, 0, 0, 0, 3000, 600, 1800). Значение целевой функции на этом плане стоит в f-строке в столбце свободных членов f(X0)=0. Опорный план в задаче на максимум является оптимальным, ес- ли в f-строке все элементы, за исключением, быть может, элемента, стоящего в столбце свободных членов, неотрицательны. План Х° неоптимален, так как в f - строке имеются отрицательные элементы. От этого плана перейдем к другому опорному плану, более близ- кому к оптимальному. Для этого введем в базис новую переменную х3, соответствующую отрицательному элементу f-строки с наибольшей абсолютной величиной (этот элемент - «-5»). Столбец коэффициентов, в котором стоит переменная, включаемая в базис, называется разрешающим и помечается «стрелочкой» (в нашей за- даче это 3-й столбец). Чтобы решить вопрос о том, какую переменную следует вывести из базиса, находят симплексные отношения i , то есть отношения элементов столбца свободных членов к соответствующим положи- тельным элементам разрешающего столбца. Из симплексных отно- шений выбирают наименьшее. Оно и определяет разрешающую строку и переменную, которую выводят из базиса. Обычно сим- плексные отношения записывают справа на краю таблицы, а разре- шающую строку помечают «стрелочкой». В нашей задаче симплексные отношения 9002/1800,6001/600,10003/3000 321   и min(1000,600,900)=600, следовательно, разрешающей строкой явля- ется вторая. Переменную x6 выводим из базиса. Элемент, стоящий на пересечении разрешающей строки и раз- решающего столбца, называется разрешающим, и его выделяют в таблице. В нашей задаче это элемент a23 = 1, и он выделен «рамоч- кой». Перейдем к новой симплекс-таблице, в которой переменная, вы- водимая из базиса, меняется местами с переменной, вводимой в ба- зис, т. е. х6 и х3 меняются местами. Все остальные переменные остаются на прежних местах. 39 Элементы симплекс-таблицы при переходе к новому плану пере- считываются по правилам, которые называются симплексными пре- образованиями. Они заключаются в следующем: 1) разрешающий элемент заменяется обратной величиной; 2) элементы разрешающей строки, за исключением разрешаю- щего элемента, делятся на разрешающий элемент; 3) элементы разрешающего столбца, за исключением разреша- ющего элемента, делятся на разрешающий элемент и меняют знак; 4) все остальные элементы таблицы вычисляются по «правилу прямоугольника»: 00 0000 ji ijjijiij ij a aaaa a    ija – пересчитываемый элемент, 00 jia разрешающий элемент,  0ij a элемент, стоящий в i-й строке и разрешающем столбце, jia 0 элемент, стоящий в j-м столбце и разрешающей строке,   ija элемент новой таблицы, стоящий в i-й строке и j-м столбце. Используя эти правила, переходим к новой таблице. Все рас- четы приведем в таблице: СП БП x1 x2 x6 x4 1 40 x5 2 1 1 1312   3 1 3  3 1 2313   1200 1 600313000   x3 0 1 0  1 1 1  1 2 1 2  1 1 600  x7 2 1 1 2111   2 1 2  3 1 2211   600 1 600211800   f -3 3 1 1512   5 1 5    6 1 2514   3000 1 600510   Запишем эту таблицу, опустив вычисления: СП БП x1 x2 x6 x4 1 i x5 2 -1 -3 -3 1200 600 x3 0 1 1 2 600 – x7 2 -1 -2 -3 600 ← 300 f -3 3 5 6 3000 ↑ Получили новый план X1 = (0, 0, 600, 0, 1200, 0, 600), f(X1)=3000. План не является оптимальным, так как в f - строке имеется отрица- тельный элемент (он равен «-3»). Он единственный, поэтому пер- вый столбец будет разрешающим. Находим симплексные отноше- ния:  21 ,6002/1200  не существует, 3002/6003  и min(600,300)=300, следовательно, разрешающей строкой будет тре- тья, а разрешающий элемент a31=2. Переменную x1 выводим из ба- зиса, а переменную х7 вводим в базис. Переходим к новой таблице, элементы которой вычисляем по тем же правилам, что и в преды- дущей. 41 СП БП х7 x2 X6 x4 1 x5 -1 0 -1 0 600 x3 0 1 1 2 600 х1 1/2 -1/2 -1 -3/2 300 f 3/2 3/2 2 3/2 3900 Полученный план X* = (300, 0, 600, 0, 600, 0, 0) является опти- мальным, так как в f - строке все элементы неотрицательны. max f(X)= f(X*)=3900. Дадим полученному результату экономическую интерпретацию. Для того чтобы суммарная стоимость произведенной продукции была максимальной, необходимо из имеющегося сырья произвести 300 единиц изделий вида А1 (х1*=300), 600 единиц изделий вида А3 (х3*=600), изделия вида А2 и А4 не производить (х2*=х4*=0). Значе- ния х5*=600, х6*=х7*=0 показывают, что остаток сырья В1 равен 600усл.ед., а сырье В2 и В3 израсходовано полностью. Максималь- ная стоимость произведенной продукции равна 3900 усл.руб. (f(X*)=3900). Задание 4. Чтобы построить двойственную задачу к данной, обозначим через y1, y2, y3 стоимость единицы ресурсов В1, В2, В3, соответственно. Они должны принимать такие значения, чтобы суммарная оценка всех ресурсов F=3000y1+600y2+1800y3 , была ми- нимальной (чтобы не допустить необоснованного завышения оцен- ки ресурсов). Коэффициенты функции F – это правые части в си- стеме ограничений (2). Суммарная стоимость ресурсов, используемых для производства единицы продукции каждого вида, должна быть не меньше стоимо- сти этой произведенной единицы продукции, то есть 2у1+2у3 ≥ 3, 2у1+у2+у3 ≥ 2, 3у1+у2+2у3 ≥ 5, 3у1+2у2+у3 ≥ 4. На переменные накла- дывается условие неотрицательности: yi ≥ 0, 3,1i . Таким образом, математическая модель задачи будет иметь вид: F=3000y1+600y2+1800y3 → min (5) 42               .3,1,0 ,423 ,523 ,22 ,322 321 321 321 31 iy yyy yyy yyy yy i (6) Матрица системы (6) получается из матрицы систем (2) транспо- нированием, а правые части системы ограничений (6) равны коэф- фициентам целевой функции (1). Задача (5), (6) является двойственной для задачи (1)-(2). Чтобы установить соответствие между переменными прямой и двойствен- ной задач, необходимо двойственную задачу записать в канониче- ской форме: F=3000y1+600y2+1800y3 → min (7)               .7,1,0 ,423 ,523 ,22 ,322 7321 6321 5321 431 iy yyyy yyyy yyyy yyy i (8) Переменные у4, у5, у6, у7 показывают, на сколько стоимость сы- рья, из которого производится единица изделия вида А1, А2, А3, А4, соответственно, больше стоимости произведенного изделия. Задача (7)-(8) является двойственной для задачи (3)-(4), и между их переменными можно установить соответствие: 43 Решая одну из пары взаимодвойственных задач (3)-(4) или (7)- (8), можно записать решение другой задачи. Решение задачи (3)-(4) содержит последняя симплекс-таблица. Запишем ее с учетом уста- новленного соответствия между переменными прямой и двойствен- ной задач. СП БП у3 у5 у2 у7 F СП БП х7 x2 x6 x4 1 у1 x5 -1 0 -1 0 600 у6 x3 0 1 1 2 600 у4 х1 1/2 -1/2 -1 -3/2 300 f 3/2 3/2 2 3/2 3900 Из этой таблицы выписываем решение двойственной задачи: свободные переменные у1* = у6*= у4*= 0, значения базисных пере- менных расположены в f – строке: у3* = 3/2, у5* = 3/2, у2* = 2, у7* = 3/2, Fmin = F(Y*) = f(X*) = 3900. Оптимальный план двойственной задачи (7)-(8) имеет вид: Y* = (0, 2, 3/2, 0, 3/2, 0, 3/2). Задание 5. Полученные оценки у1* = 0, у2* = 2, у3* = 3/2 являются мерой дефицитности ресурсов. у1* = 0 означает, что ресурс типа В1 не является дефицитным. Он после производства продукции имеется в избытке (остаток В1 равен 600 усл.ед., определено в задании 3 х5*=600). При увеличении запа- сов сырья типа В1 на единицу максимальная стоимость произведен- ной продукции не изменится. Оценки у2* = 2, у3* = 3/2 отличны от нуля и указывают на дефи- цитность ресурсов типа В2 и В3. Эти ресурсы израсходованы полно- стью. При увеличении запасов сырья типа В2 на единицу макси- мальная стоимость произведенной продукции увеличится на вели- чину оценки у2* сырья В2, то есть на 2 усл.руб. При увеличении запасов сырья типа В3 на единицу максимальная стоимость произ- веденной продукции увеличится на величину оценки у3* сырья В3, то есть на 3/2 усл.руб. Сырье В2 поэтому считается более дефицит- ным, чем сырье В3. 44 Задание 6. Если в план производства включаются новые виды продукции, то оценка целесообразности их введения определяется по формуле     m i jiijj cya 1 , где ija – расход ресурсов i -го типа на про- изводство единицы изделия j-го типа, jc – стоимость единицы про- дукции j-го типа, iy – оптимальные двойственные оценки ресурса i -го типа. Если j < 0, то продукцию целесообразно вводить в план производства, так как стоимость сырья, идущего на производство единицы продукции, меньше стоимости единицы продукции. Если j ≥ 0, продукцию нецелесообразно вводить в план производства. В нашем задании Δ5 = 2∙0+3∙2+ (3/2)∙1-3=9/2 > 0. Это означает, что стоимость сырья, идущего на производство единицы продукции А5, больше стоимости единицы этойпродукции, поэтому продукцию А5 нецелесообразно вводить в план производства. Решение задания типа 21–30 Производственное объединение имеет в своем составе три фир- мы )3,1( iAi , которые производят однородную продукцию в объе- ме ia . Готовая продукция поставляется потребителям  3,1jB j , спрос которых определяется, соответственно, величинами jb . Из- вестны стоимость перевозки единицы продукции  3,1,3,1  jicij от поставщика )3,1( iAi потребителю  3,1jB j , которые приведе- ны в таблице: 1 B 2B 3B Запасы 45 ia 1A 4 3 5 70 К задаче2: 4,5,6 321  ccc 2A 3 4 3 80 К задаче 3: n=1, k=2 3A 4 5 5 50 К задаче 4: m=1, l=2, d=20 Спрос jb 40 80 50 К задаче 5: r=1, s=3, p=30 Задача 1. Составить математическую модель задачи определе- ния плана перевозки готовой продукции от поставщиков )3,1( iAi потребителям  4,1jB j , чтобы запасы поставщиков были вывезе- ны, спрос всех потребителей был удовлетворен, а суммарные транспортные издержки были минимальными. Методом потенциа- лов найти оптимальный план перевозки продукции от поставщиков к потребителям. Указать запасы оставшейся продукции у постав- щиков. Задача 2. Методом потенциалов найти оптимальный план пере- возки при дополнительном условии, что продукция пункта произ- водства )3,1( iAi , в котором себестоимость  3,1ici производимой продукции наименьшая, должна быть распределена полностью, а суммарные затраты, вызванные производством и доставкой про- дукции, были бы минимальными. Задача 3. Методом потенциалов найти оптимальный план пере- возки продукции при дополнительном условии, что перевозка от поставщика nA к потребителю kB запрещена. Задача 4. Методом потенциалов найти оптимальный план пере- возки продукции при дополнительном условии, что перевозка от поставщика mA к потребителю lB ограничена d единицами. Задача 5. Методом потенциалов найти оптимальный план пере- возки продукции при выполнении обязательной перевозки от по- ставщика rA к потребителю sB в объеме не менее p единиц. Во всех задачах вычислить величину наименьших суммарных затрат и сравнить с затратами начального плана перевозок. 46 Решение задачи 1. Для того чтобы спрос всех потребителей был удовлетворен, а запасы всех поставщиков были вывезены, необхо- димо и достаточно, чтобы сумма запасов равнялась сумме спроса, то есть      3 1 3 1i j ji ba . Такая транспортная задача называется задачей закрытого типа. В нашей задаче 70+80+50≠40+80+50: предложение (200 ед.) больше спроса (170 ед.) – задача открытого типа. Чтобы ее решить надо ввести фиктивного потребителя, спрос которого будет равен 200-170=30ед. Тарифы перевозок к фиктивному потребителю полагают равными нулю. Обозначим через 4,1,3,1,  jixij объемы перевозок от i-го по- ставщика iA к j –му потребителю jB . Целевой функцией задачи является функция, определяющая суммарные транспортные из- держки, и она равна .min554343534 333231232221131211  xxxxxxxxxf О граничениями задачи будут: а) объем продукции от поставщиков должен быть вывезен: ;50 ,80 ,70 34333231 24232221 14131211    xxxx xxxx xxxx б) спрос всех потребителей должен быть удовлетворен: ;30 ,50 ,80 ,40 342414 332313 322212 312111     xxx xxx xxx xxx в) обратные перевозки исключены: .4,1,3,1,0  jixij Целевая функция и ограничения составляют экономико- математическую модель транспортной задачи. Обычно транспортную задачу записывают в виде таблицы, в правых верхних углах клеток которой указывают тарифы перевозок, а в левых нижних – объем перевозимого груза по данному маршру- ту. Если по какому-нибудь маршруту груз не перевозится, то левый нижний угол соответствующей клетки остается пустым. Такая таб- 47 лица называется распределительной таблицей транспортной зада- чи. Построим начальный опорный план транспортной задачи мето- дом минимального элемента. Суть метода минимального элемента заключается в том, что максимально возможное количество груза перевозится по самым дешевым маршрутам. В нашей задаче такой маршрут (1,2), так как тариф по этому маршруту наименьший, он равен 3 усл.ед. Запасы А1 равны 70 ед., спрос В2 равен 80 ед., тогда по этому маршруту можно перевезти 70 единиц груза, т. е. 12x = min(70, 80) = 70. Все запасы А1 вывезены, и первая строка распределительной таблицы закрыта для заполнения. Из незаполненных клеток находим клетку с наименьшим тарифом. Такими клетками являются (2,1) и (2,3). Заполним (2,1): 21x = min(80,40) = 40. Спрос В1 удовлетворен, и пер- вый столбец закрыт для заполнения. Заполним (2,3): 23x = min(80- 40, 50) = 40. Все запасы А2 вывезены, и вторая строка закрыта для заполнения. Заполним клетки (3,2) и (3,3), которые имеют одинако- вый тариф равный 5: 32x =min(50,80-70)=10; 33x =min(50-10,50- 40)=10. В последнюю очередь заполняют клетки для фиктивного потребителя: 34x =min(50-20,30)=30. Таким образом, план составлен и имеет вид: 1B 2B 3B 4B Запасы ia 1A 4 3 70 5 0 70 2A 3 40 4 3 40 0 80 3A 4 5 10 5 10 0 30 50 Спрос jb 40 80 50 30 Клетки, в которых находятся отличные от нуля перевозки, назы- ваются занятыми, а остальные – свободными. Набор клеток распре- делительной таблицы, в которой две и только две соседние клетки 48 расположены в одной строке или в одном столбце, а первая и по- следняя клетки лежат либо в одной строке, либо в одном столбце, называется циклом. Графически цикл представляет собой замкну- тую ломаную линию, отрезки которой лежат либо в строке, либо в столбце. Для того чтобы построенный план был опорным, необходимо, чтобы он удовлетворял двум условиям: а) число занятых клеток должно быть не больше (m+n-1), где m – число поставщиков, n – число потребителей, б) из занятых клеток таблицы нельзя составить ни одного за- мкнутого цикла. Если занятых клеток ровно (m+n-1), то план называется невы- рожденным, если меньше – вырожденным.Построенный план в нашей задаче является опорным и невырожденным: число занятых клеток равно 3+4-1=6. Он имеет вид            10100 40040 0700 0X , а транс- портные издержки равны 550510510340340370)( 0 Xf (усл.руб.) Если при построении опорного плана занятых клеток будет меньше, чем (m+n-1), то в свободные клетки, соответствующие наименьшим тарифам, заносят нули так, чтобы занятых клеток бы- ло ровно (m+n-1), и из занятых клеток таблицы нельзя было соста- вить ни одного замкнутого цикла. Эти клетки с нулевыми перевоз- ками считаются занятыми. Оптимальный план перевозки продукции найдем методом по- тенциалов. С помощью этого метода от одного плана переходят к другому, на котором значение целевой функции не больше, чем на предыдущем, и так до тех пор. пока не получат оптимальный план. Введем понятие потенциалов. Числа ui, i = 1,2,3, и vj, j= 1,2,3,4, называются потенциалами поставщиков и потребителей, соответ- ственно, если для каждой занятой клетки сумма потенциалов равня- ется тарифу клетки. Потенциалы обычно записывают на краю таб- лицы. 49 В нашей задаче для определения потенциалов получаем систему уравнений: u1+v2=3, u2+v1=3, u2+v3=3, u3+v2=5,u3+v3=5, u3+v4=0. в которой (m+n) неизвестных и (m+n-1) уравнений (столько занятых клеток). Эта система имеет бесконечное множество решений, любое из которых составит систему потенциалов. Чтобы найти одно из решений, определяют один из потенциалов, например, u3=0 и вы- числяют остальные потенциалы: v2=5, v3=5, v4=0, u1=-2, u2=-2, v1=5. Результаты записывают в распределительной таблице: 1B 2B 3B 4B ui 1A 4 3 70 0 -2 2A – 3 40 4 + 3 80 0 -2 3A 4 + 5 10 5 10 – 0 30 0 vj 5 5 5 0 План является оптимальным, если для всех свободных клеток сумма потенциалов не меньше тарифа этой клетки, т. е. ui+vj cij. Следовательно, чтобы проверить план на оптимальность, вычисля- ют оценки (косвенные тарифы) свободных клеток: sij=cij- (ui+vj). Если sij 0, то план оптимален, если хотя бы одна оценка sij < 0, то план не оптимален и его можно улучшить. Проверим построенный план нашей задачи на оптимальность. Вычислим оценки свободных клеток: s11=4-(5-2)=1, s13=5-(5-2)=2, s14=0-(0-2)=2, s22=4-(5-2)=1, s24=0-(0-2)=2, s31=4-(5+0)=-1. Так как среди оценок есть отрицательная: s31< 0, то план не оп- тимален и его можно улучшить. Выполняют это следующим обра- зом. а) Находят клетку с наибольшей по модулю отрицательной оцен- кой. Такая клетка называется перспективной. В нашей задаче – это клетка (3,1). Если таких клеток несколько, то в качестве «перспективной» выбирают ту из них, которая имеет наимень- ший тариф. б) Для перспективной клетки и части занятых клеток строят за- мкнутый цикл. В нашей задаче: (3,1) → (3,3) → (2,3) → (2,1). 50 Вершины этого цикла помечают чередующимися знаками «+» и «−», начиная с перспективной клетки (3,1), в которой ставится знак «+». Построенный цикл обозначен на предыдущей таблице. в) Вычисляют объем перераспределяемого груза Δ, который равен минимальному из объемов, стоящих в клетках, помеченных знаком «—». В нашей задаче: Δ= min(40, 10) = 10. г) Строят новый план. Для этого в клетках, помеченных знаком «+», объем перераспределяемого груза Δ прибавляют, а в клет- ках, помеченных знаком «–», объем перераспределяемого груза Δ вычитают, остальные объемы перевозок остаются без измене- ния. Перспективная клетка (3,1) становится занятой, а клетку, в которой получается «нулевая» перевозка, делают свободной. Замечание. Если таких клеток несколько, то свободной делают ту из них, которая имеет наибольший тариф. Построенный новый план должен содержать ровно (m+n-1) занятых клеток. Полученный план запишем в таблицу: 1B 2B 3B 4B ui 1A 4 3 70 5 0 -2 2A 3 30 4 3 50 0 -1 3A 4 10 5 10 5 0 30 0 vj 4 5 4 0 Проверяем его на оптимальность. Составляем систему уравне- ний для определения потенциалов поставщиков и потребителей: u1+v2=3, u2+v1=3, u2+v3=3, u3+v1=4, u3+v2=5, u3+v4=0. Полагаем u3=0 и вычисляем остальные потенциалы: v1=4, v2 = 5, v4=0, u2=-l, u1=-2, v3=-1. Вычисляем оценки свободных клеток: s11=4-(4-2)=2, s13=5-(4- 2)=3, s14=0-(0-2)=2, s22=4-(5-1)=0, s24=0-0-1)=1, s23=5-(4+0)=1. 51 Так как все оценки неотрицательны, то полученный план являет- ся оптимальным. Он имеет вид            01010 50030 0700 X . У поставщика А3 останется 30 единиц груза (тот объем, который он поставляет фиктивному потребителю В4). Транспортные издержки оптималь- ного плана: 540510410350330370)( Xf (усл.руб.), что на 10(усл.руб.) меньше по сравнению с начальным планом 0X . Решение задачи 2. В нашей задаче для А1 себестоимость произ- водимой продукции равна c1=5, для А2 – c2=6, для А3 – c3=4. Для учета себестоимости к элементам матрицы тарифов прибавляем се- бестоимость производимой продукции. Для того чтобы продукцию от поставщика А3 полностью вывезти (так как у него себестоимость наименьшая) запретим его перевозку к фиктивному потребителю, для этого тариф перевозки определим равным сколь угодно боль- шому числу М>0, то есть c34=М. Тогда распределительная таблица транспортной задачи примет вид: 1B 2B 3B 4B Запасы ia 1A 4+5=9 3+5=8 5+5=10 0+5=5 70 2A 3+6=9 4+6=10 3+6=9 0+6=6 80 3A 4+4=8 5+4=9 5+4=9 0+М=М 50 Спрос jb 40 80 50 30 Построим начальный опорный план транспортной задачи ме- тодом минимального элемента (расчеты выполняются аналогично расчетам задачи1) и результаты запишем в распределительную таб- лицу. Число занятых клеток равно 5<(m+n-1)=6, то есть построен- ный план является вырожденным. Чтобы найти потенциалы по- ставщиков и потребителей число занятых клеток должно быть рав- 52 но 6, для этого в одну из клеток (в нашем случае это клетка (3,3)) ставят нулевую перевозку и ее считают занятой. Вычисляем потенциалы поставщиков и потребителей из си- стемы уравнений: u1+v2=8, u2+v3=9, u2+v4=6, u3+v1=8, u3+v2=9, u3+v3=9 и запишем их на краях таблицы: 1B 2B 3B 4B Запасы ia ui 1A 9 8 70 10 5 70 -1 2A 9 10 9 50 6 30 80 0 3A 8 40 9 10 9 0 М 50 0 Спрос jb 40 80 50 30 vj 8 9 9 0 Вычисляем оценки свободных клеток: s11=9-(8-1)=2, s13=10-(9- 1)=2, s14=5-(0-1)=6, s21=9-(8+0)=1, s22=10-(9+0)=1, s24=М-(0+0)=М. Так как все оценки положительны, то полученный план является оптимальным. Он имеет вид            01040 5000 0700 X . У поставщика А2 останется 30 единиц груза (тот объем, который он поставляет фик- тивному потребителю В4). Суммарные затраты, вызванные произ- водством и доставкой продукции, для оптимального плана мини- мальны и равны: 1420910840950870)( Xf (усл. руб.). Решение задачи 3. В задаче перевозка от поставщика А1 к по- требителю В2 запрещена, поэтому тариф перевозки в клетке (1,2) полагают равным М>0, где М – сколь угодно большое число. По- строим начальный опорный план транспортной задачи методом ми- нимального элемента (расчеты выполняются аналогично расчетам задачи 1). Чтобы найти потенциалы поставщиков и потребителей 53 число занятых клеток должно быть равно (m+n-1)=6, для этого в одну из клеток (в нашем случае это клетка (1,4)) ставят нулевую перевозку и ее считают занятой. Результаты запишем в распреде- лительную таблицу. Вычисляем потенциалы поставщиков и потре- бителей из системы уравнений: u1+v1=4, u1+v2=М, u1+v4=0, u2+v3=3, u2+v4=0, u3+v2=5 и запишем их на краях таблицы: 1B 2B 3B 4B ui 1A 4 40 − М 30 5 + 0 0 2A 3 4 + 3 50 0 30 − 0 3A 4 5 50 5 0 5-М vj 4 М 3 0 Вычисляем оценки свободных клеток: s13=5-(3+0)=2, s21=3- (4+0)=-1<0, S22=4-(M+0)=4-M<0, s31=4-(4+5-M)=M-5>0, s33=5-(3+5- M)=M-3>0, s34=0-(0+5-M)=M-5>0. Так как среди оценок есть отри- цательные: s21< 0, s22<0, то план не оптимален. Перспективной явля- ется клетка с наибольшей по модулю отрицательной оценкой, В нашей задаче это клетка (2,2). С этой клеткой строят замкнутый цикл и вершины этого цикла помечают чередующимися знаками «+» и «-». Построенный цикл обозначен отрезками прямых на предыдущей таблице. Вычисляем объем перераспределяемого груза Δ=min (30,30)=30. Строим новый план (расчеты выполняются аналогично расчетам задачи 1). В клетках (1,2) и (2,4), помеченных знаком «—», получа- ются нулевые перевозки. Одну из этих клеток делают свободной (причем ту, которая имеет наибольший тариф), а в другой записы- вают нулевую перевозку и ее считают занятой. В нашей задаче клетка (1,2) – свободная, а в клетке (2,4) – нулевая перевозка. По- строенный план записываем в новой таблице. Вычисляем потенциа- лы поставщиков и потребителей из системы уравнений: u1+v1=4, u1+v4=0, u2+v2=4, u2+v3=3, u2+v4=0, u3+v2=5 и запишем их на краях таблицы: 54 1B 2B 3B 4B ui 1A 4 40 М 5 0 30 0 2A 3 + 4 30 3 50 – 0 0 0 3A 4 5 50 – 5 0 + 1 vj 4 4 3 0 Вычисляем оценки свободных клеток: s12=М-(4+0)=М-4>0, s13=5- (3+0)=2, S21=3-(4+0)=-1, s31=4-(4+1)=-1, s33=5-(3+1)=1, s34=0-(0+1)=- 1. Так как среди оценок есть отрицательные: s21< 0, s31<0, s34<0, то план не оптимален. Три клетки (2,1), (3,1) и (3,4) имеют одинако- вую отрицательную оценку. В качестве перспективной выбираем клетку (3,4) (так как у нее наименьший тариф из этих трех клеток), с ней строим замкнутый цикл, обозначенный на предыдущей таб- лице. Вычисляем объем перераспределяемого груза Δ=min (0,50)=0. Строим новый план, вычисляем потенциалы поставщиков и потре- бителей и записываем в новой таблице: 1B 2B 3B 4B ui 1A 4 40 М 5 0 30 0 2A 3 4 30 3 50 0 -1 3A 4 5 50 5 0 0 0 vj 4 5 4 0 Вычисляем оценки свободных клеток: s12=М-(5+0)=М-5>0, s13=5- (4+0)=1, S21=3-(4-1)=0, s31=4-(4+0)=0, s33=5-(4+0)=1, s24=0-(0- 1)=1.Так как все оценки неотрицательны, то полученный план явля- ется оптимальным. Он имеет вид            0500 50300 0040 X . У поставщика 55 А1 останется 30 единиц груза (тот объем, который он поставляет фиктивному потребителю В4). Транспортные издержки оптималь- ного плана: 680550410350430440)( Xf (усл.руб.), что на 140(усл.руб.) больше по сравнению с оптимальным планом в задаче без ограничений. Решение задачи 4. В задаче перевозка от поставщика А1 к по- требителю В2 ограничена 20-ю единицами. Для решения этой зада- чи потребителя В2 представляют в виде двух составляющих В2' и В2''. Спрос В2' считают равным 20 единицам, а спрос В2'' – 80-20=60 единицам, Тариф перевозки от поставщика А1 к потребителю В2' полагают таким же как и тариф к потребителю В2, а перевозку от А1 к В2'' запрещают, то есть тариф от А1 к В2'' равен М>0, где М – сколь угодно большое число. Тарифы от поставщиков А2 и А3 к потреби- телям В2' и В2'' такие же, как и к потребителю В2. Построим началь- ный опорный план транспортной задачи методом минимального элемента и вычислим потенциалы поставщиков и потребителей (расчеты выполняются аналогично расчетам предыдущих задач). Результаты запишем в таблицу: В1 В2' В2'' В3 В4 ia ui А1 4 3 20 – М 10 + 5 10 0 30 70 0 А2 3 40 4 4 + 3 40 – 0 80 -2 А3 4 5 5 50 5 0 50 5- М jb 40 20 60 50 30 vj 5 3 М 5 0 Среди свободных клеток отрицательные оценки имеют s11 = 4 – (5 + 0) = –1 и s12'' = 4 – (M – 2) = 6 – M, поэтому план не яв- ляется оптимальным и перспективной клеткой является (1,2''), так как ее оценка наибольшея по модулю среди отрицательных. С этой клеткой строим замкнутый цикл и вершины этого цикла помечаем чередующимися знаками «+» и «-» (он обозначен на предыдущей 56 таблице). Вычисляем объем перераспределяемого груза Δ=min (10,40)=10. Строим новый план, вычисляем потенциалы поставщи- ков и потребителей и записываем в новой таблице: В1 В2' В2'' В3 В4 ui А1 + 4 3 20 М – 5 20 0 30 0 А2 3 40 – 4 4 10 3 30 + 0 -2 А3 4 5 5 50 5 0 -1 vj 5 3 6 5 0 Среди свободных клеток отрицательную оценку имеет s11 = 4 – (5 + 0) = –1, поэтому план не является оптимальным и пер- спективной клеткой является (1,1). С этой клеткой строим замкну- тый цикл, обозначенный на предыдущей таблице. Вычисляем объем перераспределяемого груза Δ=min (20,40)=20. Строим новый план, вычисляем потенциалы поставщиков и потребителей и записываем в новой таблице: В1 В2' В2'' В3 В4 ui А1 4 20 3 20 М 5 0 30 0 А2 3 20 4 4 10 3 50 0 -1 А3 4 5 5 50 5 0 0 vj 4 3 5 4 0 Так как все оценки свободных клеток неотрицательны, то полу- ченный план является оптимальным. Объединяя перевозки к потре- бителям В2' и В2'', получаем план            0500 501020 02020 X . У поставщика А1 останется 30единиц груза (тот объем, который он поставляет 57 фиктивному потребителю В4). Транспортные издержки оптималь- ногопла- на: 640350550410320320420)( Xf (усл.руб.), что на 100 (усл.руб.) больше по сравнению с оптимальным планом в задаче без ограничений. Решение задачи 5. В задаче требуется выполнить обязательную перевозку от поставщика А1 к потребителю В3 в объеме не менее 30 единиц. Предполагается, что такая перевозка в объеме 30 единиц выполнена, поэтому у поставщика А1 осталось 40 единиц груза, а потребителю В3 осталось получить еще 20 единиц груза. Построим начальный опорный план транспортной задачи методом минималь- ного элемента и вычислим потенциалы поставщиков и потребите- лей (расчеты выполняются аналогично расчетам предыдущих за- дач). Результаты запишем в таблицу: В1 В2 В3 В4 Запасы ia ui А1 4 3 40 5 0 40 -2 А2 3 40 + 4 3 20 – 0 20 80 0 А3 4 5 40 – 5 0 10 + 50 0 Спрос jb 40 80 20 30 vj 3 5 3 0 Среди свободных клеток отрицательную оценку имеет s22 = 4 – – (5 + 0) = –1, поэтому план не является оптимальным и перспек- тивной клеткой является (2,2). С этой клеткой строим замкнутый цикл, обозначенный на предыдущей таблице. Вычисляем объем пе- рераспределяемого груза Δ=min (20,40)=20. Строим новый план, вычисляем потенциалы поставщиков и потребителей и записываем в новой таблице: 58 В1 В2 В3 В4 ui А1 4 3 40 5 0 -1 А2 3 40 4 20 3 20 0 0 А3 4 5 20 5 0 30 1 vj 3 4 3 -1 Так как все оценки свободных клеток неотрицательны, то полу- ченный план является оптимальным. Учитывая перевозку от по- ставщикаА1 к потребителю В3 в объеме 30 единиц, получаем план            0200 202040 30400 X . У поставщика А3 останется 30единиц груза. Транспортные издержки оптимального плана: 630520320420340530340)( Xf (усл.руб.), что на 90(усл.руб.) больше по сравнению с оптимальным планом в за- даче без ограничений. Решение задания типа 31–40 Две отрасли А и В могут вкладывать денежные средства в строи- тельство четырех объектов, причем отрасль А располагает a = 70 млн.усл.руб., а отрасль В – b= 56 млн.усл.руб. С учетом особенно- стей вкладов и местных условий прибыль отрасли А в зависимости от объема финансирования выражается элементами матрицы              131082 7671 4345 8967 С . Будем предполагать, что убыток отрасли В при этом равен прибыли отрасли А. Требуется: 1. Выявить игроков и описать их стратегии. 2. Проверить, имеет ли игра решение в чистых стратегиях. 59 3. Составить экономико-математическую модель данной кон- фликтной ситуации для каждого игрока. 4. Найти оптимальные стратегии отраслей. 5. На основании полученного результата распределить денежные средства между объектами. Задание 1. Отрасль А будем считать игроком А, и его чистыми стратегиями будут: 1А – отрасль А вкладывает в строительство пер- вого объекта 1а млн. усл.руб., 2А – отрасль А вкладывает в строи- тельство второго объекта 2а млн.усл.руб., 3А – отрасль А вклады- вает в строительство третьего объекта 3а млн.усл.руб., 4А – от- расль А вкладывает в строительство четвертого объекта 4а млн. усл. руб., при этом 1а + 2а + 3а + 4а = а = 70 (млн. усл. руб.). Отрасль В будем считать игроком В, и его чистыми стратегиями будут: 1B отрасль В вкладывает в строительство первого объекта 1b млн.усл.руб., 2B отрасль В вкладывает в строительство второго объекта 2b млн.усл.руб., 3B отрасль В вкладывает в строительство третьего объекта 3b млн.усл.руб., 4B отрасль В вкладывает в стро- ительство четвертого объекта 4b млн.усл. руб., при этом 1b + 2b + 3b + 4b = b = 56 (млн.усл.руб.). Задание 2. Матричная игра двух лиц имеет решение в чистых стратегиях, когда нижняя чистая цена игры  равна верхней чистой цене игры  . По определению i i  max , где ij j i cmin , j j  min , где ij i j cmax , ijc – элементы платежной матрицы игры. Вычислим нижнюю чистую цену игры  : 1 = min (7, 6, 9, 8) = 6, 2 = min (5, 4, 3, 4) = 3, 3 =min (1, 7, 6, 7) = 1, 4 = min (2, 8, 10, 13) = 2,  = mаx (6, 3,1, 2) = 6. Вычислим верхнюю чистую цену игры  : 1 = max (7, 5,1, 2) = 7, 2 = max (6, 4, 7, 8) = 8, 3 = max (9, 3, 6, 10) = 10, 4 =max (8, 4, 7,13) = 13,  = min (7, 8, 10 13) = 7. 60 Обычно платежную матрицу игры записывают в виде таблицы, а значения i и j на краях таблицы: jB iA 1B 2B 3B 4B i 1А 7 6 9 8 6 2А 5 4 3 4 3 3А 1 7 6 7 1 4А 2 8 10 13 2 j 7 8 10 13  =6  =7 Так как  76,   , то игра не имеет решение в чистых стра- тегиях. Однако любая матричная игра имеет решение в смешанных стратегиях. Чтобы найти это решение, удобно матрицу игры пред- варительно упростить. Задание 3. Стратегию kА для игрока А называют доминирующей над стратегией sА , если sjkj cc  для всех j, при этом стратегию sА называют доминируемой. В нашем примере стратегия 1А доминирует над стратегией 2А :7>5, 6>4, 9>3, 8>4, стратегия 4А доминирует над стратегией 3А :2>1, 8>7, 10>6, 13>7. Стратегии 2А и 3А являются доминируемыми. В связи с этим, опустив вторую и третью строки матрицы игры, получим матрицу . 13 8 10 9 8 6 2 7       Стратегию lB для игрока В называют доминирующей над страте- гией rB , если iril cc  для всех i, при этом стратегию rB называют доминируемой. В нашем примере стратегия 2B доминирует над стратегиями 3B (6<9, 8<10) и 4B (6<8, 8<13). Стратегии 3B и 4B являются доми- нируемыми. 61 Вероятности выбора игроками доминируемых стратегий равны нулю, поэтому из матрицы игры можно вычеркнуть строки и столб- цы, соответствующие доминируемым стратегиям, и перейти к игре меньшей размерности. Если  4321 ,,, ppppp  смешанная стратегия игрока А, то в нашем примере 032  pp ( 2А и 3А доминируемые), и из мат- рицы игры вычеркиваем вторую и третью строки. Аналогич- но, если  4321 ,,, qqqqq  смешанная стратегия игрока В, то 043  qq ( 3B и 4B доминируемые), и из матрицы игры вы- черкиваем третий и четвертый столбцы. В результате этих преобразований мы перешли к игре, матрица которой имеет вид        82 67 С , Смешанные стратегии игрока pA  =  41, pp , игрока  21,qqqB  , цена v этой игры совпадает с ценой v первона- чальной игры, v= v . Задание 4. Для того, чтобы стратегия  21,qqq  игрока В бы- ла оптимальной, необходимо и достаточно, чтобы выполнялось условие    2 1 , j jij vqa 4,1i , где v цена игры. Разделив это неравенство на v , 0v , получаем    2 1 ,1 j j ij v q a 4,1i . Если обозначить , v q x ii  2,1j , то неравенство принимает вид    2 1 ,1 j jij xa 4,1i . Очевидно, что ,0ix 2,1j . Составим функцию   v qq vv q v q xxf 11 21 21 21  , 62 так как    2 1 1 j jq по определению смешанной стратегии. Игрок В стремится свой выигрыш минимизировать, поэтому max 1 21  v xxf . Объединяя эти результаты, получаем экономико- математическую модель для игрока В: max21  xxf , (1)         .0, ,182 ,167 21 21 21 xx xx xx (2) Аналогично для игрока А. стратегия  41, ppp  будет опти- мальной тогда и только тогда, когда    4,1 , i iij vpa 2,1j . Разделив это неравенство на v , 0v , получаем    4,1 ,1 i i ij v p a 2,1j . Если обозначить , v q y ii  4,1i , то неравенство принимает вид    4,1 ,1 i iij ya 2,1j , ,0iy 4,1i . Составим функцию   v pp vv p v p yyF 11 41 41 41  , так как    4,1 1 i ip по определению смешанной стратегии. Игрок А стремится свой выигрыш максимизировать, поэтому min 1 41  v yyF . Объединяя эти результаты, получаем экономико- математическую модель для игрока А: min41  yyF (3) 63         .0, ,186 ,127 41 41 41 yy yy yy (4) Задачи (1), (2) и (3), (4) являются парой взаимодвойственных за- дач линейного программирования. Решив одну из них, запишем ре- шение другой. Задание 5. Для того. чтобы решить задачу (1), (2), приведем ее к каноническому виду: max21  xxf ,          .4,1,0 ,182 ,167 421 321 jx xxx xxx j Решим эту задачу симплекс-методом. Решение задач линейного программирования симплекс-методом было разобрано при выпол- нении задания типа 11–20, поэтому выполняя стандартные действия приведем здесь только последовательность симплекс-таблиц, кото- рая представляет решение задачи. СП БП 1 x 2x 1 i 3x 7 6 1  1/7 4x 2 8 1 1/2 f –1 – 1 0  СП БП 3 x 2x 1 i 1x 1/7 6/7 1/7 1/6 4x –2/7 44/7 5/7  5/44 f 1/7 – 1/7 1/7  64 СП БП 3x 4x 1 1x 2/11 –3/22 1/22 2x -1/22 7/44 5/44 f 3/22 1/44 7/44 Все элементы f-строки положительны, поэтому план оптимален и имеет вид:   44/7,44/5,22/1 max21   xffxx . Тогда цена игры 7 441 max  f v , а 7 5 7 44 44 5 , 7 2 7 44 22 1 2211   vxqvxq . ,0,0 43   qq так как стратегии 3B и 4B для игрока В были доминируемыми. Таким образом, оптимальная смешанная стратегия игрока В имеет вид        0,0, 7 5 , 7 2 q , а цена игры 7 44 v . Чтобы записать решение двойственной задачи (3), (4), приведем ее к каноническому виду: min41  yyF         .4,1,0 ,186 ,127 341 241 iy yyy yyy i Установим соответствие между переменными прямой и двой- ственной задач:    CП БП yy xx 32 21    БП СП yy xx 41 43 Запишем симплекс-таблицу, содержащую оптимальный план, с учетом этого соответствия: 65 БП 1y 4y F СП СП БП 3 x 4x 1 2y 1x 2/11 –3/22 1/22 3y 2x –1/22 7/44 5/44 1 f 3/22 1/44 7/44 Отсюда 44 7 , 44 1 , 22 3 min41   Fyy . Тогда 7 1 7 44 44 1 , 7 6 7 44 22 3 , 7 44 4411   vypvypv . 032   pp , так как стратегии 32 ,AA для игрока А являются доминируемыми. Оптимальная смешанная стратегия игрока А име- ет вид        7 1 ,0,0, 7 6 p , цена игры 7 44 v . Задание 6. Зная оптимальные стратегии игроков, денежные средства необходимо распределить следующим образом. Отрасль А: вкладывает в строительство первого объекта – 60 7 6 7011  paa (млн.усл.руб.); четвертого объекта – 60 7 1 7044  paa (млн.усл.руб.); второго и третьего – 032  aa (млн.усл.руб.), так как 032   pp . Отрасль В: вкладывает в строительство первого объекта – 16 7 2 5611  qbb (млн.усл.руб.); второго объекта – 40 7 5 5642  qbb (млн.усл.руб.); третьего и четвертого– 043  bb (млн.усл.руб.), так как 043   qq . 66 Решение задания типа 41–50 Объем реализации товара Т за рассматриваемый период времени колеблется в зависимости от уровня покупательского спроса в пре- делах от 5 до 8 тыс. ед. Прибыль торгового предприятия от единицы реализованного товара Т равна 6 ден.ед. Если запасенного товара окажется недостаточно для полного удовлетворения спроса, можно заказать дополнительное количество товара, что потребует новых затрат на доставку в размере 3 ден.ед. в расчете на единицу товара. Если же запасенный товар полностью реализовать не удастся, то расходы на содержание и хранение остатка составят 2 ден.ед. в расчете на единицу товара. Предполагается, что дополнительно за- казанный товар полностью реализуется за тот же рассматриваемый период времени. Требуется: 1. Придать описанной производственной ситуации игровую схе- му, выявить игроков и описать их стратегии. 2. Составить платежную матрицу игры. 3. Дать рекомендации об оптимальном уровне запаса товара на торговом предприятии, обеспечивающем ему наивысшую эффек- тивность работы с учетом торговой прибыли и возможных допол- нительных затрат на заказ и доставку товара, содержание и хране- ние остатка, если а) известны вероятности уровней покупательского спроса, и они, соответственно, равны 0,2; 0,4; 0,3; 0,1. б) известно, что все уровни покупательского спроса равнове- роятны; в) никакой дополнительной информации об уровнях покупа- тельского спроса нет (для нахождения оптимальной стратегии при- менить критерии Вальда, Сэвиджа, Гурвица ). Постоянная λ=0,7. Задание 1. Участниками данной конфликтной ситуации являются торговое предприятие и рынок, который определяет спрос на данную продукцию. Торговое предприятие свои стратегии выбирает осо- знанно и такого игрока называют статистиком и обозначают А. Рынок влияет на результат игры, но спрос на продукцию формирует- ся стихийно, такого игрока называют «природой» и обозначают П. Природа П может находиться в одном из своих состояний: П1 – спрос на товар равен 5 тыс.ед.; П2 – спрос на товар равен 6 тыс.ед.; 67 П3 – спрос на товар равен 7 тыс.ед.; П4 – спрос на товар равен 8 тыс.ед. Торговое предприятие (игрок А) может использовать одну из своих чистых стратегий: А1 – взять на реализацию 5 тыс.ед.; А2 – взять на реализацию 6 тыс.ед.; А3 – взять на реализацию 7 тыс.ед.; А4 – взять на реализацию 8 тыс.ед. Задание 2. Платежная матрица игры – это матрица, элементы которой ija определяют величину выигрыша игрока А, если он вы- брал свою стратегию Аi , а природа находилась в состоянии Пj. Вы- числим элементы этой матрицы. Если игрок А (торговое предприятие) выбрал свою стратегию А1 (взял на реализацию 5 тыс.ед.) и природа находилась в состоянии П1 (спрос на товар равен 5 тыс.ед.), то он реализует 5 тыс.ед. и величи- на прибыли игрока А будет равна 306511 a . Если игрок А вы- брал свою стратегию А1 и природа находилась в состоянии П2 (спрос на товар равен 6 тыс.ед.), то торговое предприятие закажет дополнительно 1 тыс.ед. товара и реализует 6 тыс.ед., но заплатит 3 ден.ед. за доставку 1 тыс.ед. Величина прибыли игрока А в этом случае будет равна 33316612 a . Если игрок А выбрал свою стратегию А2 (взял на реализацию 6 тыс.ед.) и природа находилась в состоянии П1 (спрос на товар равен 5 тыс.ед.), то торговое пред- приятие реализует только 5 тыс.ед. и будет платить 2 ден.ед. за хра- нение 1 тыс.ед. товара. Величина прибыли игрока А в этом случае будет равна 28216521 a . Аналогично вычисляем осталь- ные элементы платежной матрицы и записываем в таблицу: П1 П2 П3 П4 А1 3065  333166  363267  393368  А2 282165  3666  393167  423268  А3 262265  342166  4267  453168  А4 242365  322266  402167  4868  68 Задание 3а). Если известны вероятности уровней покупатель- ского спроса, то для определения оптимальной стратегии торгового предприятия используют критерий Байеса. Оптимальной по-Байесу является стратегия, на которой достига- ется максимальная средняя прибыль равная 4,1, 4 1     iqaa j jiji , где jq - это вероятности уровней покупательского спроса, и они, соответственно, равны 0,2; 0,4; 0,3; 0,1. Результаты вычислений за- пишем в таблице: П1 П2 П3 П4 Средняя прибыль  ia А1 30 33 36 39 9,33 1,0393,0364,0332,0301    a А2 28 36 39 42 9,35 1,0423,0394,0362,0282    a А3 26 34 42 45 4,35 1,0453,0414,0342,0253    a А4 24 32 40 48 4,34 1,0483,0404,0322,0244    a jq 0,2 0,4 0,3 0,1 Вычислим   9,354,34;4,35;9,35;9,33maxmax   ia . Это равен- ство достигается на А2, следовательно, стратегия А2 является опти- мальной по-Байесу. Это значит, что торговое предприятие должно взять на реализацию 6 тыс.ед. и ожидаемое среднее значение при- были будет равно 35,9 тыс.ден.ед. Задание 3б). Если известно, что все уровни покупательского спроса равновероятны, то для определения оптимальной стратегии торгового предприятия используют критерий Лапласа. 69 Оптимальной по-Лапласу является стратегия, на которой дости- гается максимальная средняя прибыль равная 4,1, 4 1     iqaa j jiji , где jq - вероятности уровней покупательского спроса. Так как ве- роятности все равны, то 25,0jq . Результаты вычислений запи- шем в таблице: П1 П2 П3 П4 Средняя прибыль  ia А1 30 33 36 39 5,34)39363330(25,01   a А2 28 36 39 42 25,36)42393628(25,02   a А3 26 34 42 45 25,36)45413425(25,03   a А4 24 32 4 0 48 36)48403224(25,04   a Вычислим   25,3636;25,36;25,36;5,34maxmax   ia . Это ра- венство достигается на А2 и А3, следовательно, стратегии А2 и А3 являются оптимальными по-Лапласу. Это значит, что торговое предприятие должно взять на реализацию 6 тыс.ед. или 7 тыс.ед. и ожидаемое среднее значение прибыли будет равно 36,25 тыс.ден.ед. Задание 3в). Если никакой дополнительной информации об уровнях покупательского спроса нет, то для нахождения оптималь- ной стратегии применяют критерии или Вальда, или Сэвиджа, или Гурвица. Оптимальной по-Вальду является стратегия, на которой достига- ется максимальная прибыль при наихудшем состоянии природы, то есть стратегия, на которой выполняется равенство: i i  max , где ij j i amin . 70 Результаты вычислений запишем в таблице: П1 П2 П3 П4 i А1 30 33 36 39   3039;36;33;30min1  А2 28 36 39 42   2842;39;36;28min2  А3 26 34 42 45   2645;42;34;26min3  А4 24 32 40 48   2448;40;32;24min4  Вычислим   3024;26;28;30max  i  . Это равенство достигается на А1, следовательно, стратегия А1 является оптимальной по- Вальду. Это значит, что если торговое предприятие возьмет на реа- лизацию 5 тыс.ед., то его прибыль будет не меньше 30 тыс.ден.ед. Критерий Сэвиджа применяют в том случае, если игра задана матрицей рисков. Построим для нашей игры матрицу рисков, эле- менты ijr которой равны разности между наибольшим выигрышем j при данном состоянии природы и текущим выигрышем ija , то есть ijjij ar   , где ij i j amax . Результаты вычислений запи- шем в таблице: П1 П2 П3 П4 А1 03030  33336  63642  93948  А2 22830  03636  33942  64248  А3 42630  23436  04242  34548  А4 62430  43236  24042  04848  j 30 36 42 48 Оптимальной по-Сэвиджу является стратегия, на которой дости- гается минимальный риск при наихудшем состоянии природы, то есть стратегия, на которой выполняется равенство: i i  min , где ij j i amax . Результаты вычислений запишем в таблице: 71 П1 П2 П3 П4 i А1 0 3 6 9   99;6;3;0max1  А2 2 0 3 6   66;3;0;2max2  А3 4 2 0 3   43;0;2;4max3  А4 6 4 2 0   60;2;4;6max4  Вычислим   46;4;6;9min  i  . Это равенство достигается на А3, следовательно, стратегия А3 является оптимальной по-Сэвиджу. Это значит, что если торговое предприятие возьмет на реализацию 7 тыс.ед., то его риск будет не больше 4 тыс.ден.ед. Оптимальной по-Гурвицу является стратегия, на которой выпол- няется равенство i i  max , где ij j ij j i aa max)1(min   , λ – постоянная, 10   . Если λ=1, то оптимальной является стратегия, на которой достигается максимальная прибыль при наихудшем состоянии природы, то есть критерий Гурвица стано- вится критерием Вальда (критерием пессимиста). Если λ=0, то оп- тимальной является стратегия, на которой достигается максималь- ная прибыль при наилудшем состоянии природы, то есть критерий оптимиста. На практике чаще всего выбирают 8,06,0   . В нашем задании λ=0,7. Результаты вычислений запишем в таблице: П1 П2 П3 П4 ij j amin7,0  ij j amax3,0  i А1 30 33 36 39 0,7·30=21 0,3·39=11,7 32,7 А2 28 36 39 42 0,7·28=19,6 0,3·42=12,6 32,2 А3 26 34 42 45 0,7·26=18,2 0,3·45=13,5 31,7 А4 24 32 40 48 0,7·24=16,8 0,3·48=14,4 31,2 Вычислим   7,322,31;7,31;2,32;7,32max  i  . Оптимальной по-Гурвицу является стратегия А1. Это значит, что торговое пред- приятие должно брать на реализацию 5 тыс.ед. товара. 72 S 1 2 3 4 5 7 6 10 3 12 6 5 8 9 5 7 4 3 10 13 8 Решение задания типа 51–60 Дана сеть с указанными пропускными способностями ребер ijr (одинаковы в обоих направлениях). Найти: 1) Максимальный поток из источника I в сток S методом меток; 2) Минимальный разрез (указать пунктирной линией на сети). Задание 1. Рассмотрим сеть с одним источником I и одним сто- ком S. Нужно определить максимальную величину потока  (коли- чество вещества, информации), который может войти в сетевую си- стему и выйти из неё в заданный период времени. Построим поток через ребра сети, учитывая пропускные способности ребер и пред- полагая, что поток, вытекающий из вершины, равен потоку, втека- ющему в нее. Определим некоторые пути из I в S и величины потоков по этим путям: L 1 : 1 – 2 – 5 – 7 , 10 =5; L 2 : 1 – 5 – 7 , 20 =3; L 3 : 1 – 4 – 7 , 30 =4; L 4 : 1 – 3 – 6 – 7 , 40 =6; 73 1 2 3 4 5 7 6 10,5+5 3,3 12,4 6,6 5 8 9,5 5,5 7,5 4,4 3 10,6 13,5+3+5 8,6 L 5 : 1 – 2 – 4 – 5 – 7 , 50 =5; Таким образом, начальный поток будет равен: 0 = 5040302010   =23(ед.) Стрелками на ребрах покажем направление потока, а числа ijх , стоящие рядом с пропускными способностями ijr , будут показывать его величину. Назовем ребро ненасыщенным, если ijr > ijх ; если же ijr = ijх , то ребро насыщенно. Когда нельзя указать ни одного пути из I в S по ненасыщенным ребрам, то построенный поток является максимальным и его нельзя увеличить. В противном случае постро- енный поток можно увеличить и для этого надо найти путь из нена- сыщенных ребер от I к S.Для построения такого пути используется метод меток. Источнику I припишем метку (0, + ). Это означает, что из величины I может поступить вещество в любом объеме. Находим на сети вершину, связанную с вершиной I ненасыщенным ребром, например, вершину 4. Ей приписываем метку (1  , min1   1414, xr  ) = =(1  , min1   412,  )=(1  ,8). 74 (6  ,2) 1 2 3 4 5 7 6 10,10 3,3 12,4 6,6 5 8 9,5 5,5 7,5 4,4 3 10,6 13,13 8, 6 (3  ,4) (4  ,8) (1  ,8) (0,+ ) Величине 1 =8 показывает насколько можно будет увеличить по- ток от I до вершины 4. Далее, рассмотрим вершину, связанную с вершиной 4 ненасыщен- ным ребром, например, вершину 3. Припишем ей метку (4  , min2   43431, xr  ) = (4  , min2   08,8  )= =(4  ,8). Аналогично, вершине 6 приписываем метку (3  , min3   36362 , xr  ) = (3  , min3   610,8  )= =(3  ,4). и вершине 7 приписываем метку (6  , min4   67673, xr  ) = (6  , min4   68,4  )= =(6  ,2). Проставим полученные метки на сети: Т.к сток оказался помеченным, это означает, что существует путь из I в S, состоящий из ненасыщенных ребер, и поток на этом пути 75 (3  ,3) 1 2 3 4 5 7 6 10,10 3,3 12,6 6,6 5 8,2 9,5 5,5 7,5 4,4 3 10,8 13,13 8,8 (4  ,6) (0,+  ) (1  ,6) (3  ,2) 1 2 3 4 5 7 6 10,10 3,3 12,9 6,6 5 8,5 9,5 5,5 7,5 4,4 3,3 10,8 13,13 8,8 (4  ,3) (0,+  ) (1  ,3) (4  ,3) (1 – 4 – 3 – 6 – 7 ) можно увеличить на  единиц, где     .22,4,8,8min,,,min 431 2   Величина нового потока будет равна: .)ед(25223201  Вершина 1 связана с вершиной 4 ненасыщенным ребром, поэто- му вновь расставляем метки и увеличиваем мощность потока по пути 1 – 4 – 3 – 7 на 3 единицы. Суммарный поток составит .)(283253 ед Расставим метки по ненасыщенным ребрам (рис.) от I к S. Т.к сток оказался непомеченным, то от источника I к стоку S не существует ни одного пути, состоящего из ненасыщенных ребер. 76 Следовательно, построенный поток является максимальным и его мощность равна .)(28max ед Задание 2. Для построения на сети минимального разреза разо- бьем множество всех вершин сети на два непересекающихся под- множества А и В. К множеству А относятся источник I и все вер- шины, которые можно достичь из I в S по ненасыщенным ребрам, т.е. помеченные вершины. К множеству В относятся все остальные вершины. В нашем задании: А= 6,5,4,3,2,1 , В= .7 Совокупность дуг ( ji, ), начальные вершины которых принад- лежат множеству А, а конечные – множеству В, будут определять разрез минимальной пропускной способности, отделяющий источ- ник от стока: А/B =  )7,6(),7,3(),7,4(),7,5( . На рисунке разрез А/B изображен пунктирной линией. Из теоремы Форда-Фолкерсона следует, что величина макси- мального потока в сети равна минимальной пропускной способно- сти разреза, т.е: .)(28)/( 7,67,37,47,5max едrrrrBAR  Ответ:  )7,6(),7,3(),7,4(),7,5(/ .),(28)/(max   BA едBAR 77 Решение задания типа 61–70 Дан список работ, подлежащих выполнению: Работа Непосредственно предшествующие работы Продолжительность работы 1a - 7 2a - 5 3a - 9 4a 3a 4 5a 3a 7 6a 3a 5 7a 1a 9 8a 1a 6 9a 8a 2 10a 2a , 6a , 7a 3 11a 2a , 6a , 7a 8 12a 2a , 6a , 7a 4 13a 4a , 5a , 12a 9 14a 4a 3 15a 9a , 12a 6 Требуется: 1. Построить сетевой график выполнения комплекса работ. 2. Непосредственно на графике вычислить ранние и поздние сроки свершения событий, резервы времени событий. 3. Выделить на графике критический путь и найти критический срок. 4. Найти полные и свободные резервы времени работ. 78 Задание 1. Работы на сетевом графике обозначаются дугами, а результат выполнения одной или нескольких работ является собы- тием и обозначается кружком. Работы 1a , 2a , 3a не имеют предшествующих, поэтому реализа- ция комплекса начинается с этих работ. Они изображаются дугами, выходящими из одной вершины, определяющей начальное событие 1(дуги на рисунке располагаются в произвольном порядке). Каждая работа оканчивается событием. Работам 4a , 5a , 6a предшествует работа 3a , поэтому дуги 4a , 5a , 6a располагаются вслед за событием, которым заканчивает- ся работа 3a . 1 1a 2a 3a 1 1a 2a 3a 4a 5a 6a 79 Работам 7a , 8a предшествует работа 1a , поэтому дуги 7a и 8a располагаются вслед за дугой 1a и т.д. Чтобы не изображать параллельными дугами одновременно вы- полняемые работы, вводят фиктивные работы нулевой продолжи- тельности, обозначаемые пунктирной линией. Т.о получили сетевой график комплекса работ с начальным со- бытием 1 и конечным событием х 9 . 1 1a 2a 3a 4a 5a 6a 7a 8a 80 Упорядочим вершины данной сети методом Фалкерсона. Про- нумеруем вершины в произвольном порядке х1, х2, …, х9. Нахо- дим вершины, в которые не входит ни одна дуга. Это будет группа I, в которую входит лишь одна вершина х1=1. Исключаем из рассмотрения вершину х1=1 и исходящие из неё дуги (помечаем одной чертой). В оставшейся сети находим вершины, в которые не входит ни одна дуга. Это будут вершины х2 и х3, они образуют группу II и нумеруются в произвольном порядке, например, х2=2; х3=3. Исключаем из рассмотрения вершины х2, х3 и дуги, из них ис- ходящие (помечаем двумя чертами) и т.д. Изобразим группы упорядоченных дуг с пронумерованными вершинами: 1 х8 х9 а 2 а 3 а 4 а 5 а 7 а 6 а 1 а 9 а 8 а 10 а 11 а 12 а 13 а 14 а 15 а 15 Х8 Х9 Х7 Х6 Х4 Х5 Х2 Х1 Х3 81 Задание 2. Запишем временные характеристики событий непо- средственно на сети. Для этого разобьем каждый кружок на четыре сектора: где i – номер события,  it p – ранний срок свершения события i ,  itn – поздний срок свершения события i ,  iR – резерв времени события i . I. При вычислении ранних сроков свершения событий переме- щаемся по сети от начального события 1 к конечному событию 9 в порядке возрастания номеров с использованием формулы: 1 1a 71 a 52 a 93 a 44 a 75 a 56 a 97 a 68 a 310 a 811 a 412 a 913 a 314 a 615 a 29 a 2 5 4 3 8 9 6 7 I V IV III II i  iR  itn  it p 82         jititjt t pp p ,max ,01       jji, где  j - множество работ, входящих в j-ое событие;  it p - ранний срок свершения начального события работы (i,j); t (i,j) – продолжительность работы (i,j). Например,                          ;1659;50;97max53;51;92max5 ;990max91max3 ;770max71max2    pppp pp pp tttt tt tt и т.д. Полученные результаты записываем в левый сектор кружка. II. При вычислении поздних сроков свершения событий переме- щаемся по сети от завершающего события 9 к начальному событию 1 в порядке убывания номеров с использованием формулы:           ,,min ,99 jitjtit tt nn pn     ,,   iji где  i – множество работ. выходящих из i-ого события;  jtn – поздний срок свершения конечного события работы (i,j). Например,                            ;1616;20;21min420;323;829min47;38;89min5 ;2092999min7 ;2362969min8 ;2999     nnnn nn nn pn tttt tt tt tt и т.д. Полученные результаты заносим в правый сектор кружка. 83 III. Разность между поздним и ранним сроками свершения собы- тия составляет резерв R(i) времени этого события т.е.      .ititiR pn  Например,             .41923888 .01616555   pn pn ttR ttR Полученные результаты заносим в нижний сектор кружка. Задание 3. Так как у критических событий резерв времени равен нулю, то критический путь лежит на событиях с нулевыми резерва- ми (указан двойной линией). 4 13 21 8 n 3 9 11 2 5 16 16 0 6 13 20 7 7 20 20 0 9 29 29 0 8 19 23 4 7 6 9 5 5 4 9 3 0 7 4 9 3 2 6 8 1 0 0 0 2 7 7 0 84 Если продолжительность работы принять за длину соответству- ющей дуги, то критическим называют путь максимальной длины от начального до завершающего события. Длина этого пути определя- ет критическое время крt выполнения всего комплекса работ, т.е. .299497 крt Задание 4.При распределении ресурсов при выполнении отдель- ных работ комплекса могут быть использованы такие показатели резерва времени работы (i,j), как – полный резерв  jiRn , : максимальная задержка работы (i,j) без нарушения критического срока        ;,, jititjtjiR pnn  – свободный резерв  jiRсв , :максимальная задержка работы (i,j), которая не влияет на ранние сроки последующих работ            .,,, jRjiRjititjtjiR nppсв  Работа (i,j) (1,5) (1,3) (3,6) (3,7) (3,5) (2,4) (4,8) (5,8) (5,9) (6,9) (8,9)  jiRn , 16-0- 5=11 11-0- 9=2 20-9- 4=7 20-9- 7=4 16-9- 5=2 21-7- 6=8 23-13- 2=8 23-16- 3=4 29-16- 8=5 29-13- 3=13 29-19- 6=4  jiRсв , 11-0=11 2-2=0 7-7=0 4-0=4 2-0=2 8-8=0 8-4=4 4-4=0 5-0=5 13-0=13 4-0=4 Решение задания типа 71–80 На строительство четырех предприятий, производящих некото- рую однородную продукцию, выделено 6 млн.усл.руб. По каждому из четырех предприятий известен возможный объем выпуска про- дукции    4,1ixgi в зависимости от капиталовложений  60  xx , выделенных на строительство. 85 1 2 3 4 5 6  xg1 21 23 25 29 30 31  xg2 20 22 26 28 29 32  xg3 19 21 24 27 29 33  xg4 20 21 25 27 29 33 Требуется: 1. Составить математическую модель задачи распределения ка- питаловложений в строительство предприятий, чтобы суммарный объем выпускаемой продукции был максимальным, и найти реше- ние этой задачи. 2. Используя полученное решение, найти: а) оптимальное (в смысле наибольшего объема выпускае- мой продукции) распределение 6 млн.усл.руб. между тремя пред- приятиями, б) оптимальное распределение 4 млн.усл.руб. между тремя предприятиями. Задание 1. Обозначим через        xFxFxFxF 4321 ,,, максималь- ное значение объема выпускаемой продукции, если бы выделяемый объем ресурса  60,  xx , был выделен либо одному предприя- тию   xF1 , либо распределен между двумя предприятиями   xF2 , либо между тремя предприятиями   xF3 , либо между четырьмя предприятиями   xF4 . 1 ш а г . Пусть ресурс х выделяется только одному (первому) предприятию. Тогда  xF1 =  xg1 (1) х 1 2 3 4 5 6  xF1 21 23 25 29 30 31 2 ш а г . Пусть объем средств  60,  xx распределяется между двумя предприятиями. Если второму предприятию выделяют 2x средств, то первому предприятию остается  2xx  средств и максимальный объем выпускаемой продукции будет равен 86  xF2 =     2122 0 2 max xxFxg xx   . (2) Запишем вычисления значений  xF2 в таблице, при этом справа будем отмечать оптимальные значения ресурса 2x , выделенные второму предприятию. Первое слагаемое в сумме будет соответ- ствовать  22 xg , а второе  21 xxF  =  21 xxg  . Таблица 1 2x x 0 1 2 3 4 5 6 2F  2x 1 0+21 =21 20+0 =20 21 0 2 0+23 =23 20+21 =41 22+0 =22 41 1 3 0+25 =25 20+23 =43 22+21 =43 26+0 =26 43 1,2 4 0+29 =29 20+25 =45 22+23 =45 26+21 =47 28+0 =28 47 3 5 0+30 =30 20+29 =49 22+25 =47 26+23 =49 28+21 =49 29+0 =29 49 1,3 ,4 6 0+31 =31 20+30 =50 22+29 =51 26+25 =51 28+23 =51 29+21 =50 32+0 =32 51 2,3 ,4 Поясним вычисления в табл. 1. 1-я строка: 1x , тогда 2x принимает значения: 2x = 0 и 2x = 1. Поэтому              21020,210max01,10max1 12122  FgFgF при 2x = 0. 2-я строка: 2x , тогда 2x = 0, 2x = 1 и 2x = 2. Поэтому                  41)22,41,23max(022,2120,230max 02,11,20max1 1212122   FgFgFgF при 2x = 1. 87 3-я строка: 3x , тогда 2x = 0 2x = 1, 2x = 2, 2x = 3. Поэтому                    03,12,21,30max3 121212122 FgFgFgFgF   026,2122,2320,250max   4326,43,43,25max  при 2x = 1 или  2x = 2. 4-я строка: 4x , тогда 2x =0 2x =1, 2x =2, 2x =3, 2x =4. Поэтому                                04 ,13,22,31,40 max4 12 12121212 2 Fg FgFgFgFg F   47)28,47,45,29max(028,2126,2322,2520,290max  при 2x =3. 5-я строка: 5x , тогда 2x =0 2x =1, 2x =2, 2x =3, 2x =4, 2x =5. Поэтому                  ,23,32,41,50max5 121212122 FgFgFgFgF          05,14 1212 FgFg   029,2128,2326,2522,2920,300max   4928,49,49,47,49,30max  при 2x =1,3,4. 6-я строка: 6x , тогда 2x =0 2x =1, 2x =2, 2x =3, 2x =4, 2x =5, 2x =6. По- этому                         ))0()6(),1()5(,24 ,33,42,51,60max6 121212 121212122 FgFgFg FgFgFgFgF   032,2129,2328,2526,2922,3020,310max   5132,50,51,51,51,50,31max  при 2x =2,3,4. 3 шаг. Пусть объем средств  60  xx распределяется между тремя предприятиями. Если третьему предприятию выделяют 3x 88 средств, то оставшиеся  3xx  распределяют между первым и вто- рым и максимальный объем выпускаемой продукции будет равен  xF3 =     3233 0 3 max xxFxg xx   (3) Запишем вычисления значений  xF3 в таблице, где первое сла- гаемое соответствует  33 xg , а второе –  32 xxF  , которое берем из таблицы 1. Таблица 2 3x x 0 1 2 3 4 5 6 3F  3x 1 0+21 =21 19+0 =19 21 0 2 0+41 =41 19+21 =40 21+0 =21 41 0 3 0+43 =43 19+41 =60 21+21 =42 24+0 =24 60 1 4 0+47 =47 19+43 =62 21+41 =62 24+21 =45 27+0 =27 62 1,2 5 0+49 =49 19+47 =66 21+43 =64 24+41 =65 27+21 =48 29+0 =29 66 1 6 0+51 =51 19+49 =68 21+47 =68 24+43 =67 27+41 =68 29+21 =50 33+0 =33 68 1,2 ,4 4 шаг. Пусть объем средств  60  xx распределяется между четырьмя предприятиями. Если четвертому предприятию выделяют 4x средств, то оставшиеся  4xx  распределяют между первыми тремя и максимальный объем выпускаемой продукции будет равен  xF4 =     4344 0 3 max xxFxg xx   (4) Запишем вычисления значений  xF4 в таблице, где первое сла- гаемое соответствует  44 xg , а второе –  43 xxF  , которое берем из таблицы 2. Таблица 3 89 4x x 0 1 2 3 4 5 6 4F 4x 1 0+21 =21 20+0 =20 21 0 2 0+41 =41 20+21 =41 21+0 =21 41 0,1 3 0+60 =60 20+41 =61 21+21 =42 25+0 =25 61 1 4 0+62 =62 20+60 =80 21+41 =62 25+21 =46 27+0 =27 80 1 5 0+66 =66 20+62 =82 21+60 =81 25+41 =66 27+21 =48 29+0 =29 82 1 6 0+68 =68 20+66 =86 21+62 =83 25+60 =85 27+41 =68 29+21 =50 33+0 =33 86 1 Уравнения (1) – (4) являются уравнениями Беллмана для данной задачи. На этом этапе реализуется принцип погружения динамиче- ского программирования. Чтобы получить максимальный объем выпускаемой продукции, необходимо в  xF4 подставить 60 x .   8664 F и 14  x . Следо- вательно, четвертому предприятию нужно выделить1 млн.усл.руб. Оставшиеся 51640  xx млн.усл.руб. распределяются между тремя предприятиями.   6653 F , а 13  x . Значит, третьему пред- приятию нужно выделить тоже 1 млн.усл.руб. Оставшиеся 4116340   xxx млн.усл.руб. распределяются между двумя предприятиями.   4742 F , а 32  x . Значит, второму предприятию выделяется 3 млн.усл.руб. Оставшийся 131162340   xxxx млн.усл.руб. выделяется первому предприятию. Таким образом, оптимальное решение задачи  1,1,3,1x и мак- симальный объем выпускаемой продукции   8664max  Fz . 90 Задание 2а). В основе динамического программирования лежит принцип оптимальности, на основании которого построенная оп- тимальная стратегия является оптимальной для любого количества оставшихся шагов и любых начальных состояний. Поэтому можно записать оптимальную стратегию, если 6 млн.усл.руб. распределя- ются между тремя предприятиями. В этом случае   6863max  Fz и 11,3  x или 22,3  x или 43,3  x . Пусть 11,3  x , тогда 5161,30  xx млн.усл.руб. распределя- ются между двумя предприятиями и   4952 F и 11,2  x , или 32,2  x , или 43,2  x . Тогда 41161,21,301,1   xxxx , или 23162,21,302,1   xxxx ,или 14163,21,303,1   xxxx Оптимальными стратегиями будут  1,1,41  x , или  1,3,22  x , или  1,4,13  x . Пусть 22,3  x , тогда 4262,30  xx млн.усл.руб. распреде- ляются между двумя предприятиями.   4742 F , а 32  x , значит, 132622,301   xxxx . Оптимальная стратегия имеет вид  2,3,1x . Если 43,2  x , то 2463,30  xx млн.усл.руб. распределяют- ся между двумя предприятиями.   4122 F , а 12  x , значит, 114623,301   xxxx . Оптимальная стратегия имеет вид  4,1,1x . Задание 2б). Если 40 x млн.усл.руб. распределяются между четырьмя предприятиями, то   8044max  Fz и 14  x . Оставшиеся 31440  xx млн.усл.руб. распределяются между тремя пред- приятиями, и   6033 F и 13  x . Следовательно, 2114340   xxx млн.усл.руб. распределяются между двумя 91 предприятиями. Но   4122 F и 12  x , значит, 111142301   xxxx . Оптимальная стратегия имеет вид  1,1,1,1x . Решение задания типа 81–90 Разработать оптимальную политику замены оборудования воз- раста пяти лет, исходя из условия максимизации ожидаемой прибы- ли за плановый период продолжительности десяти лет. Известны стоимость r (t) продукции в усл. ед., производимой в течение года с использованием данного оборудования возраста t лет; ежегодные расходы u (t) в усл. ед., связанные с эксплуатацией этого оборудо- вания, которые приведены в таблице; ликвидационная стоимость оборудования s = 5 в усл. ед., независящая от его возраста; стои- мость p = 20 в усл. ед. нового оборудования (сюда же включены расходы, связанные с установкой, наладкой и запуском оборудова- ния). Возраст оборудования s p 0 1 2 3 4 5 6 7 8 9 10 r(t) 50 49 48 47 47 46 45 43 42 40 40 10 30 u(t) 25 25 27 28 29 30 30 31 33 35 38 Сформулированная задача является задачей о замене оборудова- ния и решается методом динамического программирования. Обозначим через fn(t) максимально возможную прибыль за по- следние n лет планового периода при условии, что в начале периода мы имеем оборудование возраста t, и мы придерживаемся опти- мальной политики. Если на начало последнего планового года оборудования будет возраста t лет и его сохранить, то за последний год прибыль соста- вит r(t)−u(t). Если оборудование продать по остаточной стоимости и купить новое, то прибыль составит s–p+r(0)−u(0), где r(0) – стои- мость продукции, произведенной на новом оборудовании («нулево- 92 го возраста»), u(0) – расходы, связанные с эксплуатацией нового оборудования. Заменить оборудование выгодно, если s–p+r(0)−u(0) > r(t)−u(t). Таким образом,       .)0()0( ,)()( max)(1 заменаurpsq сохранениеtutr tf t Вычисляем значения этой функции при различных значениях t. Пусть t = 0       замена сохранение f 5255030-10q 252550 max)0(1 . Так как 25>5, то оптимальной политикой, соответствующей )0(1f является политика сохранения оборудования. Пусть t = 1       заменаq сохранение f 5 242549 max)1(1 . Так как 24>5, то оптимальной политикой, соответствующей )1(1f является поли- тика сохранения оборудования. Выполняя аналогичные вычисле- ния, результаты записываем в таблицу. При t = 9       заменаq сохранение f 5 53540 max)9(1 . Если при вычис- лении функции )(tfn получается равенство (5=5), оптимальную по- литику принимают первый раз в пользу сохранения оборудования, а последующие разы в пользу замены оборудования. Следовательно, в этом случае оптимальной является политика замены оборудова- ния. При t = 10       заменаq сохранение f 5 23840 )10(1 . Так как 2<5, то оп- тимальной политикой, соответствующей )10(1f является политика замены оборудования. Вычисления заносим в таблицу. Значение q записываем на краю таблицы. Если функция fn(t) принимает значение меньшее q, то мы попадаем в область замены оборудования. Чтобы в таблице разли- чать, в результате какой политики получается то или иное значение максимальной прибыли, разграничим жирной чертой элементы таб- лицы, соответствующие различным политикам. Слева от жирной 93 черты стоят значения, соответствующие политике «сохранения оборудования», а справа – политике «замены оборудования». Рассмотрим два последних плановых периода.         . .)1()0()0( ,)1()()( max)( 1 1 2 заменаfurpsq сохранениеtftutr tf t Вычисляем значения этой функции при различных значениях t. Пусть t = 0       замена сохранение f 29245q 49242550 max)0(2 . Так как 49>29, то оптимальной политикой, соответствующей )0(2f являет- ся политика сохранения оборудования. Пусть t = 1       заменаq сохранение f 29 45212549 max)1(2 . Так как 45>29, то оптимальной политикой, соответствующей )1(2f является политика сохранения оборудования. … При t = 6       заменаq сохранение f 29 27123045 max)6(2 . Так как 27<29, то оптимальной политикой, соответствующей )6(2f являет- ся политика замены оборудования. … Рассмотрим три последних плановых периода.         . .)1()0()0( ,)1()()( max)( 2 2 3 заменаfurpsq сохранениеtftutr tf t Вычисляем значения этой функции при различных значениях t. Пусть t = 0       замена сохранение f 50455q 70452550 max)0(3 . Так как 70>50, то оптимальной политикой, соответствующей )0(3f являет- ся политика сохранения оборудования. … При t = 4       заменаq сохранение f 50 49312947 max)4(3 . 94 Так как 49<50, то оптимальной политикой, соответствующей )4(3f является политика замены оборудования. … Рассмотрим четыре последних плановых периода.         . .)1()0()0( ,)1()()( max)( 3 3 4 заменаfurpsq сохранениеtftutr tf t Вычисляем значения этой функции при различных значениях t. Пусть t = 0       замена сохранение f 69645q 89642550 max)0(4 . Так как 70>50, то оптимальной политикой, соответствующей )0(3f являет- ся политика сохранения оборудования. … При t = 4       заменаq сохранение f 69 68502947 max)4(4 . Так как 68<69, то оптимальной политикой, соответствующей )4(4f являет- ся политика замены оборудования. Продолжая вычисления описанным способом, все результаты за- носим в таблицу (см. с. 95). Данные этой таблицы можно использовать для выбора опти- мальной политики замены оборудования. В начале планового десятилетнего периода имеется оборудова- ние пяти лет. В таблице на пересечении строки )(10 tf и столбца t = 5 находим значение максимальной прибыли, равное 174 (усл.ед.). Это значение записано справа от жирной линии, в области политики «замены оборудования». Это означает, что для достижения в плано- вом периоде из десяти лет максимальной прибыли равной 174 (усл.ед.) надо в первом году планового периода оборудование заме- нить. 95 t )(tfn 0 1 2 3 4 5 6 7 8 9 10 q )(1 tf 25 24 21 19 18 16 15 12 9 5 5 5 )(2 tf 49 45 40 37 34 31 29 29 29 29 29 29 )(3 tf 70 64 58 53 50 50 50 50 50 50 50 50 )(4 tf 89 82 74 69 69 69 69 69 69 69 69 69 )(5 tf 107 98 90 88 87 87 87 87 87 87 87 87 )(6 tf 123 114 109 106 105 103 103 103 103 103 103 103 )(7 tf 139 133 127 124 121 119 119 119 119 119 119 119 )(8 tf 158 151 145 140 138 138 138 138 138 138 138 138 )(9 tf 176 169 161 157 156 156 156 156 156 156 156 156 )(10 tf 194 185 178 175 174 174 174 174 174 174 174 174 96 К концу первого года возраст оборудования будет равен одному году и за последующие 9 лет планового периода значение макси- мальной прибыли стоит на пересечении строки )(9 tf и столбца t = 1, которое равно 169 (усл.ед.). Это значение записано слева от жир- ной линии, в области политики «сохранения оборудования», поэто- му на втором году планового десятилетнего периода оборудование надо сохранить. К концу второго года возраст оборудования будет равен двум годам и за последующие 8 лет значение максимальной прибыли стоит на пересечении строки )(8 tf и столбца t = 2, которое равно 145 (усл.ед.). Это значение записано слева от жирной линии, в обла- сти политики «сохранения оборудования», поэтому на третьем году планового десятилетнего периода оборудование надо сохранить. Рассуждая аналогично, результат формирования оптималь- ной политики можно символически записать следующим об- разом: замена год f  1 )5(10 сохранение год f  2 )1(9 сохранение год f  3 )2(8 сохранение год f  4 )3(7 сохранение год f  5 )4(6 замена год f  6 )5(5 сохранение год f  7 )1(4 сохранение год f  8 )2(3 сохранение год f  9 )3(2 сохранение год f  10 )4(1 97 ОГЛАВЛЕНИЕ Введение .................................................................................................. 3 Программа курса..................................................................................... 4 Литература .............................................................................................. 6 Контрольные задания ............................................................................. 7 Задания 1–10 ...................................................................................... 7 Задания 11–20 .................................................................................... 8 Задания 21–30 .................................................................................. 11 Задания 31–40 .................................................................................. 15 Задания 41–50 .................................................................................. 16 Задания 51–60 .................................................................................. 17 Задания 61–70 .................................................................................. 21 Задания 71–80 .................................................................................. 26 Задания 81–90 .................................................................................. 28 Методические указания к контрольной работе ................................. 31 Решение задания типа 1–10 ............................................................ 31 Решение задания типа 11–20 .......................................................... 34 Решение задания типа 21–30 .......................................................... 44 Решение задания типа 31–40 .......................................................... 58 Решение задания типа 41–50 .......................................................... 66 Решение задания типа 51–60 .......................................................... 72 Решение задания типа 61–70 .......................................................... 77 Решение задания типа 71–80 .......................................................... 84 Решение задания типа 81–90 .......................................................... 91 98 Учебное издание МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ Программные вопросы, контрольные задания и методические указания для студентов-заочников строительных специальностей экономического профиля Составители: ГУРИНА Татьяна Николаевна МОРОЗ Ольга Александровна Подписано в печать 08.02.2013. Формат 6084 1/16. Бумага офсетная. Ризография. Усл. печ. л. 5,70. Уч.-изд. л. 4,45. Тираж 100. Заказ 1301. Издатель и полиграфическое исполнение: Белорусский национальный технический университет. ЛИ № 02330/0494349 от 16.03.2009. Пр. Независимости, 65. 220013, г. Минск.