Транспортная задача - Линейное программирование
Одна из наиболее распространенных задач математического программирования -- транспортная задача. В общем виде ее можно представить так: требуется найти такой план доставки грузов от поставщиков к потребителям, чтобы стоимость перевозки (или суммарная дальность, или объем транспортной работы в тонно-километрах) была наименьшей. Следовательно, дело сводится к наиболее рациональному прикреплению производителей к потребителям продукции (и наоборот). В простейшем виде, когда распределяется один вид продукта и потребителям безразлично, от кого из поставщиков его получать, задача формулируется следующим образом.
Имеется ряд пунктов производства с объемами производства в единицу времени (месяц, квартал), равными соответственно и пункты потребления потребляющие за тот же промежуток времени соответственно продукции. В случае, если решается закрытая (сбалансированная) задача, сумма объемов производства на всех пунктах-поставщиках равна сумме объемов потребления на всех пунктах-получателях:
Кроме того, известны затраты по перевозке единицы продукта от каждого поставщика к каждому получателю -- эти величины обозначаются В качестве неизвестных величин выступают объемы продукта, перевозимого из каждого пункта производства в каждый пункт потребления, соответственно обозначаемые.
Тогда наиболее рациональным прикреплением поставщиков к потребителям будет такое, при котором суммарные затраты на транспортировку будут наименьшими:
При этом каждый потребитель получает нужное количество продукта:
И каждый поставщик отгружает весь произведенный им продукт:
Как и во всех подобных случаях, здесь также оговаривается неотрицательность переменных: поставка от какого-то пункта производства тому или иному пункту потребления может быть равна нулю, но отрицательной, т. е. следовать в обратном направлении, быть не может.
Строки транспортной таблицы соответствуют пунктам производства (в последней клетке каждой строки указан объем запаса продукта ai), а столбцы -- пунктам потребления (последняя клетка каждого столбца содержит значение потребности bj). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о перевозке из i-го пункта в j-й: в левом верхнем углу находится цена перевозки единицы продукта, а в правом нижнем -- значение объема перевозимого груза для данных пунктов. Клетки, которые содержат нулевые перевозки (xi, j=0), называют свободными, а ненулевые -- занятыми (xi, j>0).
В1 |
В2 |
...... |
Вn |
Всего | |
C1, 1 |
C1, 2 |
...... |
C1, n |
А1 | |
A1 |
C2, 1 |
C2, 2 |
...... |
C2, n |
А2 |
A2 |
.... |
.... |
.... |
.... | |
.... |
... |
... |
... |
.... |
.... |
Am |
Cm, 1 |
Cm, 2 |
...... |
Cm, n |
Аm |
B1 |
B2 |
Bn |
Несбалансированную (открытую) транспортную задачу приводят к виду, показанному выше, искусственно: в модель вводятся так называемые фиктивный поставщик или фиктивный потребитель, которые балансируют спрос и потребление.
В настоящее время разработано множество различных алгоритмов решения транспортной задачи: распределительный метод, метод потенциалов, дельта-метод, венгерский метод, метод дифференциальных рент, различные сетевые методы и т. д.
Производственно-транспортная задача
Это оптимизационная задача, при которой одновременно с установлением объема производства на отдельных предприятиях определяется и оптимальная схема размещения заказов (т. е. прикрепления поставщиков к потребителям). Она имеет особое значение для так называемых многотоннажных производств, где важен транспортный фактор (например, черные металлы, минеральные удобрения, нефтепереработка).
Такие задачи математически могут быть представлены в двух видах: в сетевой и в матричной постановке. Будучи основанными на принципах транспортной задачи линейного программирования, они очень сложны и решаются специальными, обычно многостадийными приемами с использованием эвристических элементов.
II. Практический раздел
Задача №1
Для производства двух видов изделий А и В предприятие использует три вида сырья. Другие условия задачи приведены в таблице 1.1.
Вид сырья |
Нормы расхода сырья на одно изделие, кг А В |
Общее количество сырья, кг |
I |
12 4 |
300 |
II |
4 4 |
120 |
III |
3 12 |
252 |
Прибыль от реализации одного изделия, ден. ед |
30 40 |
? |
Составить такой план выпуска продукции, при котором прибыль предприятия от реализации продукции будет максимальной при условии, что изделие В надо выпустить не менее, чем изделия А.
Решение.
Обозначим через х1 и х2 количество единиц продукции соответственно А и В, запланированных к производству. Для их изготовления потребуется (12 х1 +4х2 ) единиц ресурса I, (4х1 +4х2 ) единиц ресурса II, (3х1 +12х2 ) единиц ресурса III. Так как, потребление ресурсов I, II, III не должно превышать их запасов, то связь между потреблением ресурсов и их запасами выразится системой неравенств:
- 4х1 +4х2 ? 120; х1 + х2 ? 30; 3х1 +12х2 ? 252. х1 +4х2 ? 84.
По смыслу задачи переменные
Х1 ? 0, х2 ?0. (1, 1)
Конечную цель решаемой задачи - получение максимальной прибыли при реализации продукции - выразим как функцию двух переменных х1 и х2.
Суммарная прибыль А составит 30х1 от реализации продукции А и 40х 2 от реализации продукции В, то есть:
F = 30х1 +40х 2. (1, 2)
Изобразим многоугольник решений данной задачи.
В ограничениях задачи поменяем знаки неравенства на знаки равенства.
Проведем оси: на горизонтальной будут указываться значения переменной х1, а на вертикальной -- х2.Далее рассмотрим условие неотрицательности переменных: x1 ? 0 и х2 ? 0. Эти два ограничения показывают, что пространство допустимых решений будет лежать в первом квадранте (т. е выше оси x1 и правее оси х2 ).
Чтобы учесть оставшиеся ограничения, проще всего заменить неравенства на равенства, в результате чего получится система уравнений прямых:
3х1 + х2 = 75;
Х1 + х2 = 30;
Х1 +4х2 = 84.
А затем на плоскости провести эти прямые.
Например, неравенство 3х1 + х2 ? 75 заменяется уравнением прямой 3х1 + х2 = 75. Чтобы провести эту линию, надо найти две различные точки, лежащие на этой прямой Можно положить х1 = 0, тогда х2 = 75/1 = 75.. Аналогично для х2 = 0 находим x1 = 75/3 = 25. Итак, наша прямая проходит через две точки (0, 75) и (25;0). Аналогично найдем остальные точки и запишем их в таблицу 1.2.
Заштрихованная область, изображенная на рисунке, является областью допустимых значений функции F. Т. к. целевая функция F стремиться к max, то идя по направлению вектора n, получим точку B с оптимальным решением. Для определения ее координаты возьмем две прямые, на пересечении которых она образуется:
Х1 + 4х2 ? 84, х2 = 16, 09., т. е. B(16, 09; 19, 64)
Максимальное значение линейной функции равно:
FMax = 30*16, 09 + 40*19, 64 = 1232, 80.
Итак, FMax = 1232, 80 при оптимальном решении х1 = 16, 09, х2 = 19, 64, т. е. максимальная прибыль в 1232, 80 ден. ед. может быть достигнута при производстве 16, 09 единиц продукции А и 19, 64 единиц продукции В.
Ответ: FMax = 1232, 80.
Задача № 2
Для изготовления двух видов продукции Р1 и Р2 используют три вида сырья: S1, S2, S3. Запасы сырья, количество единиц сырья, затрачиваемых на изготовление единицы продукции, а также величина прибыли, получаемая от реализации единицы продукции, приведены в таблице 2.1.
Необходимо составить такой план выпуска продукции, чтобы при ее реализации получить максимальную прибыль.
Решение.
Обозначим через х1 количество единиц продукции Р1, а через х2 - количество единиц продукции Р2. Тогда, учитывая количество единиц сырья, расходуемое на изготовление продукции, а так же запасы сырья, получим систему ограничений:
- 2х1 + 5х2 ? 20 8х1 + 5х2 ? 40 5х1 + 6х2 ? 30
Которая показывает, что количество сырья, расходуемое на изготовление продукции, не может превысит имеющихся запасов. Если продукция Р1 не выпускается, то х1 =0; в противном случае x1 = 0. То же самое получаем и для продукции Р2. Таким образом, на неизвестные х1 и х2Должно быть наложено ограничение неотрицательности: х1 ? 0, х2 ? 0.
Конечную цель решаемой задачи - получение максимальной прибыли при реализации продукции - выразим как функцию двух переменных х1 и х2. Реализация х1 единиц продукции Р1 и х2 единиц продукции Р2 дает соответственно 50х1 и 40х2 руб. прибыли, суммарная прибыль Z = 50х1 + 40х2 (руб.)
Условиями не оговорена неделимость единица продукции, поэтому х1 и х2 (план выпуска продукции) могут быть и дробными числами.
Требуется найти такие х1 и х2, при которых функция Z достинает максимум, т. е. найти максимальное значение линейной функции Z = 50х1 + 40х2 при ограничениях
- 2х1 + 5х2 ? 20 8х1 + 5х2 ? 40 5х1 + 6х2 ? 30
Х1 ? 0, х2 ? 0.
Изобразим многоугольник решений данной задачи.
В ограничениях задачи поменяем знаки неравенства на знаки равенства.
Построим в программе Excelтаблицы нахождения точек пересечения линий с осями координат (Рисунок 1) и график (Рисунок 2).
Заштрихованная область, изображенная на рисунке, является областью допустимых значений функции Z. Т. к. целевая функция Z стремиться к max, то идя по направлению вектора n, получим точку C с оптимальным решением. Для определения ее координаты возьмем две прямые, на пересечении которых она образуется:
5х1 + 6х2 ? 30, х2 = 1, 74., т. е. C(3, 91; 1, 74)
Максимальное значение линейной функции равно:
ZMax = 50*3, 91 + 40*1, 74 = 265, 10.
Итак, ZMax = 265, 10 при оптимальном решении х1 = 3, 91, х2 = 1, 74, т. е. максимальная прибыль в 1232, 80 ден. ед. может быть достигнута при производстве 3, 91единиц продукции P1 и 1, 74 единиц продукции P2.
Ответ: ZMax = 265, 10.
Задача № 3
Имеется два вида корма. A и B, содержащие вещества(витамины) S1, S2, S3. Содержание числа единиц питательных веществ в одном кг каждого вида корма и необходимый минимум самих питательных веществ даны в таблице:
Решение:
Пусть х1 и х2 - количество кормоввида А и В соответственно. В одном килограмме каждого вида корма содержится (3х1 + х2 ) единиц питательного вещества S1, (x1 + 2x2 ) - S2 и (x1 + 6x2 ) - S3. Так количество питательных веществ не должно быть меньше необходимого минимума, то запишем следующую систему неравенств:
3х1 + х2 ? 8,
X1 + 2x2 ? 9,
X1 + 6x2 ? 12,
X1, x2 ? 0.
Минимальную стоимость витаминов за 1 кг корма, выразим следующей функцией:
F = 4x1 + 6x2 => min.
Изобразим многоугольник решений данной задачи.
В ограничениях задачи поменяем знаки неравенства на знаки равенства.
Построим в программе Excel таблицы нахождения точек пересечения линий с осями координат (Рисунок 1) и график (Рисунок 2).
Выделенная область, изображенная на рисунке, является областью допустимых значений функции F. Точка В - оптимальное решение. Для определения ее координаты возьмем две прямые, на пересечении которых она образуется:
X1 + 2x2 = 9, x1 = 7, 50,
X1 + 6x2 = 12, x2 = 0, 75.
Минимальное значение линейной функции равно:
FMin = 4*7.5 + 6*0.75 = 34.50.
Итак, FMin = 34.50 при оптимальном решении х1 = 7.50, х2 = 0.75.
Ответ: FMin = 34, 50.
Задача № 4
Трикотажная фабрика использует для производства свитеров и кофточек шерсть, силикон и нитрон, запасы которых составляют 820, 430 и 310 кг. Количество пряжи каждого вида (в кг), необходимой для изготовления одного изделия, а также прибыль, получаемая от их реализации, приведены в таблице.
Определить план выпуска изделий, максимизирующий прибыль.
Решение.
Пусть х1 и х2 - норма расхода пряжи для свитеров и кофточек соответственно. Количество пряжи каждого вида (в кг), необходимой для изготовления одного изделия запишем в следующую систему неравенств:
- 0, 4х1 + 0, 2х2 ? 820, 0, 2x1 + 0, 1x2 ? 430, 0, 1x1 + 0, 1x2 ? 310,
X1, x2 ? 0.
Максимальная прибыль от реализации свитеров и кофточек выразим следующей функцией:
F = 7, 8x1 + 5, 6x2 => max.
Изобразим многоугольник решений данной задачи.
В ограничениях задачи поменяем знаки неравенства на знаки равенства.
Построим в программе Excel таблицы нахождения точек пересечения линий с осями координат (Рисунок 1) и график (Рисунок 2).
Выделенная область, изображенная на рисунке, является областью допустимых значений функции F. Точка В - оптимальное решение. Для определения ее координаты возьмем две прямые, на пересечении которых она образуется:
- 0, 4x1 + 0, 2x2 = 820, x1 = 1000, 0, 1x1 + 0, 1x2 = 310, x2 = 2100.
Максимальное значение линейной функции равно:
FMax = 7.8*1000 + 5.6*2100 = 19560.
Итак, FMax = 19560 при оптимальном решении х1 = 1000, х2 = 2100.
Ответ: FMax = 19560.
Задача № 5
На звероферме могут выращиваться черно-бурые лисицы и песцы. Для обеспечения нормальных условий их выращивания используются три вида кормов. Определить, сколько лисиц и песцов следует выращивать на звероферме, чтобы прибыль от реализации их шкурок была максимальной.
Решение:
Пусть х1 и х2 - количество единиц корма, которые должны получать лисиа и песец, соответственно. Количество единиц каждого вида корма, необходимого для выращивания одного животного запишем в следующую систему неравенств:
- 2х1 + 3х2 ? 180, 4x1 + 1x2 ? 240, 6x1 + 7x2 ? 426,
X1, x2 ? 0.
Максимальная прибыль от реализации шкурок выразим следующей функцией:
F = 16x1 + 12x2 => max.
Изобразим многоугольник решений данной задачи.
В ограничениях задачи поменяем знаки неравенства на знаки равенства.
Построим в программе Excel таблицы нахождения точек пересечения линий с осями координат (Рисунок 1) и график (Рисунок 2).
Выделенная область, изображенная на рисунке, является областью допустимых значений функции F. Точка С - оптимальное решение. Для определения ее координаты возьмем две прямые, на пересечении которых она образуется:
X2 = 0, x1 = 60,
4x1 + x2 = 240, x2 = 0.
Максимальное значение линейной функции равно:
FMax = 16*60 + 12*0 = 960.
Итак, FMax = 960 при оптимальном решении х1 = 60, х2 = 0.
Ответ: FMax = 960.
Похожие статьи
-
Решение задач линейного программирования - Основы информатики
Имеются n пунктов производства и m пунктов распределения продукции. Стоимость перевозки единицы продукции с i-го пункта производства в j-ый центр...
-
Геометрический метод, Двойственная задача - Линейное программирование
Применяется для задач с двумя переменными. Метод решения состоит в следующем: На плоскости строятся прямые, которые задают соответствующие ограничения:...
-
Теоретическая основа линейного программирования, Симплекс метод - Линейное программирование
Симплекс метод Симплекс метод - метод линейного программирования, который реализует рациональный перебор базисных допустимых решений, в виде конечного...
-
Математический аппарат Для понимания всего дальнейшего полезно знать и представлять себе геометрическую интерпретацию задач линейного программирования,...
-
Методика решения задач ЛП графическим методом - Линейное программирование
I. В ограничениях задачи (1.2) заменить знаки неравенств знаками точных равенств и построить соответствующие прямые. II. Найти и заштриховать...
-
"РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ MICROSOFT EXCEL" Цель работы Приобретение навыков решения задач линейного программирования...
-
Линейное программирование - Линейное программирование
Линейный программирование математический графический Что же такое линейное программирование? Это один из первых и наиболее подробно изученных разделов...
-
Признак оптимальности плана перевозок T. З. устанавливает теорема. Теорема. Для того, чтобы некоторый допустимый план X = (xij)m-nT. З. был оптимальным,...
-
Транспортная задача (Т. З.) является одной из распространенных задач линейного программирования специального вида. Эта задача такого наиболее...
-
Введение - Линейное программирование
Линейное программирование - это наука о методах исследования и отыскания наибольших и наименьших значений линейной функции, на неизвестные которой...
-
Пересчет симплекс-таблицы. - Транспортная задача
Формируем следующую часть симплексной таблицы. Вместо переменной x в план 1 войдет переменная x1 . Строка, соответствующая переменной x1 в плане 1,...
-
Специфика транспортной задачи позволяет находить новое опорное решение задачи и новый базис по правилу более простому, чем в симплекс-методе. Пусть...
-
Транспортная задача оптимальность Поставим в соответствие поставщикам потенциалы Ui, , а потребителям - Vj, . В оптимальном плане для всех базисных...
-
Формулировка задачи - Линейное программирование
Даны линейная функция Z=С1 х1 +С2 х2 +...+СN xN (1.1) И система линейных ограничений A11 x1 + a22 x2 +... + a1N ХN = b1 A21 x1 + a22 x2 +... + a2N ХN =...
-
Постановка задачи: Фирма приобрела технологическую линию за начальную стоимость Sn. Срок службы технологической линии составляет K лет. Остаточная...
-
Кратко напомним некоторые фундаментальные определения и теоремы линейной алгебры и выпуклого анализа, которые широко применяются при решении проблем как...
-
Варианты - Решение задач линейного программирования с использованием Microsoft Excel
Используя MS Excel, найти решение для модели ЛП, соответствующей заданному варианту (табл. 1.5). Таблица 1.5 Варианты задач к лабораторной работе № 1 №...
-
Заключение - Линейное программирование
В данной дипломной работе мною были освоены навыки решения задач линейного программирования геометрическим методом. Для этого я изучил теоретические...
-
Цель Работы - изучить основные способы работы с пользовательским типом данных "класс", его объектами, методами и способы доступа к ним. - Теоретические...
-
Задачи и функции линейного отдела полиции Отдел возглавляет начальник, назначаемый на должность и освобождаемый от должности в установленном порядке....
-
Языки и системы программирования, их эволюция - Автоматизация решения задач пользователя
Язык программирования - это способ записи программ решения различных задач на ЭВМ в понятной для компьютера форме. Процессор компьютера непосредственно...
-
Постановка задачи, Подход к реализации - Обьекто-ориентированное программирование
Создать класс Triangle для представления треугольника. Поля класса - длины сторон. Требуется реализовать операции: вычисления углов треугольника,...
-
Транспортная задача - Транспортная задача
Сформулировать линейную производственную задачу и составить ее математическую модель, взяв исходные данные из приложения 1, где технологическая матрица А...
-
Оргтехника, ПК, телефонные аппараты На данный момент начальник ДЧ ЛОП использует комплекс технических средств, который предназначен для обработки...
-
Датчики Pt1000 (TSQ* и TSH*) прекрасно подходят для любых климатических систем, где необходимо измерять температуры в диапазоне от -50 до 250 °C с...
-
Таблица сопротивлений некоторых термометров сопротивления Температурав °C Pt100 Pt1000 Typ: 404 Typ: 501 -50 80, 31 803, 1 -40 84, 27 842, 7 -30 88, 22...
-
На рисунке 1 представлен фрагмент электронной таблицы, в которой содержаться исходные данные для решения задачи. Рисунок 1 - Фрагмент электронной...
-
1. Каковы основные этапы решения задач ЛП в MS Excel? 2. Каков вид и способы задания формул для целевой ячейки и ячеек левых частей ограничений? 3. В чем...
-
Протокол проверки программы - Программирование алгоритмов линейных и циклических структур
1. Введем размерность массива N = 6 2. Заполним элементы массива X(i) следующими значениями: 12, 1.34, 8, 10, 17.5, 30 3. Получим следующие результаты:...
-
FBD (Function Block Diagram) - является графическим языком программирования. Предназначенный для программирования микро контролеров с помощью блок...
-
Вычислить максимум функции F(x)=-L(x1)x2+3.1L(x2)x+5 на отрезке [a;b] с точностью е. L(x1), L(x2) - значения интерполяционного многочлена, построенного...
-
Для создания наиболее совершенных и экономичных механизмов и машин важно получить оптимальный вариант входящих в них редукторов (МЗП). Показатель, на...
-
Описание задачи, Моделирование бизнес-операций - Основы технологии программирования
Необходимо разработать клиент-серверную информационную систему для организации. Организация владеет сведениями о станциях грузоотправления,...
-
Ранг системы ограничений T. З. равен (m + n - 1), следовательно, невырожденный опорный план Т-задачи содержит (m + n - 1) положительных компонент или...
-
Теорема. Чтобы транспортная задача была разрешима, необходимо и достаточно, чтобы выполнялось условие: (1.5) Доказательство: Необходимость. Пусть...
-
Под критическим значением параметра регулятора (K или Т) понимается такое значение (Ккр или Ткр), при котором система оказывается на границе...
-
Для решения задачи №3 необходимо ввести исходные данные в электронную таблицу, т. е. таблицы 1,2 (рисунок 16). Рисунок 16 - Ввод исходных данных в...
-
Введение, Правила и порядок выполнения курсовой работы - Программирование в среде Turbo Pascal
Настоящие методические указания предназначены для выполнения курсовой работы "Расчеты на ЭВМ характеристик выходных сигналов электрических цепей" по...
-
Постановка задачи - Расчет трудоемкости средствами Ms Excel
Необходимо рассчитать нормативную трудоемкость квартальной и месячной производственной программы цеха по деталям. Для этого необходимо перемножить...
-
Технология программирования Для реализации поставленной задачи наиболее удобной парадигмой программирования будет являться объектно-ориентированная...
Транспортная задача - Линейное программирование