Методы решения задач линейного программирования

Размещено на http://www.allbest.ru/

1. Приближенные методы решения задачи линейного программирования на примере транспортной задачи

Применение методов линейного программирования при решении транспортной задачи проиллюстрировано в следующем примере:

Компания с ограниченной ответственностью «Асе Foods Ltd» осуществляет производство прохладительных напитков на двух заводах - А и В. Поставкой бутылок на каждый из заводов занимаются две фирмы - Р и Q. На ноябрь заводу А требуется 5000 бутылок, а заводу В - 3500 бутылок. Фирма Р может поставить максимум 7500 бутылок, а фирма Q - 4000 бутылок. Табл. 2.1. содержит информацию о стоимости перевозки одной бутылки от каждого поставщика каждому заводу.

Стоимость перевозки бутылок, показатели спроса и предложения

Поставщик	Стоимость перевозки одной бутылки на завод, пенсов	Максимальный объем поставки
	А	В
Р Q	4 3	4 2	7500 4000
Спрос на бутылки	5000	3500

Как следует организовать доставку бутылок на заводы, чтобы общая стоимость перевозки была минимальной?

Решение

При решении транспортной задачи всегда полезно проверить, не существует ли очевидного решения. Теоретически было бы желательно использовать для перевозок только наиболее дешевые маршруты. Для обоих заводов Q был бы наиболее предпочтительным поставщиком, так как стоимость перевозки для него ниже, чем для Р. Однако максимальный объем перевозок для Q составляет только 4000 бутылок, тогда как общий спрос равен 8500. Вероятно, наиболее дешевым вариантом было бы использование маршрута из Q в В стоимостью 2 пенса за единицу, удовлетворяющее весь спрос завода В (3500). Остаток запаса (500) следует направить из Q в А по стоимости 3 пенса за единицу. Остальной спрос завода А - следует удовлетворить через поставщика Р, причем стоимость перевозки составит 4 пенса за единицу. Общая стоимость транспортировки при таком распределении будет иметь вид:

ф. ст. в месяц.

Однако мы не можем доказать, что данное распределение ресурсов является наиболее экономичным. Основные аспекты исследования транспортной модели состоят в следующем: доказательство того, что сформулированная задача имеет решение; обоснование положения о том, что это решение является оптимальным; изучение влияния на полученное решение любых изменений условии задачи.

Построив соответствующую модель линейного программирования, решим сформулированную выше проблему графическим методом.

Пусть фирма Р поставляет х бутылок для завода А и у бутылок для завода В. Тогда для полного удовлетворения спроса фирма должна поставлять оставшиеся (5000-х) бутылок на завод А и (3500 - у) бутылок на завод В-Цель состоит в минимизации общей стоимости транспортировки С (в пенсах), где

С=4х+4у+3 (5000-х) + 2 (3500 - у),

следовательно,

С = х + 2 у + 22000,

а целевая функция задачи имеет вид:

Z = С - 22000 = х + 2у.

Z принимает свое минимальное значение тогда, когда С принимает минимальное значение. Значения х и у, которые минимизируют Z, минимизируют также и С. Минимизация целевой функции осуществляется в условиях следующей системы ограничений:

Спрос завода А: х5000 бутылок

Спрос завода В у3500 бутылок

Поставки из Р х + у7500 бутылок

Поставки из Q: (5000-х) + (3500 - у)4000 бутылок

т.е.: х + у 4500 бутылок

х, у 0

Графическое изображение системы ограничений представлено на рис. 2.1.

Точка с координатами х = 4000, у = 2000 принадлежит допустимому множеству. Значение функции в этой точке пенсов.

Типичная линия уровня целевой функции имеет вид: 8000 = х + 2 у. На рис. 2.1 она изображена пунктиром. Перемещение линии уровня в сторону уменьшения значений целевой функции приводит нас в крайнюю точку А, которая является оптимальной. В этой точке х = 4500, а у = 0. Следовательно, оптимальное решение состоит в поставке из Р в А 4500 бутылок, в отсутствии поставок из Р в В, в поставке из Q в А 500 бутылок, а из Q в В - 3500 бутылок.

Минимальная стоимость транспортировки для этого решения равна:

С_min пенсов = 265 ф. ст.

Резервный запас остается только на фирме Р и составляет 3000 единиц. Начиная решать задачу, мы предполагали, что именно это решение минимизирует стоимость перевозки. Теперь мы доказали, что это действительно так.



Транспортная задача формулируется следующим образом. Однородный продукт, сосредоточенный в m пунктах производства (хранения) в количествах а₁, а₂,…, а_m единиц, необходимо распределить между n пунктами потребления, которым необходимо соответственно b₁, b₂,…, b_n единиц. Стоимость перевозки единицы продукта из i-го пункта отправления в j-ый пункт назначения равна с_ij и известна для всех маршрутов. Необходимо составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства и общие транспортные расходы по доставке продуктов были минимальными. Обозначим через х_ij количество груза, планируемого к перевозке от i-го поставщика j-му потребителю. При наличии баланса производства и потребления

математическая модель транспортной задачи будет выглядеть так: найти план перевозок Х = (х_ij), i = 1, m; j = 1, n минимизирующий общую стоимость всех перевозок



при условии, что из любого пункта производства вывозится весь продукт

и любому потребителю доставляется необходимое количество груза

причем по смыслу задачи

х₁₁ > 0,…., x_mn > 0.

Для решения транспортной задачи чаще всего применяется метод потенциалов. Кроме того, может использоваться распределительный метод (модификация симплекс-метода). Для нахождения опорного плана могут использоваться методы: «северо-западного угла», «наименьшего элемента», двойного предпочтения и аппроксимации Фогеля.

2. Графический метод решения задач целочисленного программирования

Постановка целочисленной задачи линейного программирования.

Найти вектор x=(x₁…, xn), что минимизирует целевую функцию

L(x)= c₁x₁ +… + c_nx_n

и удовлетворяет систему ограничений

a₁₁x₁ +… + a_1n x_n = a₁₀

………………….

a_m1x1 +… + a_mnx_n = a_m0

x_j0, j=1…, n

x_j - целые, j=1…, n.

При наличии в задаче линейного программирования двух переменных, задача может быть решена графическим методом.

В системе координат X₁0X₂ находят область допустимых решений, строят вектор С и линию уровня. перемещая линию уровня по направлению С для задач на максимум, определяют наиболее удаленную от начала координат точку и ее координаты.

В случае, когда координаты этой точки нецелочисленные, в области допустимых решений строят целочисленную решетку и находят на ней такие целые числа x1 и x2, которые удовлетворяют системе ограничений и при которых значение целевой функции наиболее близко к экстремальному нецелочисленному решению. Координаты такой вершины являются целочисленным решением.

Аналогично решается задача на минимум. Целочисленному минимуму целевой функции будет соответствовать координаты вершины целочисленной решетки, лежащей в области допустимых решений, наиболее близкой к началу координат в направлении вектора С.

Графический метод основан на геометрической интерпретации задачи линейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трёхмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Задачу пространства размерности больше трёх изобразить графически вообще невозможно.

В случае если количество переменных в задаче предварительно необходимо преобразовать исходную задачу линейного программирования n переменных к задаче линейного программирования двух переменных путем исключения базисных переменных.

3. Завод выпускает два вида узлов У1 и У2 для систем управления, используя для этого два вида технологических линеек Л1 и Л2. На производство одного узла вида У1 на линейке Л1 затрачивается 2 часа; на изготовление одного узла У2 затрачивается соответственно 1 час и 2 часа. Завод может использовать Л1 в течение 10 час., а Л2 - 8 час. Прибыль от реализации одного изделия У1 - 5$, а от реализации одного изделия У2 - 4$. Определить количество узлов У1 и У2 которое необходимо выпустить заводу с тем, чтобы получить максимальную прибыль

Составим математическую модель задачи:

Обозначим х₁ - количество выпускаемых узлов У1, х₂ - количество выпускаемых узлов У2.

На производство узлов вида У1 на линейке Л1 затрачивается 2х₁ часа. На производство узлов У2 на линейке Л1 затрачивается х₂ часов. Завод может использовать Л1 в течение 10 часов, следовательно:

2х₁+х₂?10

Аналогично запишется ограничение по использовании технологической линейки Л2: 2х₂?8.

Прибыль от продажи произведенных узлов У1 составит 5х₁, а от продажи узлов У2 - 4 х₂, тогда функция описывающая полученную прибыль имеет вид:

F=5х₁+4х₂.

При этом очевидно, что х₁ и х₂ - целые.

Получили целочисленную задачу линейного программирования.

Найти F=5х₁+4х₂>max

При условиях:

2х₁+х₂?10 (1)

2х₂?8. (2)

х₁?0, х₂ ?0

х₁, х₂ - целые.

Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).

Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.

Обозначим границы области многоугольника решений.

Построим прямую, отвечающую значению функции F = 0: F = 5x1+4x2 = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.



Область допустимых решений представляет собой многоугольник.

Прямая F(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых:

2x₁+x₂=10

2x₂=8

Решив систему уравнений, получим: x₁ = 3, x₂ = 4

Откуда найдем максимальное значение целевой функции:

F(X) = 5*3 + 4*4 = 31

Решение получилось целочисленным.

Следовательно, заводу выгодно производить 3 узла вида У1 и 4 узла вида У2. При этом прибыль полученная от их реализации составит 31 $.

4. Решить транспортную задачу, используя приближенный метод Фогеля

	Пункты назначения	Объем производства
	1	2	3	4
Исходные пункты	1	7 х11	9 х12	6 х13	12 х14	10
	2	5 х21	12 х22	11 х23	8 х24	5
	3	2 х31	13 х32	6 х33	3 х34	15
	4	8 х41	10 х42	12 х43	14 х44	20
Спрос	8	20	10	12

Проверим необходимое и достаточное условие разрешимости задачи.

?a = 10 + 5 + 15 + 20 = 50

?b = 8 + 20 + 10 + 12 = 50

Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.

Используя метод Фогеля, построим первый опорный план транспортной задачи. Для каждой строки и столбца таблицы условий найдем разности между двумя минимальными тарифами, записанными в данной строе или столбце, и поместим их в соответствующем дополнительном столбце или строке.

Данный метод состоит в следующем:

1. на каждой итерации находят разности между двумя наименьшими тарифами во всех строках и столбцах, записывая их в дополнительные столбец и строку таблицы;

2. находят максимальную разность и заполняют клетку с минимальной стоимостью в строке (столбце), которой соответствует данная разность.

Находим разности по строкам.

Для строки N=1 первый минимальный элемент min¹₁ = 6, второй минимальный элемент min²₁ = 7. Их разность равна d = min²₁ - min¹₁ = 1.

Для строки N=2 первый минимальный элемент min¹₂ = 5, второй минимальный элемент min²₂ = 8. Их разность равна d = min²₂ - min¹₂ = 3.

Для строки N=3 первый минимальный элемент min¹₃ = 2, второй минимальный элемент min²₃ = 3. Их разность равна d = min²₃ - min¹₃ = 1.

Для строки N=4 первый минимальный элемент min¹₄ = 8, второй минимальный элемент min²₄ = 10. Их разность равна d = min²₄ - min¹₄ = 2.

Находим разности по столбцам.

Для столбца N=1 первый минимальный элемент min¹₁ = 2. второй минимальный элемент min²₁ 5. Их разность d = min²₁ - min¹₁ = 3.

Для столбца N=2 первый минимальный элемент min¹₂ = 9. второй минимальный элемент min²₂ 10. Их разность d = min²₂ - min¹₂ = 1.

Для столбца N=3 первый минимальный элемент min¹₃ = 6. второй минимальный элемент min²₃ 6. Их разность d = min²₃ - min¹₃ = 0.

Для столбца N=4 первый минимальный элемент min¹₄ = 3. второй минимальный элемент min²₄ 8. Их разность d = min²₄ - min¹₄ = 5.

Вычислив все эти разности, видим, что наибольшая из них соответствует столбцу (4). В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки (3) и столбца (4).

	1	2	3	4	Запасы	Разности по строкам
1	7	9	6	12	10	1
2	5	12	11	8	5	3
3	2	13	6	3	15	1
4	8	10	12	14	20	2
Потребности	8	20	10	12	0	0
Разности по столбцам	3	1	0	5	0

Искомый элемент равен 3

Для этого элемента запасы равны 15, потребности 12. Поскольку минимальным является 12, то вычитаем его.

x₃₄ = min (15,12) = 12.

0	0	0	x	0
0	0	0	x	x
0	0	0	0	15 - 12 = 3
0	x	x	x	x
0	0	0	12 - 12 = 0	x

Находим разности по строкам.

Для строки N=1 первый минимальный элемент min¹₁ = 6, второй минимальный элемент min²₁ = 7. Их разность равна d = min²₁ - min¹₁ = 1.

Для строки N=2 первый минимальный элемент min¹₂ = 5, второй минимальный элемент min²₂ = 11. Их разность равна d = min²₂ - min¹₂ = 6.

Для строки N=3 первый минимальный элемент min¹₃ = 2, второй минимальный элемент min²₃ = 6. Их разность равна d = min²₃ - min¹₃ = 4.

Для строки N=4 первый минимальный элемент min¹₄ = 8, второй минимальный элемент min²₄ = 10. Их разность равна d = min²₄ - min¹₄ = 2.

Находим разности по столбцам.

Для столбца N=1 первый минимальный элемент min¹₁ = 2. второй минимальный элемент min²₁ 5. Их разность d = min²₁ - min¹₁ = 3.

Для столбца N=2 первый минимальный элемент min¹₂ = 9. второй минимальный элемент min²₂ 10. Их разность d = min²₂ - min¹₂ = 1.

Для столбца N=3 первый минимальный элемент min¹₃ = 6. второй минимальный элемент min²₃ 6. Их разность d = min²₃ - min¹₃ = 0.

Вычислив все эти разности, видим, что наибольшая из них соответствует строке (2). В этой строке минимальный тариф записан в клетке, находящейся на пересечении строки (2) и столбца (1).

	1	2	3	4	Запасы	Разности по строкам
1	7	9	6	12	10	1
2	5	12	11	8	5	6
3	2	13	6	3	3	4
4	8	10	12	14	20	2
Потребности	8	20	10	0	0	0
Разности по столбцам	3	1	0	-	0

Искомый элемент равен 5

Для этого элемента запасы равны 5, потребности 8. Поскольку минимальным является 5, то вычитаем его.

x₂₁ = min (5,8) = 5.

0	0	0	0	0
0	x	x	0	5 - 5 = 0
0	x	x	x	x
0	x	0	0	0
8 - 5 = 3	x	0	0	0

Находим разности по строкам.

Для строки N=1 первый минимальный элемент min¹₁ = 6, второй минимальный элемент min²₁ = 7. Их разность равна d = min²₁ - min¹₁ = 1.

Для строки N=3 первый минимальный элемент min¹₃ = 2, второй минимальный элемент min²₃ = 6. Их разность равна d = min²₃ - min¹₃ = 4.

Для строки N=4 первый минимальный элемент min¹₄ = 8, второй минимальный элемент min²₄ = 10. Их разность равна d = min²₄ - min¹₄ = 2.

Находим разности по столбцам.

Для столбца N=1 первый минимальный элемент min¹₁ = 2. второй минимальный элемент min²₁ 7. Их разность d = min²₁ - min¹₁ = 5.

Для столбца N=2 первый минимальный элемент min¹₂ = 9. второй минимальный элемент min²₂ 10. Их разность d = min²₂ - min¹₂ = 1.

Для столбца N=3 первый минимальный элемент min¹₃ = 6. второй минимальный элемент min²₃ 0. Их разность d = min²₃ - min¹₃ = 0.

Вычислив все эти разности, видим, что наибольшая из них соответствует столбцу (1). В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки (3) и столбца (2).

	1	2	3	4	Запасы	Разности по строкам
1	7	9	6	12	10	1
2	5	12	11	8	0	-
3	2	13	6	3	3	4
4	8	10	12	14	20	2
Потребности	3	20	10	0	0	0
Разности по столбцам	5	1	0	-	0

Искомый элемент равен 2

Для этого элемента запасы равны 3, потребности 3. Поскольку минимальным является 10, то вычитаем его.

x₃₁ = min (3,3) = 3.



х	0	0	х
х	х	х	х	х
0	х	х	х	3-3=0
х	0	0	х
3-3=0	0	0	х

Находим разности по строкам.

Для строки N=1 первый минимальный элемент min¹₁ = 6, второй минимальный элемент min²₁ = 9. Их разность равна d = min²₁ - min¹₁ = 3.

Для строки N=4 первый минимальный элемент min¹₄ = 10, второй минимальный элемент min²₄ = 12. Их разность равна d = min²₄ - min¹₄ = 2.

Находим разности по столбцам.

Для столбца N=2 первый минимальный элемент min¹₂ = 9. второй минимальный элемент min²₂ 10. Их разность d = min²₂ - min¹₂ = 1.

Для столбца N=3 первый минимальный элемент min¹₂ = 6. второй минимальный элемент min²₂ 12. Их разность d = min²₂ - min¹₂ = 6.

Вычислив все эти разности, видим, что наибольшая из них соответствует столбцу (3). В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки (1) и столбца (3).

	1	2	3	4	Запасы	Разности по строкам
1	7	9	6	12	10	3
2	5	12	11	8	0	-
3	2	13	6	3	0	-
4	8	10	12	14	20	2
Потребности	0	20	10	0	0	0
Разности по столбцам	-	1	6	-	0

Искомый элемент равен 6

Для этого элемента запасы равны 10, потребности 10. Поскольку минимальным является 10, то вычитаем его.

x₁₃ = min (10,10) = 10.

х	х	10	х	10-10=0
0	0	х	0	0
0	0	х	0	0
0	0	х	0	0
0	0	10-10=0	0	0

После данного распределения продукта оставшееся его количество распределяется по клеткам транспортной таблицы однозначно. Оставшийся продукт помещается в клетку (4,2)

	1	2	3	4	Запасы
1	7	9	6 [10]	12	10
2	5 [5]	12	11	8	5
3	2 [3]	13	6	3 [12]	15
4	8	10 [20]	12	14	20
Потребности	8	20	10	12

Подсчитаем число занятых клеток таблицы, их 5, а должно быть m + n - 1 = 7. Следовательно, опорный план является вырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 6*10 + 5*5 + 2*3 + 3*12 + 10*20 = 327

Для получения невырожденного плана принудительно добавляем нуль [0] в клетку (1; 1); (1; 2);

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

u₁ + v₁ = 7; 0 + v₁ = 7; v₁ = 7

u₂ + v₁ = 5; 7 + u₂ = 5; u₂ = -2

u₃ + v₁ = 2; 7 + u₃ = 2; u₃ = -5

u₃ + v₄ = 3; -5 + v₄ = 3; v₄ = 8

u₁ + v₂ = 9; 0 + v₂ = 9; v₂ = 9

u₄ + v₂ = 10; 9 + u₄ = 10; u₄ = 1

u₁ + v₃ = 6; 0 + v₃ = 6; v₃ = 6

	v1=7	v2=9	v3=6	v4=8
u1=0	7 [0]	9 [0]	6 [10]	12
u2=-2	5 [5]	12	11	8
u3=-5	2 [3]	13	6	3 [12]
u4=1	8	10 [20]	12	14

линейный фогель программирование транспортный

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i <= c_ij.

Минимальные затраты составят:

F(x) = 6*10 + 5*5 + 2*3 + 3*12 + 10*20 = 327.

Размещено на Allbest.ru