padding:0cm 5.4pt 0cm 5.4pt;height:40.35pt;">25
20
10
|
10
240
|
15 |
18 |
Число занятых клеток в
таблице, приведенной выше, равно m + n – 1 = 5 + 3 – 1 = 7, то есть условие
невырожденности выполнено. Получили исходное решение, которое запишем в виде
матрицы
Х1 =
Стоимость перевозки при исходном
решении составляет
f1 = 175 * 5 + 175 * 15 + 40 * 10 + 160
* 6 + 200 * 4 + 10 * 20 + 240 * 10 = 8260.
Проверим найденное решение транспортной задачи на
оптимальность Найденное
исходное решение проверяется на оптимальность методом потенциалов по следующему
критерию: если решение транспортной задачи является оптимальным, то ему
соответствует система m+n ( 5 + 3 = 8 ) действительных чисел
и
, удовлетворяющих условиям
для занятых клеток и
– для свободных клеток.
Числа
и
называются
потенциалами. В распределительную таблицу добавляют столбец
и строку
.
Потенциалы
и
находят из равенства
, справедливого для занятых клеток. Одному из
потенциалов дается произвольное значение, например
, тогда остальные потенциалы определяются
однозначно. Так, если известен потенциал
, то
; если известен потенциал
, то
.
Обозначим
. Эту оценку называют оценкой свободных
клеток. Если
, то опорное
решение является оптимальным. Если хотя бы одна из оценок
, то решение не является оптимальным и его
можно улучшить, перейдя от одного решения к другому.
Проверим найденное
решение на оптимальность, добавив в распределительную таблицу, приведенную
ниже, столбец
и строку
.
Полагая
, запишем это значение в последнем столбце
таблицы.
|
bi
ai
|
1 |
2 |
3 |
4 |
5 |
|
| 175 |
225 |
240 |
160 |
200 |
𝛼i
|
| 1 |
350
|
5
175
|
15
175
|
18 |
16 |
8 |
0 |
| 2 |
400 |
6 |
10
40
|
15 |
6
160
|
4
200
|
-5 |
| 3 |
250 |
25 |
20
10
|
10
240
|
15 |
18 |
0 |
|
|
𝛽i
|
5 |
15 |
10 |
11 |
9 |
|
Для клетки (1,1) :
1 +
1 = 5,
1 = 0,
1 = 5
Для клетки (1,2) :
1 +
2 = 15,
1 = 0,
2 = 15
Для клетки (2,2) :
2 +
2 = 10,
2 = -5,
2 = 15
Для клетки (2,4) :
2 +
= 6,
2 = -5,
4 = 11
Для клетки (2,5) :
2 +
= 4,
2 = -5,
5 = 9
Для клетки (3,3) :
+
= 10,
3 = 0,
3 = 10
Найденные значения
потенциалов заносим в таблицу. Вычисляем оценки свободных клеток:
Δ13 =
1 +
3 – с 13 = 0 + 10 – 18 = - 8
0
Δ14 =
1 +
– с 14 = 0 + 11 – 16 = - 5
0
Δ15 =
1 +
– с 15 = 0 + 9 – 8 = 1
0
Δ21 =
+
– с 21 = -5 + 5 – 6 = -6
0
Δ23 =
+
– с 23 = -5 + 10 – 15 = -10
0
Δ31 =
+
– с 31 = 0 + 5 – 25 = -20
0
Δ34 =
+
– с 34 = 0 + 11 – 15 = -4
0
Δ35 =
+
– с 35 = 0 + 9 – 18 = -9
0
Получили одну оценку Δ15
= 1
0 следовательно, исходное решение не является оптимальным и его можно
улучшить.
Переход от одного решения
транспортной задачи к другому.
Наличие положительной
оценки свободной клетки (
)
при проверке решения на оптимальность свидетельствует о том, что полученное решение
не оптимально и для уменьшения значения целевой функции надо перейти к другому
решению. При этом надо перераспределить грузы, перемещая их из занятых клеток в
свободные. Свободная клетка становится занятой, а одна из ранее занятых клеток
– свободной.
Для свободной клетки Δ15
= 1
0 строится цикл (цепь, многоугольник), все вершины которого, кроме
одной, находятся в занятых клетках; углы прямые, число вершин четное. Около
свободной клетки цикла ставится знак (+), затем поочередно проставляют знаки
(-) и (+). У вершин со знаком (-) выбирают минимальный груз, его прибавляют к
грузам, стоящим у вершин со знаком (+), и отнимают от грузов у вершин со знаком
(-). В результате перераспределения груза получим новое решение. Это решение
проверяем на оптимальность, и так далее до тех пор, пока не получим оптимальное
решение.
Х2 =
Стоимость перевозки при
исходном решении составляет
f2 = 175 * 5 + 215 * 10 + 10 * 20 + 240
* 10 + 160 * 6 + 175 * 8 + 25 * 4 = 8085.
Проверим полученное решение на оптимальность. Для этого
запишем его в распределительную таблицу, приведенную ниже, найдем потенциалы
занятых и оценки свободных клеток.
|
bi
ai
|
1 |
2 |
3 |
4 |
5 |
|
| 175 |
225 |
240 |
160 |
200 |
𝛼i
|
| 1 |
350 |
Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.),
обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Поможем написать работу на аналогичную тему
Получить выполненную работу или консультацию специалиста по вашему учебному
проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus.
Помогаем в публикации. Правки вносим бесплатно.
Похожие рефераты:
-
Кратные интегралы
Понятие двойного и тройного интеграла. Кратные интегралы в криволинейных координатах. Геометрические и физические приложения кратных интегралов. Криволинейные и поверхностные интегралы: понятия и способы вычисления. Геометрические и физические приложения.
-
Анализ алгоритма Евклида в Евклидовых кольцах
Расширенный алгоритм Евклида, его использование для нахождения наибольшего общего делителя натуральных чисел посредством остатков от деления. Математическая проблема календаря. Евклидовы кольца - аналоги чисел Фибоначчи в кольце многочленов, их свойства.
-
Исследование математических моделей оптимизации обслуживания сложных систем
Некоторые математические вопросы теории обслуживания сложных систем. Организация обслуживания при ограниченной информации о надёжности системы. Алгоритмы безотказной работы системы и нахождение времени плановой предупредительной профилактики систем.
-
Кривые второго порядка
Окружность множество точек плоскости, равноудаленных от данной точки. Эллипс, множество точек плоскости, для каждой из которых сумма расстояний до двух точек плоскости. Парабола, множество точек плоскости, равноудаленных от данной точки плоскости.
-
Математические программирование
Графический и симплексный методы решения ОЗЛП. Построение функции цели, образующая совместно с системой ограничений математическую модель экономической задачи. Нахождение неотрицательного решения системы линейных уравнений. Решение транспортной задачи.
-
Вписанные и описанные окружности в треугольниках и четырехугольниках
Вписанная и описанная окружности в треугольниках и четырехугольниках, их определение и построение. Теорема Пифагора. Определение площади треугольника, трапеции и параллелограмма. Решение типовых задач по изложенным темам с применением полученных знаний.
-
Матрицы. Дифференциальные уравнения
Векторы на плоскости и в пространстве. Обыкновенное дифференциальное уравнение. Необходимые формулы для решения задач о касательной. Метод наименьших квадратов. Необходимые определения и формулы для вычисления интегралов. Производные элементарных функций.
-
Исследование прочности на разрыв полосок ситца
Задачи математической статистики. Распределение случайной величины на основе опытных данных. Эмпирическая функция распределения. Статистические оценки параметров распределения. Нормальный закон распределения случайной величины, проверка гипотезы.
-
Комплексные числа: их прошлое и настоящее
Об истории возникновения комплексных чисел и их роли в процессе развития математики. Алгебраические действия над комплексными числами и их геометрический смысл. Применение комплексных чисел к решению алгебраических уравнений 3-ей и 4-ой степеней.
-
Введение в математический анализ
Функция одной независимой переменной. Основные определения и понятия: число (рациональное, иррациональное), числовая ось, абсолютная величина, функция (основные ее элементы). Графики функций. Пределы, натуральный логарифм. Непрерывность функции.
-
Качественное исследование в целом двумерной квадратичной стационарной системы с двумя частными интегралами в виде кривых третьего и первого порядков
Построение квадратичной двумерной стационарной системы, нахождение состояний равновесия, исследование бесконечно-удаленной части плоскости. Необходимые и достаточные условия существования у системы двух частных интегралов. Построение траектории в круге.
-
Дифференциальные уравнения
Вычисление первого и второго замечательных пределов, неопределенного и определенного интегралов, площади криволинейной трапеции, координат середин сторон треугольника с заданными вершинами. Определение критических точек и асимптот графика функции.
-
Исследование функций
Основные теоремы дифференциального исчисления: Ферма, Ролля, Коши, Лагранжа и их доказательство. Локальные экстремумы функции, исследование ее на выпуклость и вогнутость, понятие точки перегиба. Асимптоты и общая схема построения графика функции.
-
Магические квадраты
Знакомство с историей появления и названия магических квадратов. Изучение способов заполнения магических квадратов. Реализация заполнения магических квадратов с помощью программы Microsoft Excel. Исследование количества решений поставленной задачи.
-
Математика
Практическое решение задач по математике: систем неравенств, определяющих множество внутренних точек треугольника; уравнений параболы и ее директрисы; функций, заданных различными аналитическими выражениями для различных областей изменения переменной.
-
Математический анализ
Исследование заданной функции и построение ее графика. Расчет объема тела, полученного вращением вокруг оси абсцисс фигуры, ограниченной линиями и осями координат. Вычисление интеграла при заданной силе. Работа, которую нужно совершить для сжатия пружины.
-
Алгоритм муравья
Механизмы реализации эвристических алгоритмов муравьиной колонии. Основная идея - использование механизма положительной обратной связи, помогающего найти наилучшее приближенное решение в сложных задачах оптимизации. Области применения алгоритма муравья.
-
Графы. Основные понятия
Восстановление графов по заданным матрицам смежности вершин. Построение для каждого графа матрицы смежности ребер, инцидентности, достижимости, контрдостижимости. Поиск композиции графов. Определение локальных степеней вершин графа. Поиск базы графов.
-
Вероятностные процессы и математическая статистика в автоматизированных системах
Нахождение предела прочности алюминиевых деформируемых сплавов при испытании на растяжение. Расчет коэффициентов регрессии. Выбор и описание метода условной оптимизации. Результаты обработки данных эксперимента. Определение типа поверхности отклика.
-
Возвратные последовательности
Определение возвратной последовательности. Формулы вычисления любого члена из нее. Характеристическое уравнение для возвратного уравнения. Исчисление конечных разностей. Обобщение произвольных возвратных последовательностей. Базис возвратного уравнения.
|