Пошук рішення в ms Excel

На трьох складах A,B,C знаходиться 65, 80 і 105 центнерів борошна відповідно. Потрібно скласти план його перевезення до чотирьох споживачів (I, II, III, IV) так, щоб вони отримали потрібні 45, 60, 80 і 65 центнерів борошна відповідно, а затрати на перевезення були мінімальними. Вартість перевезення 1 центнера борошна (в гривнях) зі складів до споживачів вказані в таблиці:

Склади	Споживачі
	I	II	III	IV
A	4	5	7	3
B	5	3	4	5
C	3	6	5	4

Розв’язання:

Нехай

 матриця, що визначає план перевезень;

матриця транспортних витрат;

 вектор ресурсів складів A, B, C;

 вектор потреб споживачів I, II, III, IV.

Ця транспортна задача є закритою, оскільки сумарні ресурси і сумарні потреби співпадають:

Сформулюємо математичну модель задачі.

1. цільова функція, що відповідає сумарним затратам на перевезення борошна зі складів споживачам має вигляд

(10)

2. при цьому задача має наступні обмеження:

обмеження по ресурсам

(11)

обмеження по потребам:

(12)

умови невід’ємності:

. (13)

Таким чином, розв’язання транспортної задачі зводиться до мінімізації цільової функції (10) для всіх x_ij , які задовольняють умовам (11)-(13).

Перейдемо до реалізації задачі в Excel, робочий лист з усією необхідною вхідною інформацією показано на рис.5.

Рис. 5

Створюється він наступним чином  в діапазон клітин B3:E5 в якості початкових значень попереднього розподілу запасів борошна на складах A, B, C між споживачами I, II, III, IV заносимо нулі. В діапазон клітин F3:F5 запаси борошна, що розміщені на складах A, B, C відповідно. В діапазон клітин B7:E7  потреби в борошні споживачів I, II, III, IV.

В клітину F6 заносимо контрольну суму об’ємів борошна, розміщеного на складах, тобто суму клітин F3:F5. В клітину F7 заносимо контрольну суму потреб в борошні всіх споживачів, тобто суму клітин B7:E7. Оскільки розглядається закрита модель транспортної задачі, то контрольні суми в клітинах F6 і F7 повинні співпадати.

В діапазоні клітин B11:E13 сформуємо матрицю вартостей (транспортних витрат) перевезень однієї тони борошна з кожного складу кожному споживачу.

Далі в клітину F15 заносимо формулу для розрахунку цільової функції, використовуючи вбудовану функцію =СУММПРОИЗВ(B11:E13;B3:E5). Обмеження задачі записуються в клітини F17:F23, в які вводяться функції, що відповідають лівим частинам обмежень (11), (12).

Для обмеження A заносимо в клітину F17 сумарну кількість борошна, яке буде перевезено зі складу A всім споживачам, використавши вбудовану функцію СУММ(B3:E3).

Для обмежень B, C зміст клітини F17 копіюється в клітини F18 і F19.

Для обмеження I заносимо в клітинку F20 сумарну кількість борошна, що постачається першому споживачу з усіх складів. Для цього виставляємо курсор в клітину F20 та вводимо формулу, яка має вигляд =СУММ(B3:B5).

Аналогічно заповнюються клітини F21:F23 для обмежень II, III, IV.

Результати представлені на рис.6.

Рис.6

Закінчивши складання робочого листа, запускаємо із меню Сервис команду Поиск решения. З’явиться діалогове вікно, яке зображено на рис.7.

Рис.7

В полі Установить целевую ячейку вказуємо адресу клітини, яка буде містити розв’язок задачі. В нашому випадку це клітинка F15.

В розділі Равной: вибираємо перемикач «минимальному значению», а в полі Изменяя ячейки  діапазон клітин $B$3:$E$5, значення в яких можуть змінюватися в процесі пошуку рішення (величини попереднього розподілу запасів борошна зі складів A, B, C між споживачами I, II, III, IV).

Щоб ввести обмеження задачі, натискаємо кнопку Добавить. При цьому відкривається діалогове вікно Добавление ограничения (рис.8).

Рис.8

Введемо перше обмеження:

$F$17=$F$3 , тобто сумарну кількість борошна яке буде перевезено зі складу A всім споживачам дорівнює запасу борошна, що розміщено на тому ж складі.

Аналогічним чином вводимо всі інші обмеження задачі:

$F$18=$F$4 ; $F$19=$F$5;

$F$20=$B$7; $F$21=$C$7;

$F$22=$D$7; $F$23=$E$7.

Кожен раз натискаючи в кінці введення обмеження кнопку Добавить, а в самому кінці кнопку ОК.

Для реалізації умови невід’ємності значень (13) в діалоговому вікні Поиск решения натискаємо клавішу Параметры і після появи ще одного діалогового вікна Параметры поиска решения (рис.9) вмикаємо прапорець Неотрицательные значения. Потрібно відмітити, що умови невід’ємності (13) можна також реалізувати у вигляді обмежень для діапазону клітин $B$3:$E$5>=0.

Рис.9

При натисненні кнопки Выполнить діалогового вікна Поиск решения з’являється діалогове вікно Результаты поиска решения (рис.10).

Рис.10

При необхідності з його допомогою можна сформувати звіти про хід рішення задачі (або відмовитись від них). Звіти передбачаються трьох типів: Результаты, Устойчивость, Пределы. Можна вибрати декілька типи звітів, виділивши їх за допомогою миші при натиснутій клавіші <Ctrl>. Кожен звіт буде створений на окремому робочому листі. В нашому випадку достатньо вибрати тип звіту  Результаты. Після натиснення кнопки ОК з’являється новий робочий лист із звітом про результати, а на робочому листі вихідна таблиця набуде вигляду, що показаний на рис.11.

Рис.11

Отримані результати дозволяють зробити наступні висновки:

При оптимальному плані перевезень (діапазон клітин В3:Е5) мінімальні сумарні витрати на перевезення борошна зі складів А, В, С до споживачів І, ІІ, ІІІ та ІV складуть 890 грн. (клітина F15). При цьому необхідно буде перевезти:

• зі складу А – 65 ц борошна споживачу ІV;

• зі складу В – 60 ц борошна споживачу ІІ та 20 ц борошна споживачу ІІІ;

• зі складу С – 45 ц борошна споживачу І та 60 ц борошна споживачу ІІІ.