Xreferat.com » Рефераты по информатике и программированию » Практикум по решению линейных задач математического программирования

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

по решению линейных задач математического программирования" width="39" height="21" align="BOTTOM" border="0" />1340

Наиболее дефицитное сырье І вида. Наиболее убыточный І вид продукции.

Задания для самостоятельной работы.

Для производства четырех видов продукции (П1, П2, П3, П4) используются три вида ресурсов. Норма затрат ресурсов, использованных для выпуска единицы продукции каждого вида, цена единицы продукции и запасы ресурсов приведены в таблице.

Построить модель прямой и двойственной задач. Найти оптимальный план для обеих задач и экстремальные значения целевых функций. Дать экономическую интерпретацию основным и дополнительным переменным исходной и двойственной задач.


Ресурсы Продукция Затраты ресурсов на единицу продукции

Объем

ресурсов


П1 П2 П3 П4
Р1 2 3 4 4 2100
Р2 5 5 0 7 2800
Р3 8 7 10 9 3000

Цена

единицы

60 65 55 62

Транспортная задача (ТЗ)

Транспортная задача возникает при планировании рациональных перевозок грузов. Математическая модель транспортной задачи в простейшем случае имеет вид:


Практикум по решению линейных задач математического программированияmax (1)

Практикум по решению линейных задач математического программирования (2)

Практикум по решению линейных задач математического программирования, Практикум по решению линейных задач математического программирования, Практикум по решению линейных задач математического программирования (3)


Здесь: Практикум по решению линейных задач математического программирования– запасы поставщиков;

Практикум по решению линейных задач математического программирования– спрос потребителей;

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

Z – транспортные расходы;

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

Обычно транспортную задачу задают тремя матрицами: матрицей поставщиков, матрицей потребителей и матрицей тарифов.

Для наглядности транспортную задачу представляют в виде распределительной таблицы.

Любая транспортная задача имеет допустимое решение (матрицу перевозок Практикум по решению линейных задач математического программирования), если


Практикум по решению линейных задач математического программирования (4)


Если условие (4) выполняется, то транспортную задачу называют транспортной задачей закрытого типа.

Допустимое решение транспортной задачи часто называют планом перевозок.

1) Построение начального опорного плана. Его вырожденность или невырожденность. Ранг матрицы системы.

а) Метод северо-западного угла.

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

Пример. Построить методом северо-западного угла начальный опорный план для транспортной задачи: поставщики а = (20; 30; 40); потребители Практикум по решению линейных задач математического программирования= (15; 35; 20; 20); тарифы перевозок

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

Найти стоимость перевозок.

Решение. Строим распределительную таблицу и находим груз х11 = min (20; 15) = 15. По первому столбцу не перемещаемся, так как спрос І потребителя удовлетворен. Перемещаемся по І строке в клетку (1; 2):

х12 = min (а1 – х11; b2) = min (5; 35) = 5.

Теперь переходим по ІІ столбцу в клетку (2; 2):

х22 = min (30; b2 – х12) = min (30; 30) = 30.

Так как спрос ІІ потребителя удовлетворен и у ІІ поставщика продукция уже выбрана, то переходим к клетке (3; 3):

х33 = min (40; 20) = 20.

х34 = min (а3 – х33; b4) = min (20; 20) = 20.

Таким образом, получен план перевозок:


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

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

15 35 20 20
20
4
6
12
5

15 5

30
2
7
8
10


30

40
5
3
4
6



20 20

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

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

б) Метод минимального элемента (наименьшей стоимости).

Строим распределительную таблицу и начинаем ее заполнять с той клетки, в которой наименьший тариф.

Пример. Построить начальный опорный план методом минимальной стоимости и найти транспортные расходы для транспортной задачи: поставщики а = (20; 30; 40); потребители Практикум по решению линейных задач математического программирования= (15; 35; 20; 20); тарифы перевозок

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

Решение. Строим распределительную таблицу и начинаем ее заполнять с клетки (2; 1), т. к. в ней наименьший тариф х21 = min (30; 15) = 15.


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

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

15 35 20 20
20
4
6
12
5




20
30
2
7
8
10

15
15
40
5
3
4
6


35 5

Потом заполняем клетку (3; 2) с тарифом с32 = 3;

х32 = min (40; 35) = 35.

Далее х33 = min (а3 – х32; b3) = (5; 20) = 5;

х14 = min (20; 20) = 20;

х23 = min (а2 – х21; b3 – х33) = min (15; 15) = 15.

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

Сравнивая значение Z в а) и б), видим, что учитывая стоимости перевозок, затраты при втором методе значительно меньше.

Рангом матрицы системы (2) называют число Практикум по решению линейных задач математического программирования, т.е. количество строк плюс количество столбцов и минус единица. Если число заполненных клеток в распределительной таблице равно рангу матрицы, то полученный план называется не вырожденным. В противоположном случае – вырожденным.

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

2) Метод потенциалов. Признак оптимальности опорного плана.

Допустимое решение транспортной задачи является оптимальным тогда и только тогда, когда можно найти такие числа – потенциалы Практикум по решению линейных задач математического программирования, Практикум по решению линейных задач математического программирования и Практикум по решению линейных задач математического программирования, Практикум по решению линейных задач математического программирования, которые удовлетворяют следующим условиям:


Практикум по решению линейных задач математического программирования для всех заполненных клеток; (5)

Практикум по решению линейных задач математического программирования для всех пустых клеток. (6)


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

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

3) Переход к нехудшему опорному плану.

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

Приведем примеры разновидностей форм циклов:

В каждом случае только одна вершина цикла находится в незаполненной клетке. Ее называют началом цикла и определяют по наибольшему нарушению условия оптимальности (6), т.е. по максимальной оценке Практикум по решению линейных задач математического программирования. Клетке начала цикла присваивают знак «+», во всех остальных вершинах цикла знаки чередуют «–», «+» и т.д. Из клеток цикла со знаками «–» выбирают ту, в которой находится минимальный груз. Это и будет то количество груза, которое нужно перераспределить по циклу, т.е. в клетке со знаком «+» это количество груза прибавляется, а со знаком «–» – вычитается. Клетки, которые не задействованы в цикле, остаются неизменными.

Таким образом, получаем новый опорный план. Подсчитываем транспортные расходы, которые должны быть не более предыдущих. В противном случае где-то допущена ошибка. Новый план опять проверяем на оптимальность, используя условия (5) и (6). Если план оптимальный, то задача решена. Если же план опять не оптимальный, то работаем, согласно пункту 3) до получения оптимального плана и нахождения Zmin.

Транспортная задача открытого типа

Если для транспортной задачи выполняется одно из условий


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

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


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

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

Запишем алгоритм решения транспортной задачи:

1) Проверка типа модели ТЗ.

2) Построение начального опорного плана (любым способом).

3) Проверка плана на вырожденность.

4) Проверка плана на оптимальность методом потенциалов:

а) нахождение потенциалов из системы

Практикум по решению линейных задач математического программирования (для всех заполненных клеток);

б) проверка второго условия оптимальности

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

5) Переход к нехудшему опорному плану (если это необходимо).

Пример. На складах имеются запасы однотипного товара в количестве а (35; 40; 40; 50), который необходимо доставить потребителям. Потребности потребителей задает вектор b (31; 52; 17; 20). Матрица затрат на доставку единицы товара от i-го поставщика j-му потребителю:

с=Практикум по решению линейных задач математического программирования

Составить план перевозок с минимальными транспортными затратами.

Решение. Определим тип модели транспортной задачи. Суммарная мощность поставщиков: Практикум по решению линейных задач математического программирования35+40+40+50=165 (единиц товара); Суммарный спрос потребителей: Практикум по решению линейных задач математического программирования31+52+17+20=120 (единиц товара).


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


Введем фиктивного потребителя, спрос которого равен


Практикум по решению линейных задач математического программированияПрактикум по решению линейных задач математического программированияПрактикум по решению линейных задач математического программирования 165 –120 =45 (единиц товара).

Тарифы Практикум по решению линейных задач математического программирования0. Т.о. получаем модель закрытого типа, m = 4 – число поставщиков, n = 5 – число потребителей. Ранг матрицы задачи Практикум по решению линейных задач математического программирования. Построим начальный опорный план методом минимального элемента (наименьшей стоимости).


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

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

31 52 17 20 45

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

35
5
4
3
1
0 0



15 20

40
2
3
5
8
0 1

31 9



40
6
8
7
10
0 4





40
50
5
6
7
2
0 4


43 2
5

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

1 2 3 1 – 4 Таб.1

Число заполненных клеток распределительной таблицы 8 равно рангу матрицы задачи r = 8, следовательно, опорный план является невырожденным.

Транспортные затраты, соответствующие опорному плану:

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

Исследуем опорный план на оптимальность, используя метод потенциалов.

Дополним таблицу 1 столбцом и строкой потенциалов Практикум по решению линейных задач математического программирования и Практикум по решению линейных задач математического программирования. Систему потенциалов найдем, используя первое условие оптимальности: для заполненных поставками клеток Практикум по решению линейных задач математического программирования.

Практикум по решению линейных задач математического программирования;

Практикум по решению линейных задач математического программирования;

Практикум по решению линейных задач математического программирования;

Практикум по решению линейных задач математического программирования;

Практикум по решению линейных задач математического программирования;

Практикум по решению линейных задач математического программирования;

Практикум по решению линейных задач математического программирования;

Практикум по решению линейных задач математического программирования;

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

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

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

(1; 1) Практикум по решению линейных задач математического программирования0 + 1 – 5 = –4Практикум по решению линейных задач математического программирования0;

(1; 2) Практикум по решению линейных задач математического программирования0 + 2 – 4 = –2Практикум по решению линейных задач математического программирования0;

(1; 5) Практикум по
    <div class=

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: