Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Топ:
История развития методов оптимизации: теорема Куна-Таккера, метод Лагранжа, роль выпуклости в оптимизации...
Теоретическая значимость работы: Описание теоретической значимости (ценности) результатов исследования должно присутствовать во введении...
Методика измерений сопротивления растеканию тока анодного заземления: Анодный заземлитель (анод) – проводник, погруженный в электролитическую среду (грунт, раствор электролита) и подключенный к положительному...
Интересное:
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Дисциплины:
 2019-08-04 |
 130 |
из
5.00
|
Заказать работу |
|
|
|
|
Используя вторую симметричную пару двойственных задач, составим задачу, двойственную к исходной:
Вводим неотрицательные дополнительные переменные у 4, у 5, у 6 у 7, у 8 для приведения задачи к каноническому виду:
Находим начальное опорное решение Y 1 = (0,0,0,1,-5,6,8,-2) с базисом Б1 = (А 4, А 5, А 6, А 7, А 8). Решение задачи симплексным методом приведено в табл. 2.5. (расчеты табл.2.2. и табл.2.4.)
Таблица 2.5
|
| 1 | -5 | 6 | 8 | -2 | М | M | M | |||||
| Б | Сб | А 0 | А 1 | А 2 | А 3 | А 4 | А 5 | А 6 | A7 | A8 | |||
| ← | А 6 | М | 16 | 11 | 7 | 1 | 12 | 5 | 1 | 0 | 0 | ||
| A7 | M | 17 | 14 | 10 | 0 | 3 | 8 | 0 | 1 | 0 | |||
| А 8 | М | 15 | 13 | 2 | 9 | 4 | 6 | 0 | 0 | 1 | |||
|
| 0 | -1 | 5 | -6 | -8 | 2 | 0 | 0 | 0 | ||||
|
| 48 | 28 | 19 | 10 | 19 | 19 | 0 | 0 | 0 | ||||
| a1 | 1 | 2,60 | 1,00 | 0,69 | 0,00 | 5,04 | 0,00 | 0,51 | -0,27 | -0,06 | |||
| a5 | -2 | -2,42 | 0,00 | 0,04 | 0,00 | -8,44 | 1,00 | -0,89 | 0,61 | 0,10 | |||
| a3 | 6 | -0,47 | 0,00 | -0,80 | 1,00 | -1,20 | 0,00 | -0,14 | -0,01 | 0,13 | |||
| 4,19 | 0,00 | -0,79 | 0,00 | -6,68 | 0,00 | -1,44 | 1,53 | -0,51 | ||||
|
| 25,99 | 0,00 | 6,90 | 0,00 | 50,35 | 0,00 | 4,07 | -3,75 | -1,56 | ||||
Приведем оптимальное решение прямой задачи
Окончательный базис, соответствующий оптимальному решению прямой задачи, состоит из векторов А2А3А4 поэтому базисная матрица имеет вид
Решение прямой задачи начиналось с единичного базиса А6,А7,А8 . Поэтому в окончательной таблице указанные столбцы преобразуются в матрицу 
, обратную к базисной матрице 
, следовательно,
Оптимальный план двойственной найдем из соотношения
Откуда 
При этом плане максимальное значение функции двойственной задачи составляет величину равную
Максимальное значение целевой функции двойственной задачи совпадает с минимальным значением целевой функции прямой задачи.
|
|
5. Проанализируем решение задачи, используя условия дополняющей нежесткости (вторую теорему двойственности).
Подставляем координаты оптимального решения двойственной задачи 
в систему ограничений.
Первое, третье и пятое ограничения выполняются как строгие неравенства, следовательно, их координаты оптимального решения исходной задачи равны нулю: 
. Учитывая это, первую, вторую и пятую координаты оптимального решения Х * находим при совместном решении уравнений-ограничений исходной задачи:
Ответ: Z (X) = 4,2 при Х * = (0;1,6; 0;4,9;0).
Задача № 3
Транспортная задача
Ниже приведены числовые данные транспортных задач. Стоимость перевозки единицы продукции записаны в клетках таблицы. Запасы указаны справа от таблиц, а потребности – снизу. Требуется построить начальный план методами: «северо-западного угла», «минимального элемента», «двойного предпочтения», методом Фогеля. Из каждого плана найти оптимальный план методом потенциалов.
| 24 | ||||||
| 34 | 30 | 39 | 29 | 18 | 82 | |
| 40 | 35 | 45 | 41 | 10 | 36 | |
| 36 | 38 | 41 | 50 | 8 | 79 | |
| 14 | 10 | 13 | 10 | 12 | 80 | |
| 77 | 60 | 22 | 68 | 50 | ||
Решение.
Метод северо-западного угла.
Исходные данные задачи сведем в таблицу (табл. 3.1).
Таблица 3.1.
| Поставщики | Потребители | Запасы | ||||
| 
| 
| 
| 
| ||
| 34 | 30 | 39 | 29 | 18 | 82 |
| 40 | 35 | 45 | 41 | 10 | 36 |
| 36 | 38 | 41 | 50 | 8 | 79 |
| 14 | 10 | 13 | 10 | 12 | 8 0 |
| Потребности | 77 | 60 | 22 | 6 8 | 50 | |
Решение. Построим опорный план задачи методом северо-западного угла.
Объем перевозки 
и последовательность заполнения матрицы 
будем записывать в соответствующие клетки табл. 3.2.
Цифры, стоящие в скобках над объемами перевозок, обозначают номер шага, на котором определяются эти перевозки.
1. х11(1)=min(82,77)=77. Потребности первого потребителя удовлетворены, исключаем его. Запасы первого поставщика уменьшились на х11(1) и стали равны (82-77=5) 5.
2. х12(1)=min(5,60)=5. Запасы первого поставщика исчерпаны, исключим первую строку. Второй потребитель удовлетворил свои потребности на 5 единиц, его спрос уменьшился на величину х11(1) и стал равным 55.
|
|
3. х22(3)=min(36,55)=36. После третьего шага ресурсы поставщика А2 исчерпаны. Спрос потребителя B2 равен b2(3)=55-36=19.
4. х23(4)=min(79,19)=19. Следует исключить потребителя B2. Ресурсы поставщика А3(4) = a3 – х23(4)=79-19=60 составляет 60 единиц.
5. х33(5)=min(60,22)=22. Потребитель В3 полностью удовлетворил свой спрос, исключаем столбец 3.
6. х34(6)=min(38,68)=38. Следует исключить поставщика А3, запасы которого исчерпаны. Спрос потребителя В4 в4(6) – х34(5)=68-38=30 составляет 30 единиц.
7. х44(7)=min(80,30)=30. Спрос четвертого потребителя удовлетворен. Запасы поставщика А4 составляет
80-30=50.
8. х45(8)=min(50,50)=0. Запасы исчерпаны, потребности удовлетворены.
Опорный план построен (табл. 3.2).
Таблица 3.2.
| 34 | 3 0 | 3 9 | 29 | 18 | |
| 77(1) | 5(2) | 82 | |||
| 4 0 | 35 | 4 5 | 41 | 10 | |
| 36(3) | 36 | ||||
| 36 | 3 8 | 41 | 50 | 8 | |
| 19(4) | 22(5) | 38(6) | 79 | ||
| 1 4 | 1 0 | 1 3 | 1 0 | 1 2 | |
| 30(7) | 50(8) | 8 0 | |||
| 7 7 | 60 | 22 | 6 8 | 50 |
Суммарные транспортные издержки на перевозку продукции от поставщиков к потребителю составляют
2.Метод минимального элемента.
Исходные данные
| поставщики | потребители | Запасы | ||||
| В1 | В2 | В3 | В4 | В5 | ||
| А1 | 34 | 30 | 39 | 29 | 18 | 82 |
| А2 | 40 | 35 | 45 | 41 | 10 | 36 |
| А3 | 36 | 38 | 41 | 50 | 8 | 79 |
| А4 | 14 | 10 | 13 | 10 | 12 | 8 0 |
| потребности | 77 | 60 | 22 | 6 8 | 50 | |
1. 
Объем запасов и потребностей после первого шага уменьшается на величину: х31(1)=50; 
. Запасы пятого поставщика исчерпаны, потребности первого потребителя уменьшились на 50 единиц и стали равны 29, исключаем пятый столбец.
2. 
. Объем запасов и потребностей после второго шага уменьшается на величину: х42(2)=60; 
. Потребности пункта В2 удовлетворены, исключим из рассмотрения второй столбец.
3. 
. Объем запасов и потребностей после третьего шага уменьшается на величину: х44(3)=20; 
. Запасы пункта А4 исчерпаны, исключим из рассмотрения четвертую строку.
4. 
. Корректируем объемы запасов и потребностей после четвертого шага: 
. Потребности пункта В4 удовлетворены, исключим четвертый столбец.
5. 
. После пятого шага запасы поставщика А1 будут исчерпаны, исключаем первую строку. Потребности В1 равны: 
.
6. 
. После шестого шага запасы третьего поставщика будут исчерпаны 
, потребности первого потребителя равны 
. Исключаем третью строку.
7. 
. После седьмого шага запасы второго поставщика будут равны 
, потребности первого потребителя удовлетворены.
|
|
8. 
. После восьмого шага запасы и потребности будут удовлетворены.
Потребности всех потребителей удовлетворены, запасы поставщиков исчерпаны. После седьмого шага мы получили исходный опорный план 
(Табл.3.3).
Х0 Таблица 3.3.
| 34 | 30 | 39 | 29 | 18 | |
| 34(5) | 48(4) | 82 | |||
| 40 | 35 | 45 | 41 | 10 | |
| 14(7) | 22(8) | 36 | |||
| 36 | 38 | 41 | 50 | 8 | |
| 29(6) | 50(1) | 79 | |||
| 14 | 10 | 13 | 10 | 12 | |
| 60(2) | 20(3) | 80 | |||
| 77 | 60 | 22 | 68 | 50 |
Также как и в предыдущем случае, номер шага помещен в скобках над объемами перевозок. Суммарные транспортные расходы, соответствующие данному плану перевозок равны
По сравнению с расчетом по методу северо-западного угла суммарные транспортные расходы уменьшились с 8452 у.е. до 6342 у.е.
Для проверки плана на оптимальность составим систему уравнений, следуя условию — для базисных переменных сумма потенциалов равна тарифу. Значение одного из потенциалов зададим произвольно (пусть 
), последовательность вычисления остальных потенциалов указана ниже: 1), 2),…, 8).
Потенциалы поставщиков 
поместим слева от таблицы, а потенциалы потребителей 
– сверху над таблицей (табл.3.4).
Таблица 3.4
| 34 | 29 | 39 | 29 |
| 6 |
| |||||||||||||
| 0 | 34 | 30 | 39 | 29 | 18 |
| |||||||||||||
| 34(5) | 48(4) |
|
| 82 | |||||||||||||||
|
| -1 | 0 |
|
| -12 | ||||||||||||||
| 6 | 40 | 35 | 45 | 41 | 10 | ||||||||||||||
| 14(7) | 22(8) |
|
| 36 | |||||||||||||||
|
| 0 |
| -6 | -2 | |||||||||||||||
| 2 | 36 | 38 | 41 | 50 | 8 | ||||||||||||||
| 29(6) |
| 50(1) | 79 | ||||||||||||||||
|
| -7 | 0 | -19 |
| |||||||||||||||
| -19 | 14 | 10 | 13 | 10 | 12 | ||||||||||||||
| 60(2) | 20(3) |
|
| 80 | |||||||||||||||
| 1 |
| 7 |
| -25 | |||||||||||||||
| 77 | 60 | 22 | 68 | 50 |
| ||||||||||||||
|
|
Для небазисных переменных вычислим оценки по формуле:
Значения оценок поместим в левом нижнем углу незанятых клеток табл. 3.4. Фиксируем наибольшую положительную оценку. В данном случае: 
. Разрешающей объявим коммуникацию (4,3). Строим цикл пересчета, который показан в табл. 3.4 пунктирной линией.
Величина корректировки ρ=(58,79)=58. Вносим изменение в план: перевозки отрицательного полуцикла уменьшаем на 
, а перевозки положительного полуцикла увеличиваем на эту же величину, остальные перевозки оставим без изменения. Переменная х11 вводится в базис со значением =58,переменная х14 выводится из базиса. Получим план 
(табл. 3.5).
План 
Таблица 3.5
| 34 | 29 | 39 | 29 |
| 6 |
| |||||||||||||
| 0 | 34 | 30 | 39 | 29 | 18 |
| |||||||||||||
| 34(5) | 48(4) |
|
| 82 | |||||||||||||||
|
| -1 | 0 |
|
| -12 | ||||||||||||||
| 6 | 40 | 35 | 45 | 41 | 10 | ||||||||||||||
| 14(7) | 22 |
|
| 36 | |||||||||||||||
|
| 0 |
| -6 | -2 | |||||||||||||||
| 2 | 36 | 38 | 41 | 50 | 8 | ||||||||||||||
| 29(6) |
| 50(1) | 79 | ||||||||||||||||
|
| -7 | 0 | -19 |
| |||||||||||||||
| -19 | 14 | 10 | 13 | 10 | 12 | ||||||||||||||
| 60(2) | 20(3) |
|
| 80 | |||||||||||||||
| 1 |
| 7 |
| -25 | |||||||||||||||
| 77 | 60 | 22 | 68 | 50 |
| ||||||||||||||
Значение функции уменьшилось на (38*16-9*38=290) и стало: 
План не оптимален. Заново вычисляем потенциалы и оценки (табл. 3.6). Наибольшая положительная оценка– это 
, план не оптимален. Строим цикл пересчета и определяем величину корректировки плана ρ=(48,58)=48.
Таблица 3.6
План X2
| 34 | 29 | 39 | 29 |
| 6 |
| |||||||||||||
| 0 | 34 | 30 | 39 | 29 | 18 |
| |||||||||||||
| 14 | 68(4) |
|
| 82 | |||||||||||||||
|
| -1 | 0 |
|
| -12 | ||||||||||||||
| 6 | 40 | 35 | 45 | 41 | 10 | ||||||||||||||
|
| 36 | 36 | |||||||||||||||||
|
| 0 |
| -6 | -2 | |||||||||||||||
| 2 | 36 | 38 | 41 | 50 | 8 | ||||||||||||||
| 65 |
| 14 | 79 | ||||||||||||||||
|
| -7 | 0 | -19 |
| |||||||||||||||
| -19 | 14 | 10 | 13 | 10 | 12 | ||||||||||||||
| 12 | 46(2) | 22 |
|
| 80 | ||||||||||||||
| 1 |
| 7 |
| -25 | |||||||||||||||
| 77 | 60 | 22 | 68 | 50 |
| ||||||||||||||
Значение функции и соответственно транспортные расходы составили 
Положительных оценок нет, план Х2 оптимален.
Метод Фогеля
В табл. 3.4 показаны последовательность определения базисных переменных, наборы разностей 
в строках справа от таблицы, а 
в столбцах снизу под таблицей.
План Х0
Таблица 3.4
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |||||||
| 34 | 30 | 39 | 29 | 18 | 11 | 11 | 11 | 11 | 11 | 11 | - | - | ||
| 34(6) | 48(5) |
|
|
| 82 | |||||||||
| 40 | 35 | 45 | 41 | 10 | 25 | 25 | 25 | 25 | 25 | 25 | 25 | 25 | ||
| 14(7) |
| 22(8) |
|
| 36 | |||||||||
| 36 | 38 | 41 | 50 | 8 | 28 | 2 | - | - | - | - | - | - | ||
| 29(2) |
|
|
| 50(1) | 79 | |||||||||
| 14 | 10 | 13 | 10 | 12 | 2 | 2 | 2 | 2 | - | - | - | - | ||
|
| 12(4) |
| 68(3) |
| 80 | |||||||||
| 77 | 60 | 22 | 68 | 50 | ||||||||||
| Этап 1 | 20 | 20 | 26 | 19 | 2 | |||||||||
| Этап 2 | 20 | 20 | 26 | 19 | - | |||||||||
| Этап 3 | 20 | 20 | 26 | 19 | - | |||||||||
| Этап 4 | 20 | 20 | 26 | 12 | - | |||||||||
| Этап 5 | 20 | - | 26 | - | - | |||||||||
| Этап 6 | 20 | - | 26 | - | - | |||||||||
| Этап 7 | 16 | - | 26 | - | - | |||||||||
| Этап 8 | - | - | 26 | - | - |
Суммарные транспортные расходы, соответствующие данному плану перевозок равны
.
Сравним расчеты, проделанные тремя методами. Транспортные расходы, рассчитанные:
1) методом северо-западного угла составили 8452 у.е.,
2) методом минимального элемента соответственно 6342 у.е.,
3) пересчитанные по методу потенциалов – 6118 у.е.,
4) методом Фогеля соответственно – 6390 у.е.
Наименьшие транспортные расходы составили расходы, рассчитанные по методу потенциалов.
Задача № 4
Сетевая задача
Ниже приведено 10 вариантов транспортной задачи в сетевой постановке. Каждая задача изображена в виде неориентированного связного графа. На ребрах проставлены значения тарифов 
, на вершинах (в кружках) — значения запасов-потребностей 
. Построить пробный допустимый план, проверить его на оптимальность. В случае необходимости довести до оптимального плана методом потенциалов.
 |  | ||||||||||||
| |||||||||||||
|
| ||||||||||||
 | |||||||||||||
 | |||||||||||||
Решение. Построим пробный опорный план (рис.1).
 | |||||
 | |||||
 | |||||
Рис. 1. Пробный план перевозок по сети.
В качестве начальной выберем вершину 12, которая является поставщиком с запасами в 20 единиц продукции. Из этой вершины отправим транзитом через 13 с запасами 45 ед. и 10 вершину с запасами 30 единиц в 8 вершину и удовлетворяем её потребности в 40 единиц. Оставшиеся 55 единиц отправим в 6 вершину с потребностями 40 единиц, оставшиеся 15 единиц отправляем в 5 вершину с потребностями 10 единиц, оставшиеся 5 единиц направим в 1 вершину, потребности которой составляют 35 единиц.
Из 11 вершины с запасами 45 единиц направим транзитом через 9 вершину, всего запасов стало 75 единиц, направим их транзитом через 7 вершину в 4 вершину, потребности которой составляют 40 единиц, оставшиеся 35 единиц направим во 2 вершину и удовлетворим ее потребности.
Из 3 вершины с запасами 30 единиц направим транзитом через 7 вершину в 1 вершину, потребности которой удовлетворим.
В результате проведенных операций все запасы вывезены, потребности всех потребителей удовлетворены.
В результате проведенных операций все запасы вывезены, потребности всех потребителей удовлетворены. Число базисных ребер здесь равно 11, число вершин 13.
Итак, полученный план является опорным, так как удовлетворяет всем требованиям опорного плана. Значение функции, которое соответствует построенному плану равно
.
Проверку плана на оптимальность осуществим с помощью метода потенциалов.
Одной из вершин (например, 1) зададим произвольное значение потенциала α1=0. Запишем его около вершины 1.
Затем, двигаясь по базисным ребрам, вычисляем потенциалы остальных вершин.
; 
; 
;
; 
;
; 
; 
;
<
|
|
|
Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!
