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

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

Рубрика Экономико-математическое моделирование
Вид контрольная работа
Язык русский
Дата добавления 29.10.2012
Размер файла 225,3 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на 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 пунктах производства (хранения) в количествах а1, а2,…, аm единиц, необходимо распределить между n пунктами потребления, которым необходимо соответственно b1, b2,…, bn единиц. Стоимость перевозки единицы продукта из i-го пункта отправления в j-ый пункт назначения равна сij и известна для всех маршрутов. Необходимо составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства и общие транспортные расходы по доставке продуктов были минимальными. Обозначим через хij количество груза, планируемого к перевозке от i-го поставщика j-му потребителю. При наличии баланса производства и потребления

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

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

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

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

х11 > 0,…., xmn > 0.

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

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

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

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

L(x)= c1x1 +… + cnxn

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

a11x1 +… + a1n xn = a10

………………….

am1x1 +… + amnxn = am0

xj0, j=1…, n

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

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

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

В случае, когда координаты этой точки нецелочисленные, в области допустимых решений строят целочисленную решетку и находят на ней такие целые числа 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 - количество выпускаемых узлов У1, х2 - количество выпускаемых узлов У2.

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

12?10

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

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

F=5х1+4х2.

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

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

Найти F=5х1+4х2>max

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

12?10 (1)

2?8. (2)

х1?0, х2 ?0

х1, х2 - целые.

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

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

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

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

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

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

2x1+x2=10

2x2=8

Решив систему уравнений, получим: x1 = 3, x2 = 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 первый минимальный элемент min11 = 6, второй минимальный элемент min21 = 7. Их разность равна d = min21 - min11 = 1.

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

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

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

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

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

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

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

Для столбца N=4 первый минимальный элемент min14 = 3. второй минимальный элемент min24 8. Их разность d = min24 - min14 = 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, то вычитаем его.

x34 = 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 первый минимальный элемент min11 = 6, второй минимальный элемент min21 = 7. Их разность равна d = min21 - min11 = 1.

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

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

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

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

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

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

Для столбца N=3 первый минимальный элемент min13 = 6. второй минимальный элемент min23 6. Их разность d = min23 - min13 = 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, то вычитаем его.

x21 = 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 первый минимальный элемент min11 = 6, второй минимальный элемент min21 = 7. Их разность равна d = min21 - min11 = 1.

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

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

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

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

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

Для столбца N=3 первый минимальный элемент min13 = 6. второй минимальный элемент min23 0. Их разность d = min23 - min13 = 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, то вычитаем его.

x31 = min (3,3) = 3.

х

0

0

х

х

х

х

х

х

0

х

х

х

3-3=0

х

0

0

х

3-3=0

0

0

х

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

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

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

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

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

Для столбца N=3 первый минимальный элемент min12 = 6. второй минимальный элемент min22 12. Их разность d = min22 - min12 = 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, то вычитаем его.

x13 = 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);

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

u1 + v1 = 7; 0 + v1 = 7; v1 = 7

u2 + v1 = 5; 7 + u2 = 5; u2 = -2

u3 + v1 = 2; 7 + u3 = 2; u3 = -5

u3 + v4 = 3; -5 + v4 = 3; v4 = 8

u1 + v2 = 9; 0 + v2 = 9; v2 = 9

u4 + v2 = 10; 9 + u4 = 10; u4 = 1

u1 + v3 = 6; 0 + v3 = 6; v3 = 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

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

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

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

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

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


Подобные документы

  • Применение линейного программирования для решения транспортной задачи. Свойство системы ограничений, опорное решение задачи. Методы построения начального опорного решения. Распределительный метод, алгоритм решения транспортной задачи методом потенциалов.

    реферат [4,1 M], добавлен 09.03.2011

  • Виды задач линейного программирования и формулировка задачи. Сущность оптимизации как раздела математики и характеристика основных методов решения задач. Понятие симплекс-метода, реальные прикладные задачи. Алгоритм и этапы решения транспортной задачи.

    курсовая работа [268,0 K], добавлен 17.02.2010

  • Математическая формализация оптимизационной проблемы. Геометрическая интерпретация стандартной задачи линейного программирования, планирование товарооборота. Сущность и алгоритм симплекс-метода. Постановка транспортной задачи, последовательность решения.

    учебное пособие [126,0 K], добавлен 07.10.2014

  • Математическая формулировка задачи линейного программирования. Применение симплекс-метода решения задач. Геометрическая интерпретация задачи линейного программирования. Применение методов линейного программирования к экстремальным задачам экономики.

    курсовая работа [106,0 K], добавлен 05.10.2014

  • Геометрический способ решения стандартных задач линейного программирования с двумя переменными. Универсальный метод решения канонической задачи. Основная идея симплекс-метода, реализация на примере. Табличная реализация простого симплекс-метода.

    реферат [583,3 K], добавлен 15.06.2010

  • Основные методы решения задач линейного программирования. Графический метод, симплекс-метод. Двойственная задача, метод потенциалов. Моделирование и особенности решения транспортной задачи методом потенциалов с использованием возможностей Мicrosoft Excel.

    контрольная работа [1,1 M], добавлен 14.03.2014

  • Геометрическая интерпретация, графический и симплексный методы решения задачи линейного программирования. Компьютерная реализация задач стандартными офисными средствами, в среде пакета Excel. Задачи распределительного типа, решаемые в землеустройстве.

    методичка [574,3 K], добавлен 03.10.2012

  • Цель работы: изучить и научиться применять на практике симплекс - метод для решения прямой и двойственной задачи линейного программирования. Математическая постановка задачи линейного программирования. Общий вид задачи линейного программирования.

    реферат [193,4 K], добавлен 28.12.2008

  • Формулировка проблемы в практической области. Построение моделей и особенности экономико-математической модели транспортной задачи. Задачи линейного программирования. Анализ постановки задач и обоснования метода решения. Реализация алгоритма программы.

    курсовая работа [56,9 K], добавлен 04.05.2011

  • Решение задачи линейного программирования графическим и симплекс-методом. Решение задачи двойственной к исходной. Определение оптимального плана закрепления потребителей за поставщиками однородного груза при условии минимизации общего пробега автомобилей.

    контрольная работа [398,2 K], добавлен 15.08.2012

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.