- содержательная постановка задачи коммивояжёра, транспортной задачи, задачи распределения ресурсов в ТЭС;

Санкт-Петербургский Государственный университет

Аэрокосмического приборостроения

 

РУКОВОДСТВО

К лабораторной работе

«Исследование задач оптимизации на графах»

 

 

Санкт-Петербург

 

 

Введение

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

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

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

- транспортные задачи;

- сетевые задачи.

 

 

1. цель лабораторной работы

Целью лабораторной работы является:

- закрепление теоретических знаний, получаемых студентами на лекционных и самостоятельных занятиях по решению транспортных задач;

- развитие практических навыков в постановке транспортных задач, в проведении их технико-экономической интерпретации, умения составлять по содержательному описанию задачи её математическую модель и проводить формализацию и исследование транспортных задач, преобразовав их в задачи линейного программирования;

- ознакомление с особенностями применения современных пакетов прикладных программ для решения транспортных задач, приобретение навыков в их постановке и решении на ПЭВМ;

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

В связи с этим при подготовке к проведению лабораторной работы обучаемым следует уяснить такие вопросы:

- методологические и методические основы подготовки и принятия решений в сложных технико-экономических системах (ТЭС);

- классификация задач выбора с одним отношением предпочтения;

- содержательная постановка задачи коммивояжёра, транспортной задачи, задачи распределения ресурсов в ТЭС;

- формализация задач выбора с линейной целевой функцией и ограничениями;

- основные этапы решения транспортной задачи;

- особенности подготовки исходных данных и решения транспортных задач с использованием пакета прикладных программ QSB и табличного процессора Excel 7.0.

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

 

 

2. теоретические основы работы

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

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

Постановка и методы решения транспортной задачи

Пусть имеется т пунктов отправления и п пунктов назначения. Запасы продукта в пунктах отправления обозначим через аi, потребность в продукте в… Балансовое условие производства и потребления имеет вид .

Постановка и метод решения задачи о многополюсной кратчайшей цепи

Кратчайшей цепью между двумя произвольными узлами является цепь, стоимость единицы потока по которой минимальна. Поскольку направление потока в неориентированных дугах нельзя определить… Пусть N = {1,2,..., n} – множество узлов, а ci j – количественный параметр (длина, стоимость) дуги (i, j),…

Приложение 1

Варианты индивидуальных заданий на выполнение лабораторной работы

А. Индивидуальные задания для решения транспортных задач

Задача 1. На трёх базах имеется некоторая продукция в количестве а₁=70, а₂=80, а₃=90, потребность в которой в пяти организациях составляет b₁=20, b₂=60, b₃=70, b₄=50, b₅=40.

Затраты времени и средств на перевозки продукции потребителям заданы матрицами

.

Найти оптимальные планы перевозок по критерию минимизации затрат (), по критерию минимизации суммарного времени перевозки продукции ().

Задача 2. Найти оптимальное распределение трёх видов механизмов, имеющих в количестве а₁=45, а₂=20, а₃=35 между четырьмя участниками работ, потребности которых соответственно равны b₁=10, b₂=20, b₃=30, b₄=40, при следующей матрице производительности каждого из механизмов на соответствующем участке работы.

.

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

Задача 3. Составить оптимальное распределение специалистов четырёх профилей, имеющихся в количествах 60, 30, 45, 25 между пятью видами работ. Потребности в специалистах для каждого вида работы соответственно равны 20, 40, 25, 45 и 30. Матрица

характеризует эффективность использования специалиста на данной работе.

Задача 4. Четыре различных предприятия могут выпускать любой из четырёх видов продукции. Производственные мощности предприятия позволяют обеспечить выпуск продукции каждого вида в количествах 50, 70, 100 и 30 тыс. штук. Плановое задание составляет соответственно 30, 80, 20, 100 тыс. штук. Матрица

характеризует себестоимость единицы i-го вида продукции при производстве его на k-м предприятии. Найти оптимальное распределение планового задания между предприятиями.

Задача 5. Имеется три участка земли, на которых могут быть засеяны кукуруза, пшеница, ячмень и просо. Площадь каждого из участков соответственно равна 600, 180 и 220 га. С учётом наличия семян кукурузы, пшеницы, ячменя и проса, следует соответственно засеять 290, 180, 110, 420 га. Урожайность каждой из культур для каждого из участков различна и задаётся матрицей

.

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

Задача 6. Мясокомбинат имеет в своём составе четыре завода, на каждом из которых может изготовляться три вида колбасных изделий. Мощности каждого из заводов соответственно равны 320, 280, 270 и 350 т/сутки. Ежедневные потребности в колбасных изделиях каждого вида также известны и соответственно равны 450, 370 и 400 т. Зная себестоимость 1 т каждого вида колбасных изделий на каждом заводе, определяются матрицей

.

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

Задача 7. Решить транспортную задачу по перевозке однородной продукции со складов в магазины. Запасы продукции на складах А, Б, В соответственно равны 200, 270, 130 тонн. Потребность магазинов I, II, III, IV в продукции соответственно равна 120, 80, 240, 160 тонн. Тарифы перевозок единицы продукции из каждого из складов во все магазины задаются матрицей

.

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Задача 8. Решить транспортную задачу по перевозке однородной продукции со складов в магазины. Запасы продукции на складах А, Б, В, Г соответственно равны 180, 160, 140, 220 тонн. Потребность магазинов I, II, III, IV в продукции соответственно равна 150, 250, 120, 180 тонн. Тарифы перевозок единицы продукции из каждого из складов во все магазины задаются матрицей

.

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Задача 9. Решить транспортную задачу по перевозке однородной продукции со складов в магазины. Запасы продукции на складах А, Б, В соответственно равны 90, 60, 150 тонн. Потребность магазинов I, II, III, IV в продукции соответственно равна 120, 40, 60, 80 тонн. Тарифы перевозок единицы продукции из каждого из складов во все магазины задаются матрицей

.

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Задача 10. Решить транспортную задачу по перевозке однородной продукции со складов в магазины. Запасы продукции на складах А, Б, В соответственно равны 50, 30, 10 тонн. Потребность магазинов I, II, III, IV в продукции соответственно равна 30, 30, 10, 20 тонн. Тарифы перевозок единицы продукции из каждого из складов во все магазины задаются матрицей

.

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Задача 11. Решить транспортную задачу по перевозке однородной продукции со складов в магазины. Запасы продукции на складах А, Б, В соответственно равны 180, 350, 20 тонн. Потребность магазинов I, II, III, IV, V в продукции соответственно равна 110, 90, 120, 80, 150 тонн. Тарифы перевозок единицы продукции из каждого из складов во все магазины задаются матрицей

.

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Задача 12. Решить транспортную задачу по перевозке однородной продукции со складов в магазины. Запасы продукции на складах А, Б, В соответственно равны 160, 140, 170 тонн. Потребность магазинов I, II, III, IV в продукции соответственно равна 120, 50, 190, 110 тонн. Тарифы перевозок единицы продукции из каждого из складов во все магазины задаются матрицей

.

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Задача 13. Решить транспортную задачу по перевозке однородной продукции со складов в магазины. Запасы продукции на складах А, Б, В, Г соответственно равны 50, 20, 30, 40 тонн. Потребность магазинов I, II, III, IV, V в продукции соответственно равна 15, 30, 65, 20, 10 тонн. Тарифы перевозок единицы продукции из каждого из складов во все магазины задаются матрицей

.

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Задача 14. Решить транспортную задачу по перевозке однородной продукции со складов в магазины. Запасы продукции на складах А, Б, В, Г соответственно равны 10, 70, 60, 30 тонн. Потребность магазинов I, II, III, IV, V в продукции соответственно равна 40, 40, 60, 25, 5 тонн. Тарифы перевозок единицы продукции из каждого из складов во все магазины задаются матрицей

.

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Задача 15. Решить транспортную задачу по перевозке однородной продукции со складов в магазины. Запасы продукции на складах А, Б, В, Г соответственно равны 10, 48, 27, 46 тонн. Потребность магазинов I, II, III, IV, V в продукции соответственно равна 17, 33, 38, 21, 22 тонн. Тарифы перевозок единицы продукции из каждого из складов во все магазины задаются матрицей

.

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Задача 16. Решить транспортную задачу по перевозке однородной продукции со складов в магазины. Запасы продукции на складах А, Б, В, Г соответственно равны 80, 12, 38, 45 тонн. Потребность магазинов I, II, III, IV, V в продукции соответственно равна 75, 10, 20, 40, 30 тонн. Тарифы перевозок единицы продукции из каждого из складов во все магазины задаются матрицей

.

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Задача 17. Решить транспортную задачу по перевозке однородной продукции со складов в магазины. Запасы продукции на складах А, Б, В, Г соответственно равны 14, 25, 56, 45 тонн. Потребность магазинов I, II, III, IV, V в продукции соответственно равна 40, 40, 20, 10, 30 тонн. Тарифы перевозок единицы продукции из каждого из складов во все магазины задаются матрицей

.

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Задача 18. Решить транспортную задачу по перевозке однородной продукции со складов в магазины. Запасы продукции на складах А, Б, В, Г соответственно равны 15, 17, 23, 75 тонн. Потребность магазинов I, II, III, IV, V в продукции соответственно равна 30, 27, 16, 33, 24 тонн. Тарифы перевозок единицы продукции из каждого из складов во все магазины задаются матрицей

.

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Задача 19. Решить транспортную задачу по перевозке однородной продукции со складов в магазины. Запасы продукции на складах А, Б, В, Г соответственно равны 30, 70, 50, 20 тонн. Потребность магазинов I, II, III, IV, V в продукции соответственно равна 35, 30, 35, 45, 25 тонн. Тарифы перевозок единицы продукции из каждого из складов во все магазины задаются матрицей

.

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Задача 20. Решить транспортную задачу по перевозке однородной продукции со складов в магазины. Запасы продукции на складах А, Б, В, Г соответственно равны 50, 20, 10, 30 тонн. Потребность магазинов I, II, III, IV, V в продукции соответственно равна 5, 15, 35, 15, 40 тонн. Тарифы перевозок единицы продукции из каждого из складов во все магазины задаются матрицей

.

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Задача 21. Решить транспортную задачу по перевозке однородной продукции со складов в магазины. Запасы продукции на складах А, Б, В, Г соответственно равны 60, 50, 40, 20 тонн. Потребность магазинов I, II, III, IV, V в продукции соответственно равна 10, 50, 40, 50, 20 тонн. Тарифы перевозок единицы продукции из каждого из складов во все магазины задаются матрицей

.

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Задача 22. Решить транспортную задачу по перевозке однородной продукции со складов в магазины. Запасы продукции на складах А, Б, В, Г соответственно равны 10, 13, 28, 17 тонн. Потребность магазинов I, II, III, IV, V в продукции соответственно равна 11, 10, 14, 16, 17 тонн. Тарифы перевозок единицы продукции из каждого из складов во все магазины задаются матрицей

.

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Задача 23. Решить транспортную задачу по перевозке однородной продукции со складов в магазины. Запасы продукции на складах А, Б, В, Г соответственно равны 20, 30, 70, 71 тонн. Потребность магазинов I, II, III, IV, V в продукции соответственно равна 37, 26, 91, 24, 13 тонн. Тарифы перевозок единицы продукции из каждого из складов во все магазины задаются матрицей

.

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Задача 24. Решить транспортную задачу по перевозке однородной продукции со складов в магазины. Запасы продукции на складах А, Б, В, Г соответственно равны 20, 40, 52, 73 тонн. Потребность магазинов I, II, III, IV, V в продукции соответственно равна 45, 38, 40, 28, 34 тонн. Тарифы перевозок единицы продукции из каждого из складов во все магазины задаются матрицей

.

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Задача 25. Решить транспортную задачу по перевозке однородной продукции со складов в магазины. Запасы продукции на складах А, Б, В, Г соответственно равны 29, 39, 28, 42 тонн. Потребность магазинов I, II, III, IV, V в продукции соответственно равна 25, 13, 60, 15, 25 тонн. Тарифы перевозок единицы продукции из каждого из складов во все магазины задаются матрицей

.

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Б. Индивидуальные задания для решения задачи о многополюсной кратчайшей цепи

1.1	1.2	1.3
1.4	1.5	1.6
1.7	1.8	1.9
1.10	1.11	1.12
1.13	1.14	1.15
1.16	1.17	1.18

 

Приложение 2

Использование пакета прикладных программ qsb в процессе принятия решений

Порядок решения транспортных задач с помощью QSB рассмотрим на следующем примере. Пример П2.1. Требуется составить такой план прикрепления трёх потребителей к… Таблица П2.1 Поставщики Тарифы перевозок Предложение поставщиков …

Экран 1

постав.: S1: 120____ S2: 100____ S3: 80___ D1: 90____ D2: 90____ D3: 120___

После нажатия клавиши Spacebar на экране появится шаблон для ввода стоимости перевозок (или прибыли от перевозок).

Введите данные, как показано ниже:

Экран 2

от к S1: D1: 7____ D2: 6____ D3: 4___ S2 D1: 3____ D2: 8___ D3: 5___ S3 D1: 2____ D2: 3____ D3: 7____

После нажатия Spacebar на экране появится функциональное меню.

В функциональном меню выберите опцию 5 – Решение задачи. На экране появится меню опции <Решение>:

Экран 3

Для построения начального допустимого плана по умолчанию используется метод северо-западного угла, который можно заменить на метод аппроксимации… Для поиска оптимального плана применён метод потенциалов. При этом признаком… U(i)+V(j)=C(i,j) для xi j > 0;

Экран 4

Выберите опцию 1 – просмотр итогового решения. На экране появится таблица с результатами решения задачи:

Экран 5

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

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

Из пункта i	Расстояние до пункта j

Требуется найти кратчайший маршрут от пункта 1 до любого другого пункта.

Подготовьте исходные данные задачи для решения на ЭВМ: определите число ветвей и узлов в задаче (20 ветвей и 5 узлов).

Выберите опцию 5 Сетевое моделирование (NET)в главном меню системы. На экране появится функциональное меню, идентичное рассмотренному ранее.

В функциональном меню выберите опцию 2-Ввод новой задачи, введите название задачи (например, prim5), ответьте на вопросы о задаче. Варианты ответов: 20 ветвей, 5 узлов, будем использовать алгоритм кратчайшего пути. По окончании нажмите клавишу Spacebar. На экране появится шаблон для ввода расстояния между пунктами. Заполните шаблон следующим образом:

Ветвь Номер	Ветвь Код	Нач. узел	Кон. узел	Расстоян.	Ветвь Номер	Ветвь Код	Нач. узел	Кон. узел	Расстоян.
	<B1 > <B2 > <B3 > <B4 > <B5 > <B6 > <B7 > <B8 > <B9 > <B10 >	<1> <1> <1> <1> <2> <2> <2> <2> <3> <3>	<2> <3> <4> <5> <1> <3> <4> <5> <1> <2>	<10 > <25 > <25 > <10 > <1 > <10 > <15 > <2 > <8 > <9 >		<B11 > <B12 > <B13 > <B14 > <B15 > <B16 > <B17 > <B18 > <B19 > <B20 >	<3> <3> <4> <4> <4> <4> <5> <5> <5> <5>	<4> <5> <1> <2> <3> <5> <1> <2> <3> <4>	<20 > <10 > <14 > <10 > <24 > <15 > <10 > <8 > <25 > <27 >

Можно дать произвольные названия ветвям длиной до 6 символов (заданные по умолчанию – В₁,...,В_п). Узлы нумеруются последовательно, начиная с 1 до 5. Ветви вводятся в произвольной последовательности. После нажатия Spacebar на экране появится функциональное меню.

В функциональном меню выберите опцию 5 – Решение задачи. На экране появится меню опции <Решение>:

Меню опции <Решение> prim 5

пункт 1---- Решение и просмотр по шагам 2---- Решение без просмотра по шагам 3---- Возврат в функциональное меню

Выбор опции 3 обеспечивает возврат в функциональное меню без решения задачи. Опция 1 обеспечивает просмотр процесса решения задачи с помощью заданного вами алгоритма (алгоритма кратчайшего пути). Опция 2 даёт решение без просмотра процесса по шагам.

Выберите опцию 2 – Решение без просмотра по шагам. Результат решения задачи:

итоговый кратчайший путь для prim5 Стр.: 1
узел	Расстояние	Кратчайший путь из узла 1
		1-2(В1)
		1-3(В2)
		1-2-4(В1-В7)
		1-2-5(В1-В8)

В графе «Расстояние» показана длина кратчайшего пути от 1 пункта до указанного пункта в графе «узел»; в последней графе – названия пунктов, через которые проходит кратчайший путь, а в скобках – названия ветвей. После нажатия любой клавиши на экране появится меню <Решение>.

Выйдите в функциональное меню и выберите 7 – Измерение задачи.

На экране появится меню опции <Изменение>, в котором выберите опцию 5 – Выбор алгоритма. На экране появится меню выбора алгоритма модели, где показан текущий алгоритм и предложено 3 варианта выбора: алгоритм кратчайшего пути (1), алгоритм максимального потока (2) и алгоритм минимального размаха дерева (3).

Введите цифру 2 и нажмите Enter. Ранее введённые данные о расстоянии между пунктами теперь интерпретируются как величина потока (объём грузоперевозок) между этими пунктами. Найдём максимальную величину потока от начального узла до конечного, т.е. максимальный суммарный объём грузоперевозок. Для этого вернитесь в функциональное меню и решите задачу.

итоговый поток для prim5 Стр.:1
Ветвь	поток
1-2(В1) 1-3(В2) 1-4(В3) 1-5(В4) 2-3(В6) 2-4(В7) 2-5(В8) 3-4(В11) 3-5(В12) 4-5(В16)
Макс. итоговый поток = 0

Поскольку сеть замкнута, то максимальный поток равен нулю.

 

Приложение 3

Поиск оптимальных решений задач линейного программирования с использованием программных средств excel 7.0

Решение задач линейного программирования с использованием Excel 7.0 осуществляется с помощью инструментального средства Поиск решения. Для запуска… После загрузки инструмента Поиск решения в списке опций ниспадающего меню… В поле ввода Установить целевую ячейку указывается ссылка на ячейку с целевой функцией, значение которой будет…

Литература

1. Акулич И.Л. Математическое программирование в примерах и задачах: Уч. пособие для студентов экон. спец. вузов. – М.: Высшая школа, 1998.

2. Акулич И.Л., Ворончук И.С. Задачи нелинейного и динамического программирования. – Рига: Изд-во ЛГУ, 1989..

3. Иванилов Ю.П., Лотов А.В. Математические модели принятия решений в управлении и экономике. – М.: Наука, 1979.

4. Ларичев О.И. Наука и искусство принятия решений. – М.: Наука, 1979.

5. Саати Т. Принятие решений. Метод анализ иерархий: Пер. с англ. – М.: Ради и связь, 1989.

6. Князевский Н.В., Князевская В.С. Принятие раскованных решений в экономике и бизнесе: Уч. пособие. – М.: Контур, 1998.

7. Фатхутдинов Р.А. Разработка управленческого решения. – Учебник, М.: ЗАО «Бизнес-школа Интел-Синтез», 1998.

8. Андрейчиков А.В., Андрейчикова О.Н. Анализ, синтез, планирование решений в экономике. – Учебник. – М.: Финансы и статистика, 2000.

9. Красников В.С. Разработка управленческих решений. – СПб.: Изд-во СЗАГС, 1999.

10. Глухов В.В., Медников М.Д., Коробко С.Б. Экономико–математические методы и модели в менеджменте. – Уч. пособие. – СПб.: Изд-во СПб ГТУ, 1999.

11. Курицкий Б.Я. Поиск оптимальных решений средствами Excel 7.0. – СПб., ВНV Санкт-Петербург, 1997.

ОГЛАВЛЕНИЕ

введение.............................................................................................. 2

1. цель лабораторной работы................................................ 3

2. теоретические основы работы....................................... 4

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

2.2. Постановка и методы решения транспортной задачи 7

3. Методические указания по выполнению лабораторной работы.......................................................................................................... 12

4. форма отчётности по выполненной лабораторной работе........................................................................................................................... 18

Приложение 1. варианты индивидуальных заданий на выполнение лабораторной работы.............................. 19

Приложение 2. использование пакета прикладных программ qsb в процессе принятия решений................................ 28

Приложение 3. поиск оптимальных решений задач линейного программирования с использованием программных средств excel 7.0......................................................................... 31

литература....................................................................................... 33