Industrialnet Головна Про сайт webcache.site checkip.site takescreenshot.site
  • Строрінки

  • Транспортна задача. Математична модель [1 ч.]

    Лінійне програмування

  • Математичні моделі задач лінійного програмування
  • Симплексний метод розв'язання задач лінійного програмування
  • Транспортна задача. Математична модель [1 ч.]
  • Транспортна задача. Опорне рішення [2 ч.]. Метод північно-західного кута
  • Лекції з Вищої математики
  • Симплексний метод розв'язання задач лінійного програмування
  • Ймовірність події
  • Зміст
  • Загальна характеристика транспортної задачі
  • Математична модель транспортної задачі
  • Під назвою " транспортна задача об'єднується широке коло завдань з єдиною матетической моделлю. Дані задачі відносяться до задач лінійного програмування і можуть бути вирішені відомим симплексним методом. Однак, звичайна транспортна задача має велику кількість змінних і рішення її симплексним методом громозко. З іншого боку матриця системи обмежень транспортної задачі вельми своєрідна, тому для її вирішення розроблено спеціальні методи. Ці методи, як і симплексний метод, дозволяють знайти початкове опорне рішення, а потім, покращуючи його, отримати послідовність опорних рішень, яка завершується оптимальним рішенням.

    Загальна характеристика транспортної задачі

    Умова:
    Однорідний вантаж зосереджений у m постачальників в обсягах a1, a2, ... am.
    Даний вантаж необхідно доставити n споживачам в обсягах b1, b2 ... bn.
    Відомі Cij , i=1,2,...m; j=1,2,...n — вартості перевезення одиниць вантажу від кожного i-го постачальника кожному j-му споживачеві.
    Потрібно скласти такий план перевезень, при якому запаси всіх постачальників вивозяться повністю, запити всіх споживачів задовольняються повністю, і сумарні витрати на перевезення всіх вантажів є мінімальними.

    Вихідні дані транспортної задачі записуються у вигляді таблиці:

    Вихідні дані завдання можуть бути представлені у вигляді:

  • вектора А=(a1,a2,...,am) запасів постачальників
  • вектора B=(b1,b2,...,bn) запитів споживачів
  • матриці вартостей:
  • Математична модель транспортної задачі

    Змінними (невідомими) транспортної задачі є xij , i=1,2,...,m j=1,2,...,n — обсяги перевезень від i-го постачальника кожному j-му споживачеві.
    Ці змінні можуть бути записані у вигляді матриці перевезень:

    Так як твір Cij*Xij визначає витрати на перевезення вантажу від і-го постачальника j-му споживачеві, то сумарні витрати на перевезення всіх вантажів рівні:

    За умовою задачі потрібно забезпечити мінімум сумарних витрат.
    Отже, цільова функція задачі має вигляд:

    Система обмежень задачі складається з двох груп рівнянь.
    Перша група з m рівнянь описує той факт, що запаси всіх m постачальників вивозяться повністю і має вигляд:

    Друга група з n рівнянь висловлює вимога задовольнити запити всіх n споживачів повністю і має вигляд:

    Враховуючи умову неотрицательности обсягів перевезень математична модель виглядає наступним чином:

    У розглянутій моделі транспортної задачі передбачається, що сумарні запаси постачальників рівні суммарынм запитам споживачів, тобто:

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

    Математичне формулювання транспортної задачі така: знайти змінні задачі X=(xij), i=1,2,...,m; j=1,2,...,n, задовольняють системі обмежень (цифра 2 на математичній моделі) , (3), умов неотрицательности (4) і забезпечують мінімум цільової функції (1)

    Приклад 34.1

    Скласти математичну модель транспортної задачі, вихідні дані якої наведені в таблиці 34.2

    Рішення:
    1. Вводимо змінні завдання (матрицю перевезень):

    2. Записуємо матрицю вартостей:

    3. Цільова функція задачі дорівнює сумі добутків всіх відповідних елементів матриць C і X.

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

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

    Це означає, що запаси постачальників вивозяться повністю.

    Суми перевезень, що стоять у кожному стовпці матриці X, повинні бути рівні запитами відповідних споживачів:

    Це означає, що запити споживачів задовольняються повністю.

    Необхідно також враховувати, що перевезення не можуть бути негативними:

    Відповідь: Таким чином, математична модель даної задачі записується наступним чином:
    Знайти змінні завдання, що забезпечують мінімум цільової функції (1) і задовольняють системі обмежень (2) і умов неотрицательности (3).

    Copyright © industrialnet.com.ua. 2016 • All rights reserved.