 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Раздел 2. Автоматизированное решение транспортной задачи линейного программирования
Второй раздел курсовой работы посвящён особенностям постановки и решения некоторой разновидности общей задачи линейного программирования, а именно, транспортной задаче (ТЗЛП).
Постановка и модель ТЗЛП:
Пусть имеется m пунктов отправления:
A1, A2,…Am, в которых сосредоточены запасы некоторых однородных грузов (товаров) в количестве a1,a2,…,am.
Имеется n пунктов назначения:
B1,B2,…,Bn, имеющих заявки на b1,b2,…,bn единиц грузов.
Предполагается, что сумма всех заявок равна сумме всех запасов:
Известна стоимость (Cij) перевозки единицы товара от каждого пункта отправления Ai до каждого пункта назначения Bj.
Матрица стоимостей выглядит следующим образом:
C11 C12 Cn
C21 C22 C2n
………………
Cm1 Cm2 Cmn
Требуется составить такой план перевозок, при котором все заявки были бы выполнены, и общая стоимость перевозок была бы минимальная.
При такой постановке показателем эффективности плана является стоимость, поэтому задача называется транспортной по критерию стоимости.
| Потребности филиалов | |||||||||||
| 18,4 | 16,4 | 16,2 | Bj | ||||||||
| Кол-во перевозок | |||||||||||
| Объем предложения | |||||||||||
| 1,6 | 5,4 | ||||||||||
| 11,4 | 17,4 | 16,2 | |||||||||
| Аi | 18,4 | 16,4 | 16,2 | ||||||||
| Объем спроса | |||||||||||
| 1,2 | 2,3 | 3,1 | 1,6 | 2,7 | Сij | ||||||
| 3,1 | 1,1 | 4,2 | 3,8 | 1,6 | |||||||
| 0,8 | 3,1 | 1,5 | 2,1 | 4,5 | Удельные затраты | ||||||
| 2,9 | 3,7 | 4,3 | 2,8 | ||||||||
| 3,1 | 3,6 | 5,2 | 2,6 | ||||||||
| 3,4 | 2,8 | 4,1 | 3,7 | ||||||||
| 4,8 | 5,6 | 6,7 | 4,5 | 5,8 | |||||||
| Целевая ячейка - | |||||||||||
| стоимость перевозки |
Отчет о результатах.
| Ячейка целевой функции (Минимум) | ||||||
| Ячейка | Имя | Исх. Знач. | Окончательное значение | |||
| $D$27 | Потребности филиалов | 338,98 | ||||
| Ячейки переменных | ||||||
| Ячейка | Имя | Исх. Знач. | Оконч. Знач. | Целочисленное | ||
| $D$4 | Потребности филиалов | Продолжить | ||||
| $E$4 | Кол-во перевозок | Продолжить | ||||
| $F$4 | Продолжить | |||||
| $G$4 | Продолжить | |||||
| $H$4 | Продолжить | |||||
| $D$5 | Потребности филиалов | Продолжить | ||||
| $E$5 | Кол-во перевозок | Продолжить | ||||
| $F$5 | Продолжить | |||||
| $G$5 | Продолжить | |||||
| $H$5 | Продолжить | |||||
| $D$6 | Потребности филиалов | Продолжить | ||||
| $E$6 | Кол-во перевозок | Продолжить | ||||
| $F$6 | Продолжить | |||||
| $G$6 | Продолжить | |||||
| $H$6 | Продолжить | |||||
| Ограничения | ||||||
| Ячейка | Имя | Значение ячейки | Формула | Состояние | Допуск | |
| $B$10 | $B$10=$J$10 | Привязка | ||||
| $B$4 | $B$4=$J$4 | Привязка | ||||
| $B$5 | $B$5=$J$5 | Привязка | ||||
| $B$6 | $B$6=$J$6 | Привязка | ||||
| $B$7 | $B$7=$J$7 | Привязка | ||||
| $B$8 | $B$8=$J$8 | Привязка | ||||
| $B$9 | $B$9=$J$9 | Привязка | ||||
| $D$2 | Потребности филиалов | 18,4 | $D$2=$D$13 | Привязка | ||
| $E$2 | $E$2=$E$13 | Привязка | ||||
| $F$2 | 16,4 | $F$2=$F$13 | Привязка | |||
| $G$2 | 16,2 | $G$2=$G$13 | Привязка | |||
| $H$2 | $H$2=$H$13 | Привязка |
Отчет о пределах.
| Целевая функция | |||||||
| Ячейка | Имя | Значение | |||||
| $D$27 | Потребности филиалов | ||||||
| Переменная | Нижний | Цел. Функц. | Верхн. | Цел. Функц. | |||
| Ячейка | Имя | Знач. | Предел | Результ. | Предел | Результат | |
| $D$4 | Потребности филиалов | 338,98 | 338,98 | ||||
| $E$4 | Кол-во перевозок | 338,98 | 338,98 | ||||
| $F$4 | 338,98 | 338,98 | |||||
| $G$4 | 338,98 | 338,98 | |||||
| $H$4 | 338,98 | 338,98 | |||||
| $D$5 | Потребности филиалов | 338,98 | 338,98 | ||||
| $E$5 | Кол-во перевозок | 338,98 | 338,98 | ||||
| $F$5 | 338,98 | 338,98 | |||||
| $G$5 | 338,98 | 338,98 | |||||
| $H$5 | 338,98 | 338,98 | |||||
| $D$6 | Потребности филиалов | 338,98 | 338,98 | ||||
| $E$6 | Кол-во перевозок | 338,98 | 338,98 | ||||
| $F$6 | 338,98 | 338,98 | |||||
| $G$6 | 338,98 | 338,98 | |||||
| $H$6 | 338,98 | 338,98 |
Отчет об устойчивости
| Ячейки переменных | |||||||
| Оконч. | Приведенн. | Целевая функ. | Допустимое | Допустимое | |||
| Ячейка | Имя | Знач. | Стоимость | Коэфф. | Увеличение | Уменьшение | |
| $D$4 | Потребности филиалов | 1,2 | 0,3 | 1E+30 | |||
| $E$4 | Кол-во перевозок | 0,3 | 2,3 | 1E+30 | 0,3 | ||
| $F$4 | 0,3 | 3,1 | 1E+30 | 0,3 | |||
| $G$4 | 0,7 | 1,6 | 1E+30 | 0,7 | |||
| $H$4 | 0,8 | 2,7 | 1E+30 | 0,8 | |||
| $D$5 | Потребности филиалов | 2,8 | 3,1 | 1E+30 | 2,8 | ||
| $E$5 | Кол-во перевозок | 1,1 | 0,6 | 1E+30 | |||
| $F$5 | 2,3 | 4,2 | 1E+30 | 2,3 | |||
| $G$5 | 3,8 | 3,8 | 1E+30 | 3,8 | |||
| $H$5 | 0,6 | 1,6 | 1E+30 | 0,6 | |||
| $D$6 | Потребности филиалов | 0,9 | 0,8 | 1E+30 | 0,9 | ||
| $E$6 | Кол-во перевозок | 2,4 | 3,1 | 1E+30 | 2,4 | ||
| $F$6 | 1,5 | 0,9 | 1E+30 | ||||
| $G$6 | 2,5 | 2,1 | 1E+30 | 2,5 | |||
| $H$6 | 3,9 | 4,5 | 1E+30 | 3,9 | |||
| Ограничения | |||||||
| Окончательное | Тень | Ограничение | Допустимое | Допустимое | |||
| Ячейка | Имя | Значение | Цена | Прав. сторона | Увеличение | Уменьшение | |
| $B$10 | -2,9 | 3,553E-15 | 1,6 | ||||
| $B$4 | 0,7 | 3,553E-15 | 1,6 | ||||
| $B$5 | 1,6 | 3,553E-15 | 1,6 | ||||
| $B$6 | 3,553E-15 | 5,4 | |||||
| $B$7 | -0,2 | 3,553E-15 | |||||
| $B$8 | 1E+30 | 3,5527E-15 | |||||
| $B$9 | -0,1 | 3,553E-15 | 1,6 | ||||
| $D$2 | Потребности филиалов | 18,4 | -1,9 | 1,6 | 3,5527E-15 | ||
| $E$2 | -2,7 | 1,6 | 3,5527E-15 | ||||
| $F$2 | 16,4 | -3,5 | 5,4 | 3,5527E-15 | |||
| $G$2 | 16,2 | -1,6 | 1,6 | 3,5527E-15 | |||
| $H$2 | -2,6 | 3,5527E-15 |
Транспортные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. В общей постановке транспортная задача состоит в поиске оптимального плана перевозок некоторого однородного груза с баз потребителям.
Решая транспортную задачу, сначала мы находили объем спроса с помощью встроенной функции СУММ и объем предложения – СУММ по количеству перевозок. Затем в целевую ячейку заносим формулу для вычисления целевой функции СУММПРОИЗВ.
С помощью решения транспортной задачи мы можем найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение для минимизации затрат.
Поиск по сайту: