183653 (Решение задач симплекс-методом), страница 3
Описание файла
Документ из архива "Решение задач симплекс-методом", который расположен в категории "". Всё это находится в предмете "экономико-математическое моделирование" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "контрольные работы и аттестации", в предмете "экономико-математическое моделирование" в общих файлах.
Онлайн просмотр документа "183653"
Текст 3 страницы из документа "183653"
3-я итерация
cj | p0 | x0 | x1 | х2 | х3 | х4 | х5 | х6 | х7 |
0 | х4 | 0.6 | 0.0 | 0.0 | 0.0 | 1.0 | -0.1 | -0.6 | 0.4 |
8 | х1 | 26.3 | 1.0 | 0.0 | 0.0 | 0.0 | -0.2 | -0.3 | 0.4 |
15 | х2 | 24.3 | 0.0 | 1.0 | 0.0 | 0.0 | 0.1 | -0.3 | 0.0 |
10 | х3 | 3.6 | 0.0 | 0.0 | 1.0 | 0.0 | -0.1 | 0.4 | -0.6 |
Zj - Cj | 537.2 | 0.0 | 0.0 | 0.0 | 0.0 | -1.7 | -1.2 | -1.9 |
Подставив значения неизвестных в исходные неравенства, получаем:
1 * 26,3 + 1 * 24,3 + 0 * 3,6 ≥ 50
4 * 26,3 + 1 * 24,3 + 3 * 3,6 ≥ 140
1 * 26,3 + 4 * 24,3 + 1 * 3,6 ≥ 127
0 * 26,3 + 3 * 24,3 + 2 * 3,6 ≥ 80
Стоимость сырья при этом будет минимальной и составит:
F = 8 * 26,3 + 12 * 24,3 + 12 * 3,6 = 537,2
ЗАДАЧА 3
Составить оптимальный план перевозок пищевых продуктов от 4-х поставщиков к 6-ти потребителям. Поставщики (П), потребители (М), объемы вывоза и завоза, кратчайшие расстояния между пунктами вывоза и завоз приведены в таблице.
Поставщики | Потребители | Объемы вывоза, т | ||||||
М1 | М2 | М3 | М4 | М5 | М6 | |||
П1 | 24 | 30 | 42 | 15 | 39 | 21 | 144 | |
П2 | 9 | 24 | 30 | 33 | 27 | 29 | 148 | |
П3 | 24 | 22 | 20 | 45 | 21 | 23 | 76 | |
П4 | 11 | 36 | 27 | 40 | 30 | 8 | 132 | |
Объемы завоза, т | 92 | 84 | 80 | 112 | 96 | 36 |
Решение задачи начинается с распределения у имеющихся у поставщиков объемов вывоза между потребителями с учетом объемов завоза. Для первоначального распределения используются способы: северо-западного угла, наименьшего элемента по строке, наименьшего элемента по столбцу, наименьшего элемента матрицы.
Способ северо-западного угла состоит в том, что распределение объемов вывоза производится, начиная с верхнего левого угла таблицы и кончая нижним углом ее. Результаты распределения показаны в таблице.
Поставщики и объемы вывоза, т | Потребители и объемы завоза |
Потенциалы строк | ||||||
М1 | М2 | М3 | М4 | М5 | М6 | |||
92 | 84 | 80 | 112 | 96 | 36 | |||
П1 | 144 | 24 | 30 | 42 | 15 | 39 | 21 | 0 |
92 | 52 |
|
|
|
| |||
П2 | 148 | 9 | 24 | 30 | 33 | 27 | 29 | -6 |
| 32 | 80 | 36 |
|
| |||
П3 | 76 | 24 | 22 | 20 | 45 | 21 | 23 | 6 |
|
|
| 76 | 0 |
| |||
П4 | 132 | 11 | 36 | 27 | 40 | 30 | 8 | 15 |
|
|
|
| 96 | 36 | |||
Потенциалы столбцов | 24 | 30 | 36 | 39 | 15 | -7 |
|
Проверка плана на оптимальность. Когда исходный план получен и рассчитана соответствующая ему суммарная тонно-километровая работа, определяют, является ли этот план оптимальным. Для проверки плана на оптимальность применяется метод потенциалов.
Сущность метода потенциалов состоит в том, что для каждой строки и каждого столбца таблицы (матрицы) определяют специальные числа, называемые потенциалами. С помощью этих потенциалов можно установить, нужно ли заполнять свободную клетку матрицы или ее нужно оставить незаполненной.
Для решения задач методом потенциалов исходный план должен иметь количество заполненных клеток m + n – 1 (m - число строк, n - число столбцов). Если план не отвечает этим требованиям, то не для всех строк и столбцов можно рассчитать потенциалы, а без них нельзя проверить план на оптимальность.
Потенциалы строк и столбцов определяются по заполненным клеткам, находящимся на их пересечении.
Элемент заполненной клетки должен равняться сумме потенциалов строки и столбца, на пересечении которых находится эта заполненная клетка.
Для начала вычислений первый потенциал для строки или столбца принимается условно равным нулю, все остальные потенциалы определяются с помощью элементов заполненных клеток.
Обозначив потенциалы строк ui, потенциалы столбцов Vj, элементы заполнения клеток , можно записать порядок расчета потенциалов для общего случая.
Из основного требования = ui + Vj вытекает:
ui = - Vj; Vj = - ui
Из этих выражений видно, что для расчета потенциала строки необходимо иметь заполненную клетку, в столбце которой потенциал уже определен, а для расчета потенциала столбца нужна заполненная клетка, имеющая потенциал в строке.
Потенциалы показаны в таблице.
После того, как по строкам и столбцам определены потенциалы, с их помощью выясняется, является ли план оптимальным, и если нет, то как его можно улучшить. С этой целью для каждой свободной клетки вычисляется сумма потенциалов строк и столбцов, на пересечении которых находится эта клетка.
Сравнение суммы потенциалов с величиной элемента в свободных клетках позволяет определить, нужно ли заполнять эту клетку или ее нужно оставить свободной.
При решении задач на минимум функционала (в нашем случае на минимум тонно-километровой работы) не заполняются те свободные клетки, в которых сумма потенциалов меньше величины элемента (в нашем случае - расстояния).
Иными словами, если характеристика, значение которой равно разности - (ui + Vj), положительная, то свободная метка не заполняется при решении задачи на минимум функции.
Свободные клетки, имеющие нулевое значение характеристики, показывают на то, что их заполнение приведет к перераспределению поставок, но объем работ (значение функционала) останется неизменным.
Суммы потенциалов, значения элементов и характеристики для незаполненных клеток приведены в таблице.
Шифры клеток | П1-М3 | П1-М4 | П1-М5 | П1-M6 | П2-М1 | П2-М5 | П2-М6 | П3-М1 | П3-М2 | П3-М3 | П3-М6 | П4-М1 | П4-М2 | П4-М3 | П4-М4 |
Суммы потенциалов | 36 | 39 | 15 | -7 | 18 | 9 | -13 | 30 | 36 | 42 | -1 | 39 | 45 | 51 | 54 |
Значение элементов | 42 | 15 | 39 | 21 | 9 | 27 | 29 | 24 | 22 | 20 | 23 | 11 | 36 | 27 | 40 |
Характеристики | 6 | -24 | 24 | 28 | -9 | 18 | 42 | -6 | -14 | -22 | 24 | -28 | -9 | -24 | -14 |
В первоначальном плане шесть клеток имеют положительные характеристики, в девяти клетках характеристики отрицательные.
Так как задача решается на минимум целевой функции, то именно эти отрицательные клетки должны быть заполнены поставщиками. Но заполнение свободной клетки и связанное с ним перераспределение поставок производится не изолированно, а в связи с несколькими заполненными клетками. Эта связь выявляется путем построения замкнутых многоугольников, вершинами которых являются клетки таблицы. Одна вершина многоугольника находится в свободной клетке, а все остальные - в заполненных клетках. Многоугольник, или как его называют цепь, имеет прямые углы и четное число вершин.