История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Топ:
История развития методов оптимизации: теорема Куна-Таккера, метод Лагранжа, роль выпуклости в оптимизации...
Определение места расположения распределительного центра: Фирма реализует продукцию на рынках сбыта и имеет постоянных поставщиков в разных регионах. Увеличение объема продаж...
Устройство и оснащение процедурного кабинета: Решающая роль в обеспечении правильного лечения пациентов отводится процедурной медсестре...
Интересное:
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Дисциплины:
2017-10-11 | 378 |
5.00
из
|
Заказать работу |
|
|
Любой опорный план ТЗ должен удовлетворять двум условиям:
1. Количество занятых клеток должно равняться числу m+n-1
2. Опорный план должен быть ацикличным, т.е. в таблице с опорным планом невозможно построить замкнутую ломаную линию вершины которой располагались бы в занятых клетках, а звенья вдоль строк или столбцов.
Теорема
Если для некоторого опорного плана
x*=(xij) i=1,m; j=1,n существуют такие числа
U1, … Um,
V1, … Vm, что
(3)
(4)
То x*=(xij) – оптимальный опорный план ТЗ
Числа Ui и Vj называются потенциалами соответственно пунктов отправления и пунктов назначения. Данная теорема позволяет определить алгоритм поиска оптимального решения ТЗ.
Пусть построен опорный план ТЗ. Для каждого пункта отправления и назначения определяются потенциалы Ui и Vj. Эти числа определяются из системы линейных уравнений (3). Поскольку достаточно найти любое частное решение (3), то одну из неизвестных можно приравнять к произвольному числу, например Ui = 0 и найти из (3) остальные неизвестные. После того как найдены все потенциалы, для каждой из свободных клеток определяются числа,
которые называются оценками свободных клеток.
Если среди оценок нет отрицательных, что соответствует условию (4), то найденный опорный план будет оптимальным.
Если среди этих оценок есть отрицательные, то план не является оптимальным и необходимо перейти к новому опорному плану. Для этого выбирается клетка с наибольшей по абсолютной величине отрицательной разностью Sij и построим цикл, в котором кроме этой клетки все остальные являются базисными. Такой цикл всегда существует и единственен. Циклом в транспортной таблице называется несколько клеток, соединенных замкнутой ломаной линией так, чтобы две соседние вершины ломаной были расположены либо в одной строке, либо в одном столбце. Причем, одно звено каждой вершины находится в строке, другое в столбце.
|
Переход к новому опорному плану осуществляется путем изменения грузов в пределах клеток по следующему алгоритму:
1. По вершинам цикла расставляются чередующиеся знаки «+» и «-», причем в свободную клетку цикла ставится «+»
2. Находим минимальной значение груза в ячейках цикла имеющих знак «-» и вписываем его в свободную ячейку со знаком «+». Затем последовательно обходим все ячейки цикла, поочередно вычитая и прибавляя к ним минимальное значение (в соответствии со знаками, которыми эти ячейки помечены: где минус - вычитаем, где плюс - прибавляем).
Получем новый опорный план и снова вычисляем значения потенциалов и разности Sij.
2. Построить опорное решение методом «северо-западного» угла и методом минимального тарифа. Решить транспортную задачу методом потенциала для опорного плана, полученного при решении методом «северо-западного» угла.
1ai/bi | ||||
[4 | [5 | [7 | [2 | |
[9 | [8 | [7 | [9 | |
[4 | [6 | [8 | [7 |
2ai/bi | ||||
[4 | [8 | [5 | [7 | |
[7 | [6 | [4 | [6 | |
[5 | [9 | [8 | [3 |
3ai/bi | ||||
[7 | [4 | [8 | [6 | |
[3 | [9 | [5 | [4 | |
[8 | [7 | [4 | [5 |
4ai/bi | ||||
[5 | [6 | [6 | [4 | |
[7 | [5 | [6 | [3 | |
[4 | [5 | [9 | [3 |
5ai/bi | ||||
[8 | [7 | [6 | [7 | |
[4 | [8 | [3 | [7 | |
[5 | [6 | [4 | [5 |
6ai/bi | ||||
[7 | [5 | [6 | [5 | |
[4 | [3 | [5 | [6 | |
[8 | [7 | [5 | [7 |
7ai/bi | ||||
[8 | [7 | [4 | [4 | |
[6 | [9 | [6 | [8 | |
[5 | [8 | [5 | [6 |
8ai/bi | ||||
[7 | [6 | [8 | [7 | |
[6 | [7 | [5 | [9 | |
[7 | [6 | [6 | [9 |
9ai/bi | ||||
[7 | [6 | [5 | [8 | |
[9 | [8 | [7 | [7 | |
[8 | [9 | [7 | [8 |
10ai/bi | ||||
[4 | [6 | [7 | [6 | |
[5 | [3 | [4 | [5 | |
[4 | [5 | [8 | [9 |
11ai/bi | ||||
[8 | [4 | [7 | [3 | |
[6 | [8 | [6 | [8 | |
[5 | [4 | [5 | [6 |
12ai/bi | ||||
[7 | [6 | [8 | [7 | |
[4 | [5 | [6 | [3 | |
[8 | [6 | [7 | [9 |
|
13ai/bi | ||||
[5 | [6 | [4 | [3 | |
[8 | [4 | [9 | [5 | |
[7 | [5 | [7 | [4 |
14ai/bi | ||||
[8 | [4 | [7 | [3 | |
[6 | [8 | [6 | [8 | |
[5 | [4 | [5 | [6 |
16ai/bi | ||||
[8 | [9 | [7 | [8 | |
[7 | [6 | [8 | [7 | |
[6 | [5 | [6 | [4 |
15ai/bi | ||||
[9 | [6 | [7 | [5 | |
[8 | [7 | [9 | [6 | |
[7 | [8 | [6 | [7 |
17ai/bi | ||||
[4 | [3 | [2 | [3 | |
[5 | [6 | [4 | [5 | |
[6 | [5 | [2 | [3 |
18ai/bi | ||||
[8 | [7 | [8 | [9 | |
[6 | [6 | [5 | [7 | |
[8 | [7 | [6 | [8 |
19ai/bi | ||||
[8 | [5 | [7 | [7 | |
[6 | [6 | [8 | [7 | |
[7 | [5 | [6 | [6 |
20ai/bi | ||||
[7 | [8 | [6 | [3 | |
[9 | [7 | [5 | [8 | |
[6 | [7 | [4 | [6 |
21ai/bi | ||||
[5 | [8 | [3 | [5 | |
[5 | [4 | [6 | [4 | |
[4 | [7 | [6 | [5 |
22ai/bi | ||||
[7 | [7 | [6 | [5 | |
[9 | [8 | [9 | [7 | |
[8 | [6 | [7 | [8 |
23ai/bi | ||||
[6 | [9 | [8 | [7 | |
[8 | [7 | [6 | [8 | |
[7 | [5 | [6 | [8 |
24ai/bi | ||||
[7 | [8 | [6 | [7 | |
[8 | [9 | [7 | [8 | |
[6 | [7 | [6 | [7 |
25ai/bi | ||||
[5 | [4 | [6 | [3 | |
[7 | [8 | [9 | [6 | |
[6 | [7 | [4 | [5 |
26ai/bi | ||||
[4 | [5 | [4 | [6 | |
[3 | [4 | [5 | [2 | |
[6 | [3 | [6 | [5 |
27ai/bi | ||||
[5 | [6 | [7 | [6 | |
[8 | [8 | [7 | [9 | |
[7 | [4 | [6 | [7 |
28ai/bi | ||||
[8 | [8 | [7 | [8 | |
[6 | [7 | [9 | [8 | |
[7 | [8 | [6 | [7 |
29ai/bi | ||||
[7 | [8 | [7 | [9 | |
[8 | [7 | [6 | [8 | |
[6 | [8 | [5 | [6 |
30ai/bi | ||||
[7 | [8 | [7 | [9 | |
[8 | [6 | [8 | [7 | |
[7 | [8 | [7 | [6 |
3. Решить транспортную задачу на сети
10n |
20n |
-10n |
-9n |
-5n |
-7n |
n |
n – номер варианта
Контрольные вопросы
1. Что такое транспортная задача?
2. Что такое целевая функция и система ограничений?
3. Какие методы линейного программирования для решения транспортной задачи вы знаете?
4. В чем суть метода минимального тарифа?
ПРАКТИЧЕСКАЯ РАБОТА №2
Выбор оптимального варианта построения АИС небольшой фирмы
Цель работы: приобретение практических навыков по построению разных вариантов АИС небольшой фирмы и выбора из них оптимального.
|
Исходные данные
Условие задачи: На фирме работают три человека: генеральный директор, коммерческий директор, бухгалтер. Осуществляется два направления деятельности: оптовая торговля книгами, оптовая торговля канцелярскими товарами. Существует неограниченный доступ в Интернет. У каждого сотрудника свой персональный компьютер. Бухгалтерия учет предприятия полностью автоматизирован. Поиск поставщиков и покупателей ведется в сети Интернет, а связь с ними осуществляется частично через Интернет, частично с использованием обычных средств связи (почта, телефон, факс).
Ход работы:
1. Выделите информационные потоки предприятия
2. Предложите варианты построения АИС для представленной фирмы
3. Опишите преимущества и недостатки выбранного вами варианта построения АИС
Контрольные вопросы
1. Что такое АИС?
2. Какие типы АИС вы знаете?
3. Что такое обеспечивающая часть АИС?
4. Что такое функциональная часть АИС?
ПРАКТИЧЕСКАЯ РАБОТА №3.
|
|
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!