ustify"> Microsoft Excel 12.0 Звіт по устойчівостіРабочій лист: [Стариков ЕММ - решеніе.xlsx] Завдання лінійного программірованОтчет створено: 01.10.2012 17: 07: 48Ізменяемие ячейкиРезульт.Нормир.ЯчейкаИмязначениеградиент$B$10оптимальные значення х1 * 100 $ C $ 10оптімальние значення х2*0-3ОграниченияРезульт.ЛагранжаЯчейкаИмязначениеМножитель$D$5коэф в 1 обмеженні ліва часть203,5 $ D $ 6коеф під 2 обмеженні ліва часть100 $ D $ 7коеф в 3 обмеженні ліва часть200
3. Транспортна задача
На трьох складах А 1, А 2 і А 3 зберігається а 1=100, а 2=200, а 3=60 + 10n одиниць одного і того ж вантажу, відповідно. Цей вантаж потрібно доставити трьом споживачам В 1, В 2 і В 3, замовлення яких b 1=190, b 2=120, b 3=10m одиниць вантажу, відповідно. Вартості перевезень c ij одиниці вантажу з i-го складу j-му споживачеві вказані у відповідних клітинах транспортної таблиці:
Таблиця 3
Потреби запасів 1 У 2 У 3 b 1=190b 2=120b 3=500А 1 а 1=100425А 2 а 2=200253А 3 а 3=260166
. Порівнюючи сумарний запас і сумарну потребу у вантажі, встановити, чи є модель транспортної задачі відкритою або закритою. Якщо модель відкрита, то її необхідно закрити, додавши фіктивний склад А 4 із запасом а 4=b-а у випадку а lt; b або фіктивного споживача В 4 з потребою b 4=ab у випадку а gt; b і поклавши відповідні їм тарифи перевезень нульовими.
. Скласти початковий план перевезень методом північно-західного кута і методом найменшої вартості.
. Методом потенціалів перевірити початковий план перевезень на оптимальність в сенсі сумарної вартості перевезень, і якщо це не так, то скласти оптимальний план
,
забезпечує мінімальну вартість перевезень. Знайти цю вартість.
. Вирішити завдання в MS Excel в режимі «пошук рішення». Відповіді, отримані в результаті рішень «вручну» і за допомогою Excel, повинні збігатися.
Рішення:
Потреба=190 + 120 + 500=810
Можливості=100 + 200 + 260=560
Таким чином, дана транспортна задача (ТЗ) - відкрита.
Отже для вирішення такого завдання необхідно ввести фіктивного постачальника - А4, що має запаси вантажу рівні 250 одиниць, тим самим ми збалансували попит та пропозиція (таблиця 4).
Таблиця 4
ПоставщікПотребітельЗапаси грузаВ1В2В3А1425100А2253200А3166260А4000250Потребность190120500810
Складемо початковий план за методом північно-західного кута (таблиця 5).
Таблиця 5
ПоставщікПотребітельЗапаси грузаВ1В2В3А1100 425100А290 +2110 53200А3110 +6250 6260А400250 0250Потребность190120500810 + m - 1=4 + 3-1=6 - відповідає числу заповнених клітин
Загальні транспортні витрати дорівнюють:
Z 1=100 * 4 + 90 * 2 + 110 * 5 + 10 * 6 + 250 * + 250 * 0=400 + 180 + 550 + 60 + 1500 + 0=2690
Перевіримо складений план на оптимальність методом потенціалів.
Розрахуємо потенціали, виходячи з того, що потенціал рядки А1=0 (таблиця 6).
Таблиця 6
ПоставщікПотребітельЗапаси грузаВ1В2В3А1100 425100U1=0А290 2110 53200U2=- 2А3110 +6250 6260U3=- 1А400250 0250U4=- 7Потребность190120500810V1=4V2=7V3=7
Далі, розрахуємо тіньові ціни (таблиця 7 - тіньові ціни виділені сірим кольором).
Таблиця 7
ПоставщікПотребітельЗапаси грузаВ1В2В3А1100 4 - - 5 2 + - 2 5100U1=0А290 2 +110 5 - - 2 3200U2=- 2А3-2 110 6250 6260U3=- 1А43 00 +0250 0250U4=- 7Потребность190120500810V1=4V2=7V3 =7
Наявність тіньових цін означає не оптимальність наявного плану, отже, для поліпшення плану намічаємо маршрут з найменшою негативною тіньової ціною і для цього маршруту визначаємо цикл перерозподілу. Обсяг перевезеного вантажу чисельно дорівнює мінімальному значенню з тих обсягів вантажу, які вказані в клітинах зі знаком мінус. Таким чином, min (100; 110)=100.
Отже, складаємо новий план (таблиця 8).
Даний цикл триває до тих пір, поки всі тіньові ціни не стануть позитивними.
Таблиця 8
ПоставщікПотребітельЗапаси грузаВ1В2В3А15 4100 23 5100U1=0А2190 2 - 10 5+ - 2 3200U2=3А3-2 1 +10 6 - 250 6260U3=4А43 00 +0250 0250U4=- 2Потребность190120500810V1=- 1V2=2V3=2 + m - 1=4 + 3-1=6 - відповідає числу заповнених клітин
Загальні транспортні витрати дорівнюють:
Z 2=190 * 2 + 100 * 2 + 10 * 5 + 10 * 6 + 250 * 6 + 250 * 0=380 + 200 + 50 + 60 + 1500 + 0=2190
Таблиця 9
