Решение транспортной задачи линейного программирования в среде MS Excel (стр. 6 из 9)
На этом действия этапа 3 заканчиваются, а найденные значения потенциалов записываются в исходную таблицу, которая на первой итерации алгоритма будет иметь следующий вид таблица 2.5.
Таблица 2.5. Таблица метода потенциалов
на первой итерации
| F(x) | 0 15 | 2 12 | 6 8,5 | 1 5,5 |
| 3 10 | 3 1 | 5 9 | 7 | 11 |
| 1 14 | 1 14 | 4 | 6 | 3 |
| 6 17 | 5 | 8 3 | 12 8,5 | 7 5,5 |
Для выполнения этапа 4 алгоритма по формуле (2.11)необходимо последовательно рассчитать значения оценок для свободных ячеек:
7-3-6=-2, 
4-1-2=1, 
6-1-6=-1, 
3-1-1=1, 
5-6-0=-1. Поскольку среди оценок свободных ячеек имеются отрицательные, то условие (2.12) не выполняется, и найденное решение не является оптимальным, т.е. его можно улучшить.Из всех
выбирается наименьшее значение 
-2. Соответствующая свободная ячейка для помечается знаком (*), и для нее х13 в таблице метода потенциалов строится цикл содержащий занятые ячейки: х12, х32, х33. После этого следует перейти к выполнению действий этапа 5.Таблица 2.6. Таблица метода потенциалов
после выполнения первой итерации
| F(x)=209,5 | V1 15 | V2 12 | V3 8,5 | V4 5,5 |
| u1 10 | 3 1 | 5 0,5(-) | 7 8,5(+) | 11 |
| u2 14 | 1 14 | 4 | 6 | 3 |
| U3 17 | 5 | 8 11,5(+) | 12 (-) | 7 5,5 |
Поскольку ячейка для х13 имеет знак (+), то соседние с ней в цикле занятые ячейки х12 и х33 будут иметь знак (-). Следуя по правилу чередования знаков, оставшаяся ячейка х32 будет иметь знак (+). Наименьшее из чисел в минусовых ячейках равно 8,5.
Ячейка х33 , в которой находится это число, становится свободной в новой таблице метода потенциалов. Другие значения ячеек цикла в новой таблице получаются следующим образом: новое значение в минусовой ячейке равно:
, новое значение в плюсовой ячейке равно: 
.В полученной таким образом новой таблице ячейка
становится свободной. После выполненных на этапе 5 преобразований получаем новое допустимое решение транспортной задачи с лучшим значением целевой функции F(x)=209.5. Этому допустимому решению соответствует новая таблица метода потенциалов, которая имеет следующий вид, таблица 2.7.После получения таблицы 2.7 следует приступить к проверке условия получения оптимального решения (вторая итерация, этап 3).
Таблица 2.7. Метода потенциалов на
второй итерации
| F(x)=209,5 | 0 15 | 2 12 | 4 8,5 | 1 5,5 |
| 3 10 | 3 1 | 5 0,5 | 7 8,5 | 11 |
| 1 14 | 1 14 | 4 | 6 | 3 |
| 6 17 | 5 | 8 11,5 | 12 | 7 5,5 |
Для этого предварительно необходимо найти новые потенциалы пунктов производства и потребления. Для определения значений потенциалов следует решить следующую систему уравнений: {v1+u1=3, v1+u2=1, v2+u1=5, v2+u3=8, v3+u1=7, v4+u3=7}. Полагая v1=0, находятся значения остальных неизвестных: v2=2, v3=4 v4=1, u1=3, u2=1 u3=6.
На этом действия этапа 3 заканчиваются, а найденные значения потенциалов записываются в таблицу, которая на второй итерации алгоритма будет иметь следующий вид, таблица 2.7.
Для выполнения этапа 4 на второй итерации алгоритма по формуле (2.11) необходимо последовательно рассчитать значения для свободных ячеек:
11-3-1=-7, 
4-1-2=1, 
6-1-4=1, 3-1-1=1, 
5-6-0=-1, 
12-6-4=2.Поскольку среди оценок свободных ячеек имеется единственная отрицательная, то условие (2.12) не выполняется, и найденное решение не является оптимальным, т.е. его можно улучшить. Для единственного значения
соответствующая свободная ячейка для х31 помечается знаком (+), и для нее в таблице метода потенциалов строится цикл, содержащий занятые ячейки: х11, х12,х32. После этого следует перейти к выполнению действий этапа 5 второй итерации.На этапе 5 необходимо определить плюсовые и минусовые ячейки. Поскольку ячейка для х31 имеет знак (+), то соседние с ней в цикле занятые ячейки х11 и х32 будут иметь знак (-). Следуя правилу чередования знаков, оставшаяся ячейка х12, будет иметь знак (+). Наименьшее из чисел в минусовых ячейках равно 1. Ячейка х11, в которой находится это число, становится свободной в новой таблице метода потенциалов. Другие значения ячеек цикла в новой таблице получаются следующим образом: новое значение в минусовой ячейке равно: x’32=x32-1=10.5, а новое значение в плюсовой ячейке равно: x’12=x12+1=1,5. В полученной таким образом новой таблице ячейка x’31=0 становится свободной. После выполненных на этапе 5 преобразований получаем новое допустимое решения транспортной задачи с лучшим значением целевой функции F(x)= 208.5. Этому допустимому решению соответствует новая таблица методов потенциалов, которая имеет следующий вид, таблица 2.8.
После получения таблицы 8 следует снова проверить условия получения оптимального решения (третья итерация, этап 3). Для этого необходимо найти новые потенциалы пунктов производства и потребления, т. е. решить следующую систему уравнений: {v1+u2=1, v1+u3=5, v2+u1=5, v2+u3=8, v3+u1=7, v4+u3=7}. Полагая v1=0, находятся значения остальных неизвестных: v2=3, v3=5 v4=2, u1=2, u2=1 u3=5. На этом действия этапа 3 заканчиваются, а найденные значения потенциалов записываются в таблицу, которая на третьей итерации алгоритма будет иметь следующий вид , таблица 9.
После получения таблицы 2.8 следует снова проверить условия получения оптимального решения (третья итерация, этап 3).
Для этого необходимо найти новые потенциалы пунктов производства и потребления, т. е. решить следующую систему уравнений: {v1+u2=1, v1+u3=5, v2+u1=5, v2+u3=8, v3+u1=7, v4+u3=7}. Полагая v1=0, находятся значения остальных неизвестных: v2=3, v3=5 v4=2, u1=2, u2=1 u3=5.
На этом действия этапа 3 заканчиваются, а найденные значения потенциалов записываются в таблицу, которая на третьей итерации алгоритма будет иметь следующий вид , таблица 2.9.
Таблица 2.8. Таблица метода потенциалов
после выполнения второй итерации
| F(x)=209,5 | V1 15 | V2 12 | V3 8,5 | V4 5,5 |
| u1 10 | 3 (-) | 5 1,5(-) | 7 8,5 | 11 |
| u2 14 | 1 14 | 4 | 6 | 3 |
| U3 17 | 5 1(+) | 8 10,5(-) | 12 | 7 5,5 |
Для выполнения этапа 4 на третьей итерации алгоритма по формуле (2.11) необходимо последовательно рассчитать значения оценок для свободных ячеек:
3-2-0=1, 
11-2-2=7, 4-1-3=0, 6-1-5=0, 
3-1-2=0, 
12-5-5=2. Поскольку среди оценок свободных ячеек отсутствуют отрицательные значения, то условие (2.12) выполняется, и найденное решение является оптимальным.Таблица 2.9. Таблица метода потенциалов
на третьей итерации
| F(x)=209,5 | 0 15 | 3 12 | 5 8,5 | 2 5,5 |
| 2 10 | 3 | 5 1,5 | 7 8,5 | 11 |
| 1 14 | 1 14 | 4 | 6 | 3 |
| 5 17 | 5 1 | 8 10,5 | 12 | 7 5,5 |
Таким образом, искомое оптимальное решение исходной транспортной задачи, полученное с использованием описанного алгоритма метода потенциалов, содержится в таблице9 и равно: х12=1,5, х13=8,5, х21=14, х31=1, х32=10,5, х34=5,5, значения остальных переменных равны 0. Оптимальное значение целевой функции при этом равно: F(x)=208.5.
Сравнение найденных оптимальных решений транспортной задачи с помощью программы MS Excel и метода потенциалов показывает их полное совпадение, что может свидетельствовать о достоверности соответствующих результатов.
2.4 Рекомендации по решению задач оптимизации с
помощью надстройки Поиск решения.
Построение математической модели задачи.
Работа по решению некоторой оптимизационной задачи всегда начинается с построения математической модели, для чего необходимо ответить на следующие вопросы:
- Каковы переменные модели (для определения каких величин строится модель)?