Контрольная работа: Побудова економіко-математичної моделі розробки асортименту швейних виробів

Загальні витрати = 12·13 + 10·15 + 7·17 + 8·21 + 7·19 + 18·9 + 2·16 = 920 грн.

Стадія 3. Знаходження оптимального рішення

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

Метод послідовних кроків

Етапи процесу:

1.  Оберіть будь-яку пусту клітину та укажіть замкнений шлях, що веде до неї. Цей шлях складається з горизонтальних та вертикальних ліній, які ведуть від пустої клітини через інші назад до неї ж. В замкненому шляху може бути тільки одна пуста клітина – та, що розглядається. Повороти шляху на 90є можуть виконуватися лише в найближчих до пустої заповнених клітинах.

2.  Перемістіть одну одиницю із заповненої клітини у куті замкненого шляху в пусту клітину та приведіть інші заповнені клітини, що залишилися в інших кутах у відповідність до заданих потреб та поставок.

3.  Визначить доцільність здійсненого переміщення:

Σ витрат в клітинах, __ Σ витрат в клітинах, до яких була додана одиниця з яких була віднята одиниця

Якщо витрати в результаті переміщень скоротилися, то необхідно перемістити якомога більше одиниць з оціненої заповненої клітини в пусту. Якщо витрати збільшилися, то ніяких переміщень не виконують, а пусту клітину помічають, щоб більше до неї не повертатися.

4.  Повторювати етапи 1 – 3 доти, доки не будуть оцінені всі пусті клітини.

Максимальна кількість одиниць, яку можна додати до будь-якої клітини, не повинна перевищувати кількість, що вказана в клітині з найменшим значенням, з якої буде проводитися віднімання. Це необхідно для врахування обмежень щодо потреб та поставок.

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

Якщо оцінка пустої клітини дає в результаті таке саме значення, що і розподіл, який розглядається, значить існує рівноцінне альтернативне оптимальне рішення. (Зазвичай пусту клітину, визначену як альтернативний оптимальний маршрут, помічають 0.)

В транспортних задачах у випадках, 1) коли кількість заповнених клітин менше суми кількості рядків та стовпців мінус 1 (m+n-1) або 2) коли перше значення в рядку або стовпці задовольняє обмеженням як по рядку, так і по стовпцю, може спостерігатися явище виродження.

Тоді в будь-яку пусту клітину (або декілька) записується деяка кількість одиниць θ (зазвичай це 0) таким чином, щоб можна було скласти замкнений шлях для оцінки інших пустих клітин. Це значення залишається в задачі доти, поки воно не зникне при відніманні або до отримання остаточного рішення.

Оптимізація розподілу (метод північно-західного кута)

Страницы: 1, 2, 3, 4, 5, 6, 7