Способы решения транспортной и линейной оптимизационной задач
Задача оптимального использования ресурсов при изготовлении трех видов продукции на максимум общей стоимости, рекомендации относительно развития производства. Анализ алгоритма решения закрытой транспортной задачи с применением распределительного метода.
| Рубрика | Экономико-математическое моделирование |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 17.12.2013 |
| Размер файла | 81,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
3
Размещено на http://www.allbest.ru/
1. Линейная оптимизационная задача
транспортный задача ресурс
Для изготовления трех видов продукции используют три вида сырья. Запасы сырья, норма его расхода и прибыль от реализации каждого продукта приведены в таблице. На основании информации, приведенной в таблице решить задачу оптимального использования ресурсов на максимум общей стоимости.
|
Тип сырья |
Нормы расхода сырья на одно изделие |
Наличие ресурсов |
|||
|
А |
Б |
В |
|||
|
I |
1 |
2 |
1 |
430 |
|
|
II |
3 |
0 |
2 |
460 |
|
|
II |
1 |
4 |
0 |
420 |
|
|
Цены |
3 |
2 |
5 |
Решение: Составим математическую модель
Приведем задачу к каноническому виду
Решим задачу симплекс-методом
|
Шаг 0 |
||||||||
|
Базис |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
x 6 |
Свободный член |
|
|
x4 |
1 |
2 |
1 |
1 |
0 |
0 |
430 |
|
|
x5 |
3 |
0 |
2 |
0 |
1 |
0 |
460 |
|
|
x6 |
1 |
4 |
0 |
0 |
0 |
1 |
420 |
|
|
L |
-3 |
-2 |
-5 |
0 |
0 |
0 |
0 |
В строке коэффициентов целевой функции имеются отрицательные элементы, выберем минимальный из них (-5). В третьем столбце два положительных элемента, найдем минимальное симплексное отношение
Таким образом, ключевым элементом является 2
Разделим ключевую вторую строку на 2 и вычтем ее из первой строки.
Умножим преобразованную ключевую строку на 5 и сложим ее с четвертой строкой. В итоге над ключевым элементом и под ним будут получены нули. Х5 выводится из базиса, его место занимает Х3. Симплекс-таблица принимает вид:
|
Шаг 1 |
||||||||
|
Базис |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
x 6 |
СЧ |
|
|
x4 |
-1/2 |
2 |
0 |
1 |
-1/2 |
0 |
200 |
|
|
x3 |
3/2 |
0 |
1 |
0 |
1/2 |
0 |
230 |
|
|
x6 |
1 |
4 |
0 |
0 |
0 |
1 |
420 |
|
|
L |
9/2 |
-2 |
0 |
0 |
5/2 |
0 |
1150 |
В строке целевой функции имеется отрицательный элемент (-2).
Во втором столбце имеется два положительных элемента. Найдем минимальное симплексное отношение
Таким образом, ключевым элементом является 2.
Разделим первую строку на 2
Умножим преобразованную первую строку на 4 и вычтем ее из третьей строки.
Умножим преобразованную первую строку на 2 и сложим ее с четвертой строкой. Х4 выводится из базиса, его место занимает Х2. Получаем таблицу. В строке целевой функции нет отрицательных элементов, значит задача решена.
|
Шаг 2 |
||||||||
|
Базис |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
x 6 |
СЧ |
|
|
x2 |
-1/4 |
1 |
0 |
1/2 |
-1/4 |
0 |
100 |
|
|
x3 |
3/2 |
0 |
1 |
0 |
1/2 |
0 |
230 |
|
|
x6 |
2 |
0 |
0 |
-2 |
1 |
1 |
20 |
|
|
L |
4 |
0 |
0 |
1 |
2 |
0 |
1350 |
Снимает ответ. Переменные, вошедшие в базис, приравниваем к свободным членам. Переменные, которые не вошли в базис, равны нулю.
Таким образом, рекомендуем предприятию выпускать продукцию второго типа в объеме 100 ед., продукцию третьего типа в объеме 230 ед., а продукцию первого типа выпускать нецелесообразно. При этом первый и второй ресурс будут израсходованы полностью, а третьего останется 20 ед.
Подставляем значения переменных в целевую функцию
2. Транспортная задача
|
Стоимость перевозки единицы продукции |
Объем производства |
|||||
|
3 |
9 |
4 |
5 |
40 |
||
|
1 |
8 |
5 |
3 |
10 |
||
|
7 |
2 |
1 |
4 |
30 |
||
|
2 |
4 |
10 |
6 |
20 |
||
|
Объем потребления |
50 |
10 |
30 |
10 |
Решение: Транспортная задача закрытая, так как суммарные запасы =40+10+30+20=100 и суммарные потребности =50+10+30+10=100 совпадают.
Строим опорный план (методом минимального тарифа) с базисными клетками.
|
ai bj |
50 |
10 |
30 |
10 |
Потенциал |
|
|
40 |
3 20 |
9 10 |
4 Х |
5 10 |
U 1 |
|
|
10 |
1 10 |
8 Х |
5 Х |
3 Х |
U 2 |
|
|
30 |
7 Х |
2 Х |
1 30 |
4 Х |
U 3 |
|
|
20 |
2 20 |
4 Х |
10 Х |
6 Х |
U 4 |
|
|
Потенциал |
V 1 |
V 2 |
V 3 |
V4 |
Вначале заполним клетку (3;3). Она имеет минимальный тариф, равный единице. Третий поставщик исчерпал себя и третий потребитель удовлетворен.
Находим во всей таблице минимальный тариф. Его имеет клетка (2;1) и он равен 10. Поставляем в нее груз равный десяти от второго поставщика. Второй поставщик исчерпал себя.
Вновь находим во всей таблице минимальный тариф. Он равен 2 его имеет клетка (4;1). Поставляем первому потребителю груз 20 от четвертого поставщика. Четвертый поставщик исчерпал себя.
Находим во всей таблице минимальный тариф. Его имеет клетка (1;1). Этот тариф равен 3. Поставляем первому потребитель груз 20 от первого поставщика. Первый потребитель удовлетворен.
Находим в первой строке минимальный тариф. Он равен 5. Поставляем четвертому потребителю от первого поставщика груз 10. Четвертый потребитель удовлетворен.
Поставляем груз 10 в клетку (1;2). Первый поставщик исчерпал себя и второй потребитель удовлетворен.
|
ai bj |
50 |
10 |
30 |
10 |
Потенциал |
|
|
40 |
3 20 |
9 10 |
4 Х |
5 10 |
U 1 |
|
|
10 |
1 10 |
8 Х |
5 Х |
3 Х |
U 2 |
|
|
30 |
7 Х |
2 Х |
1 30 |
4 Х |
U 3 |
|
|
20 |
2 20 |
4 Х |
10 Х |
6 Х |
U 4 |
|
|
Потенциал |
V 1 |
V 2 |
V 3 |
V4 |
Проверим план на оптимальность.
Для составления уравнений потенциалов заполним две клетки нулями.
Найдем оценки свободных клеток
Дij = cij- (ui + vj ) от тарифа отнимем сумму потенциалов
Д13 = c13- (u1 + v3 )=5-(0+4)=1
Д22 = c22.- (u2 + v2 )=8-(-2+9)=1
Д24 = c24 - (u2 + v4 )=3-(-2-1)=6
Д23 = c23 - (u2 + v3 )=5-(-2+4)=3
Д31 = c31 - (u3+ v1 )=7-(-3+3)=7
Д32 = c32 - (u3+ v2 )=2-(-3+9)=-4
Д34 = c34 - (u3+ v4 )=4-(-3-1)=8
Д42 = c42 - (u4+ v2 )=4-(-1+9)=-4
Д43 = c43 - (u4+ v3 )=10-(-1+4)=7
Д44 = c44 - (u4+ v4 )=6-(-1-1)=4
Так как имеются отрицательные оценки план не является оптимальным.
Возьмем в качестве перспективной клетку (3;2).
Построим на ее базе цикл.
Присвоим перспективной клетке знак +, далее по часовой стрелке клеткам присвоим знаки, чередуя их.
Будем перемешать минимальный груз, получивший знак минус. Этот груз равен 10. Если встречаем клетку со знаком плюс прибавляем в нее груз 10, если со знаком минус, вычитаем этот груз. В итоге получим следующий цикл.
После применения распределительного метода имеем таблицу
|
ai bj |
50 |
10 |
30 |
10 |
Потенциал |
|
|
40 |
3 20 |
9 Х |
4 10 |
5 10 |
U 1 |
|
|
10 |
1 10 |
8 Х |
5 Х |
3 Х |
U 2 |
|
|
30 |
7 Х |
2 10 |
1 20 |
4 Х |
U 3 |
|
|
20 |
2 20 |
4 Х |
10 Х |
6 Х |
U 4 |
|
|
Потенциал |
V 1 |
V 2 |
V 3 |
V4 |
Проверим найденный план на оптимальность. Уравнения потенциалов имеют вид:
Д22 = c22 - (u2 + v2 )=8-(-2+5)=5
Д24 = c24 - (u2 + v4 )=3-(-2-1)=6
Д23 = c23 - (u2 + v3 )=5-(-2+4)=3
Д31 = c31 - (u3+ v1 )=7-(-3+3)=7
Д34 = c34 - (u3+ v4 )=4-(-3-1)=8
Д42 = c42 - (u4+ v2 )=4-(-1+5)=0
Д43 = c43 - (u4+ v3 )=10-(-1+4)=7
Д44 = c44 - (u4+ v4 )=6-(-1+5)=5
Таким образом, план оптимален, так как все оценки положительны.
Нулевая оценка свидетельствует о том, что план не является единственным.
Найдем стоимость плана
Ответ:
Размещено на Allbest.ru
Подобные документы
Графический метод решения задачи оптимизации производственных процессов. Применение симплекс-алгоритма для решения экономической оптимизированной задачи управления производством. Метод динамического программирования для выбора оптимального профиля пути.
контрольная работа [158,7 K], добавлен 15.10.2010Формулировка проблемы в практической области. Построение моделей и особенности экономико-математической модели транспортной задачи. Задачи линейного программирования. Анализ постановки задач и обоснования метода решения. Реализация алгоритма программы.
курсовая работа [56,9 K], добавлен 04.05.2011Математическая формализация оптимизационной проблемы. Геометрическая интерпретация стандартной задачи линейного программирования, планирование товарооборота. Сущность и алгоритм симплекс-метода. Постановка транспортной задачи, последовательность решения.
учебное пособие [126,0 K], добавлен 07.10.2014Применение линейного программирования для решения транспортной задачи. Свойство системы ограничений, опорное решение задачи. Методы построения начального опорного решения. Распределительный метод, алгоритм решения транспортной задачи методом потенциалов.
реферат [4,1 M], добавлен 09.03.2011Основные подходы и способы решения транспортной задачи, ее постановка и методы нахождения первоначального опорного решения. Математическая модель транспортной задачи и алгоритм ее решения методом потенциалов. Составление опорного плана перевозок.
курсовая работа [251,0 K], добавлен 03.07.2012Составление математической модели задачи. Расчёт оптимального плана перевозок с минимальной стоимостью с использованием метода потенциалов. Оптимальный вариант специального передвижного оборудования для технического обеспечения управления производством.
контрольная работа [135,3 K], добавлен 01.06.2014Виды задач линейного программирования и формулировка задачи. Сущность оптимизации как раздела математики и характеристика основных методов решения задач. Понятие симплекс-метода, реальные прикладные задачи. Алгоритм и этапы решения транспортной задачи.
курсовая работа [268,0 K], добавлен 17.02.2010Понятие классической транспортной задачи, классификация задач по критерию стоимости и времени. Методы решения задач: симплекс, северо-западного угла (диагональный), наименьшего элемента, потенциалов решения, теория графов. Определение и применение графов.
курсовая работа [912,1 K], добавлен 22.06.2015Особенности формирования и способы решения оптимизационной задачи. Сущность экономико-математической модели транспортной задачи. Характеристика и методика расчета балансовых и игровых экономико-математических моделей. Свойства и признаки сетевых моделей.
практическая работа [322,7 K], добавлен 21.01.2010Особенности решения задач линейного программирования симплекс-методом. Управляемые параметры, ограничения. Изучение метода потенциалов в процессе решения транспортной задачи. Создание концептуальной модели. Понятие стратификации, детализации, локализации.
лабораторная работа [869,0 K], добавлен 17.02.2012
