В предыдущем параграфе мы описали некоторые общие подходы к решению задач линейного программирования. Однако существуют частные типы задач линейного программирования, которые, в силу особой своей структуры, допускают решение более простыми методами. Она ставится следующим образом: Имеются пунктов назначения ПН , подавших заявки соответственно на единиц груза. Сумма всех заявок равна сумме всех запасов: Известны стоимости перевозки единицы груза от каждого пункта отправления до каждого пункта назначения. Все числа образующие прямоугольную таблицу матрицу , заданы: Считается, что стоимость перевозки нескольких единиц груза пропорциональна их числу. Требуется составить такой план перевозок откуда, куда и сколько единиц везти , чтобы все заявки были выполнены, а общая стоимость всех перевозок минимальна. Поставим эту задачу как задачу линейного программирования. Обозначим — количество единиц груза, отправляемого из. Неотрицательные переменные тоже можно записать в виде матрицы которую мы будем коротко обозначать Совокупность чисел Эти неотрицательные переменные должны удовлетворять следующим условиям. Суммарное количество груза, направляемого из каждого ПО во все ПН, должно быть равно запасу груза в данном пункте. Это даст нам условий-равенств: Суммарное количество груза, доставляемого в каждый ПН из всех ПО, должно быть равно заявке, поданной данным пунктом. Суммарная стоимость всех перевозок, то есть сумма величин умноженных на соответствующие стоимости должна быть минимальной: Мы видим, что перед нами — задача линейного программирования с условиями-равенствами Особенностью этой задачи является то, что все коэффициенты в условиях О них и пойдет речь. Прежде всего, замечаем, что условия-равенства Число линейно независимых среди уравнений Значит, в нашем случае для оптимального плана по крайней мере перевозок должны быть равны нулю из соответствующих ПО в соответствующие ПН ничего не перевозится. Будем называть любой план перевозок допустимым, если он удовлетворяет условиям Допустимый план будем называть опорным, если в нем отличны от нуля не более базисных перевозок, а остальные перевозки равны нулю. План будем называть оптимальным, если он, среди всех допустимых планов, приводит к минимальной суммарной стоимости перевозок. В силу особой структуры ТЗ при ее решении не приходится долго и нудно разрешать и переразрешать систему уравнений. Все операции по нахождению оптимального плана сводятся к манипуляциям непосредственно с таблицей, где в определенном порядке записаны условия транспортной задачи: В правом верхнем углу каждой клетки мы будем ставить стоимость перевозки единицы груза из а центр клетки оставим свободным, чтобы помещать в нее саму перевозку Клетку таблицы, соответствующую пунктам будем кратко обозначать Пример транспортной таблицы, где приведены условия задачи и стоимости перевозок, но нет еще самих перевозок, дан в таблице Прежде всего займемся составлением опорного плана. Это в транспортной задаче очень просто: Продемонстрируем его непосредственно на конкретных данных таблицы Пункт подал заявку на 18 единиц груза; удовлетворим ее из запасов пункта Таблица Но заявка этого пункта еще не удовлетворена; выделим недостающие 15 единиц из запасов пункта и т. Рассуждая точно таким же образом, заполним до конца перевозками транспортную таблицу таблица Проверим, является ли этот план допустимым: Проверим, является ли план перевозок, данный в таблице Число свободных клеток с нулевыми перевозками в таблице Вот как нам его удалось легко построить! Скорее всего, нет ведь составляя опорный план, мы совсем не думали о стоимостях. Так и есть —план не оптимальный. Чтобы план оставался опорным, мы должны при этом сделать одну из свободных клеток базисной, а одну из базисных — свободной. Сколько единиц груза можем мы перенести по циклу , увеличивая перевозки в нечетных вершинах цикла и уменьшая — в четных? Очевидно, не больше, чем И единиц иначе перевозки в клетке 3. Очевидно, в результате циклического переноса допустимый план остается допустимым — баланс запасов и заявок не нарушается. Ну что же, произведем этот перенос и запишем новый, улучшенный план перевозок в таблице Теперь посмотрим, чего мы добились, сколько сэкономили? Общая стоимость плана, показанного в таблице Это, впрочем, можно было предсказать и не подсчитывая полную стоимость плана. Значит, при переносе одной единицы груза по этому циклу стоимость перевозок уменьшается на четыре. В теории линейного программирования доказывается, что при опорном плане для каждой свободной клетки транспортной таблицы существует цикл, и притом единственный, одна вершина которого первая лежит в данной свободной клетке, а остальные — в базисных клетках. Если такая клетка есть, нужно для нее найти цикл, вычислить его цену и, если она будет отрицательной, перенести по этому циклу столько единиц груза, сколько будет возможно без того, чтобы какие-то перевозки сделать отрицательными. При этом данная свободная клетка становится базисной, а какая-то из бывших базисных — свободной. Попробуем еще раз улучшить план, приведенный в таблице Нельзя ли улучшить план, увеличив перевозки в этой клетке, зато уменьшив в других при этом, конечно, придется кое-где перевозки тоже увеличить. Давайте разглядим внимательно таблицу Немного подумав, мы этот цикл обнаружим: Нечетные вершины цикла отмечены плюсом — это значит, что перевозки в этих клетках увеличиваются: Цикл показан стрелками в таблице Подсчитаем цену этого цикла. Так как цена цикла отрицательна, то переброска перевозок по этому циклу выгодна. Посмотрим, сколько же единиц мы можем по нему перебросить? Это определяется наименьшей перевозкой, стоящей в отрицательной вершине цикла. В данном случае это опять 11 чистое совпадение! Умножая 11 на цену цикла — 5 получим, что за счет переброски 11 единиц груза по данному циклу мы еще уменьшим стоимость перевозок на 55 предоставляем любознательному читателю сделать это самостоятельно. Таким образом, разыскивая в транспортной таблице свободные клетки с отрицательной ценой цикла и перебрасывая по этому циклу наибольшее возможное количество груза, мы будем все уменьшать и уменьшать стоимость перевозок. Для такого плана уже не остается ни одной свободной клетки с отрицательной ценой цикла. Это — признак того, что оптимальное решение найдено. Если сумма запасов больше суммы заявок , то все заявки могут быть удовлетворены, но при этом не все запасы будут израсходованы. Тогда задача сводится к задаче с правильным балансом, так как Возникает вопрос: Естественно положить их равными нулю ведь фактически в пункт ничего перевозиться не будет! Поэтому для любого пункта отправления стоимость Введем в транспортную таблицу дополнительный столбец, соответствующий пункту назначения и проставим в нем нулевые стоимости перевозок. После этого задача решается как обычная транспортная, и для нее находится оптимальный план перевозок: Математические модели операций ГЛАВА 2. Прямые и обратные задачи исследования операций. Многокритериальные задачи исследования операций. Понятие о нелинейном программировании ГЛАВА 4. Примеры решения задач динамического программирования 1. Прокладка наивыгоднейшего пути между двумя пунктами. Задача о распределении ресурсов 3. Задача о загрузке машины. Задача динамического программирования в общем виде. Принцип оптимальности ГЛАВА 5. Уравнения Колмогорова для вероятностей состояний. Финальные вероятности состояний ГЛАВА 6. Задачи теории массового обслуживания. Схема гибели и размножения. Простейшие системы массового обслуживания и их характеристики 2. Одноканальная СМО с неограниченной очередью. Одноканальная СМО с ограниченной очередью. Замкнутая СМО с одним каналом и m источниками заявок. Более сложные задачи теории массового обслуживания ГЛАВА 7. Определение характеристик стационарного случайного процесса по одной реализации ГЛАВА 8. Транспортная задача линейного программирования В предыдущем параграфе мы описали некоторые общие подходы к решению задач линейного программирования. Общее число переменных в нашей задаче равно как бы ни разрешать уравнения
Транспортная задача линейного программирования получила в настоящее время широкое распространение в теоретических разработках и практическом применении на транспорте ив промышленности. Особенно большое значение она имеет в деле рационализации поставок важнейших видов промышленной и сельскохозяйственной продукции, а также оптимального планирования грузопотоков и работы различных видов транспорта. Транспортная задача — это задача, в которой работы и ресурсы измеряются в одних и тех же единицах. В таких задачах ресурсы могут быть разделены между работами, и отдельные работы могут быть выполнены с помощью различных комбинаций ресурсов. Примером типичной транспортной задачи является распределение транспортировка продукции, находящейся на складах, по предприятиям-потребителям. Стандартная ТЗ определяется как задача разработки наиболее экономичного плана перевозки продукции одного вида из нескольких пунктов отправления в пункты назначения. При этом величина транспортных расходов прямо пропорциональна объему перевозимой продукции и задается с помощью тарифов на перевозку единицы продукции. Три поставщика одного и того же продукта располагают в планируемый период следующими запасами этого продукта: Этот продукт должен быть перевезен к трем потребителям, спросы которых соответственно равны 90, 90 и условных единиц. Приведенная ниже таблица содержит показатели затрат, связанных с перевозкой продукта из i -го пункта отправления в j -й пункт потребления. Пусть —I поставщиком, А-му потребителю, тогда , — количество единиц продукта перевозимого этим же поставщиком Б-му и В-му потребителю соответственно. Целевая функция в этом случае имеет вид: При следующих ограничениях первые три ограничения — по запасам продуктов, последние три — по спросу потребителей:. Вид электронной таблицы Excel, созданной для решения задачи, в режиме отображения формул, представлен на рис. Искомые значения находятся в блоке ячеек B4: Требования к ограничениям по спросу и запасам представлены соответственно в ячейках B7: Коэффициенты ЦФ, означающие затраты на доставку расположены в блоке ячеек B Формулы целевой функции и ограничений находятся соответственно в ячейке F8 и ячейках B8: D8 ограничения по спросу , F4: F6 ограничения по запасам. Данная задача является сбалансированной, в ней общее наличие продукта у поставщиков равно общей потребности в продукте потребителей. На практике возможны случаи, когда эти параметры не совпадают. Тогда в рассмотрение вводятся фиктивная фабрика или фиктивный магазин, которые позволяют свести задачу к сбалансированной. Методом транспортной задачи решаются экономические задачи, которые по своему характеру не имеют ничего общего с транспортировкой груза, поэтому коэффициенты целевой функции могут иметь различный смысл в зависимости от конкретной задачи. Они могут означать стоимость, расстояние время, производительность и т. Рассмотрим постановку и математические модели некоторых задач. Три типа самолетов требуется распределить между четырьмя авиалиниями. В приводимых ниже таблицах задано число самолетов каждого типа, месячный объем перевозок каждым самолетом на каждой авиалинии и соответствующие эксплуатационные расходы. Требуется распределить самолеты по авиалиниям так, чтобы при минимальных суммарных эксплуатационных расходах перевезти по каждой из четырех авиалиний соответственно не менее , , и единиц груза. Значения переменных располагаются в блоке ячеек B Коэффициенты целевой функции, отражающие расходы на перевозку находятся по адресам B Данные о месячных объемах перевозок одним самолетом имеются в блоке B Задан план перевозок и число самолетов — соответственно блоки B Формулы целевой функции и ограничений находятся соответственно в ячейке F25 и ячейках B E25 ограничения по плану , F F23 ограничения по количеству самолетов. Результаты поиска решения приведены на рис. Имеются три механизма М1, М2, М3, каждый из которых может быть использован на трех видах работ Р1, Р2, Р3 с производительностью в условных единицах , заданной в виде таблицы:. Требуется так распределить механизмы по одному на каждую из работ, чтобы суммарная производительность всех механизмов была максимальной. Значения переменных x ij располагаются в блоке ячеек B Коэффициенты целевой функции, отражающие производительность механизмов, находятся по адресам B Формулы целевой функции и ограничений находятся соответственно в ячейке E49 и ячейках E E47 каждый механизм может быть назначен только на одну работу , B D49 каждая работа выполняется только на одном механизме. Данная задача является задачей линейного булева программирования и в ней переменные x ij должны принимать значения либо 0 либо 1. В поиске решения такое ограничение задается тремя ограничениями, по которым изменяемые ячейки в блоке x ij одновременно больше либо равны 0, меньше либо равны 1 и являются целыми. Решить транспортную задачу согласно номера варианта номера компьютера в аудитории , условие задачи и результаты расчёта записать в отчёт по лабораторной работе. В машину необходимо поместить четыре вида предметов, причем могут потребоваться несколько одинаковых предметов. Имеется три вида ограничений такого типа, как вес, объем и т. В приведенной ниже таблице даны — i -я характеристика предмета j -го наименования, c j - полезность одного предмета j-го наименования. Требуется загрузить машину так, чтобы суммарная полезность груза была максимальной. Целевая функция имеет вид: Значения переменных x ij располагаются в блоке ячеек B4: Коэффициенты целевой функции, отражающие полезности предметов находятся по адресам B7: Данные о характеристиках предметов имеются в блоке B Заданы значения ограничений- соответственно блок H Формулы целевой функции и ограничений находятся соответственно в ячейке F7 и ячейках F E12 ограничения по свойствам. Фирма обслуживает 5 клиентов. Каждый день она доставляет своим клиентам товары на грузовых машинах. Существует 3 допустимых маршрута доставки, каждый из которых позволяет обслужить определенное количество клиентов и требует использования в течении дня одного транспортного средства. Каждый маршрут характеризуется определенными расходами см. Необходимо выбрать такое множество маршрутов, при котором обеспечивается обслуживание каждого из клиентов и, кроме того, суммарные расходы минимальны, при условии, что каждый клиент обслуживается один раз в день. Четыре предприятия данного экономического района для производства продукции используют три вида сырья. Потребности в сырье каждого из предприятий соответственно равны , 50, и ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны , и ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей. Составить такой план перевозок, при котором общая стоимость перевозок является минимальной. Для строительства трех объектов используется кирпич, изготовляемый на трех заводах. Ежедневно каждый из заводов может изготовлять , и 50 ус. Ежедневные потребности в кирпиче на каждом из строящихся объектов соответственно равны 75, 80, 60 и 85 усл. Известны также тарифы перевозок 1 усл. Составить такой план перевозок кирпича, при котором общая стоимость перевозок является минимальной. Дано распределения самолетов трех типов по четырем маршрутам. Характеристики парка самолетов и движения по авиалиниям приведены в таблице. Убыток от неудовлетворенного спроса на одного неперевезенного пассажира. Необходимо так распределить самолеты по авиалиниям, чтобы суммарные эксплуатационные расходы были минимальны. Парк самолетов используется для перевозки пассажиров на пяти авиалиниях, по каждой из них задан объем ежемесячных перевозок. Постройте оптимальный план перевозок пассажиров. Объемы запасов семян, объемы заказов на поставку и тарифы на перевозку приведены в транспортной таблице. Запас кассет, имеющихся на складах, а также объемы заказов магазинов и тарифы на доставку представлены в транспортной таблице. Каждая упаковка содержит 12 банок емкостью 0,33 литра. Тарифы на доставку товара, объемы запасов и заказы на продукцию приведены в таблице. Определите оптимальный план поставок газированных напитков в супермаркеты города, а также затраты на перевозку. Объемы запасов шин на складах, объемы заявок магазинов и тарифы на перевозку приведены в транспортной таблице. Самара — 80 кг, Москва — кг, Ростов-на-Дону — кг, Санкт-Петербург — кг. Нижний Новгород — кг. Определите минимальную стоимость фрахта специализированного транспорта, обеспечивающую полное удовлетворение заявок покупателей, при заданной матрице тарифов. Составьте оптимальный план перевозки автомобилей из городов Ижевск, Казань, Тольятти в города Москва, Саранск и Ульяновск. Стоимость перевозки одного автомобиля составляет 10 руб. Расстояние между городами, объемы заявок и заказов представлены в таблице. Составьте оптимальный план перевозки лекарств с минимальными затратами из аптечных складов в пять аптек города: Запасы лекарств на складах, заявки потребителей и тарифы перевозок представлены в таблице. Составьте оптимальный план перевозки угля с минимальными транспортными расходами с шахт Варгашорская В. Западная 3 и Комсомольская К , еженедельно добывающих соответственно 26, 32 и 17 тыс. Покупатели угля расположены в разных городах А, В, С и D, заявки которых составляют 28,19,12 и 16 тыс. Тарифы определяет стоимость перевозки 1 тыс. А, В, С, D. Заказы на поставку хлебобулочных изделий, производительность пекарен и транспортные тарифы представлены в транспортной таблице. FAQ Обратная связь Вопросы и предложения. Upload Опубликованный материал нарушает ваши авторские права? Планирование производства использования сырья. Транспортная задача линейного программирования Цель работы: Изучение видов транспортной задачи и методов её решения. Изучение видов распределительной задачи и методов её решения. Требуется перевезти продукт с минимальными затратами. Поставщики Потребители и их спрос Запасы А Б В I 7 6 4 II 3 8 5 III 2 3 7 80 Спрос 90 90 1 Составим математическую модель задачи. При следующих ограничениях первые три ограничения — по запасам продуктов, последние три — по спросу потребителей: Тип самолета Число самолетов Месячный объем перевозок одним самолетом по авиалиниям I II III IV 1 50 15 10 20 50 2 20 30 25 10 17 3 30 25 50 30 45 Тип самолета Эксплуатационные расходы I II III IV 1 15 20 25 40 2 70 28 15 45 3 40 70 40 65 Математическая модель задачи выглядит следующим образом. Имеются три механизма М1, М2, М3, каждый из которых может быть использован на трех видах работ Р1, Р2, Р3 с производительностью в условных единицах , заданной в виде таблицы: Механизмы Работы Р1 Р2 Р3 М1 1 2 3 М2 2 4 1 М3 3 1 5 Требуется так распределить механизмы по одному на каждую из работ, чтобы суммарная производительность всех механизмов была максимальной. D49 каждая работа выполняется только на одном механизме Рис. Задание Решить транспортную задачу согласно номера варианта номера компьютера в аудитории , условие задачи и результаты расчёта записать в отчёт по лабораторной работе. Ограничения Предмет1 Предмет2 Предмет3 Предмет4 Значения ограничений I 3 3 5 2 II 4 2 4 4 III 3 5 4 3 Полезность 3 4 3 3 Математическая модель задачи выглядит следующим образом. Таблица обслуживания клиентов по маршрутам Клиенты Маршруты 1 2 3 1 1 1 2 1 3 1 1 4 1 5 1 1 Расходы по маршруту Целевая функция имеет вид: Тарифы перевозок являются известными величинами и задаются матрицей Составить такой план перевозок, при котором общая стоимость перевозок является минимальной. Тип самолета Загрузка пассажирами Время полета без посадки, ч Парк самолетов, шт. ТУ 68 76 7 25 2. ТУ 4 10 3. ИЛ 12 10 4. ИЛ 5 12 5. ИЛ — 10 4 6. В — 12 3 7. В — 22 2 8. А 12 4 Парк самолетов используется для перевозки пассажиров на пяти авиалиниях, по каждой из них задан объем ежемесячных перевозок. Рейс Протяженность линий, ч т Количество промежуточных посадок Объем пассажирских перевозок, чел. Египет - Хургада 5,5 0 II. Испания - Малага 4,5 0 III. Япония - Токио 11 2 IV. Франция - Париж 3,5 1 V. США - Нью-Йорк 9 2 Вариант 7. Филиалы Заводы Запасы,т А В С D Е Ф1 7 9 15 4 18 Ф2 13 12 8 15 5 Ф3 5 14 6 20 12 Заявки,тонн Постройте оптимальный план перевозки подсолнечных семян с минимальными транспортными расходами Вариант 8. Склады Магазины Запасы, тыс. Склады в городах Магазины Запасы Чебоксары Нижний Новгород Вязники Набережные Челны Казань Москва 14 8 6 20 16 Нижний Новгород 6 1 2 12 8 Покров 12 6 4 18 14 Заявки Составьте оптимальный план, обеспечивающий минимальные транспортные расходы перевозок. Города Города Запасы, шт. Москва Саранск Ульяновск Ижевск 20 Казань 65 Тольятти 80 Заказы, шт. Шахты Потребители Добыча угля, тыс. Название работы Цель работы Содержание работы Задания без таблиц Выводы по работе 0. Месячный объем перевозок одним самолетом по авиалиниям. Таблица обслуживания клиентов по маршрутам. Количество рейсов в сутки на каждом маршруте.
https://gist.github.com/77c143f39aaabea2f562b46206ac03b6
https://gist.github.com/a196fc632ba06bc0cc95b7ac1c96700a
https://gist.github.com/87a4dd76f416027e429e3c074f5bc6c2