Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Топ:
Комплексной системы оценки состояния охраны труда на производственном объекте (КСОТ-П): Цели и задачи Комплексной системы оценки состояния охраны труда и определению факторов рисков по охране труда...
Устройство и оснащение процедурного кабинета: Решающая роль в обеспечении правильного лечения пациентов отводится процедурной медсестре...
Когда производится ограждение поезда, остановившегося на перегоне: Во всех случаях немедленно должно быть ограждено место препятствия для движения поездов на смежном пути двухпутного...
Интересное:
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Аура как энергетическое поле: многослойную ауру человека можно представить себе подобным...
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Дисциплины:
 2019-08-04 |
 125 |
из
5.00
|
Заказать работу |
|
|
|
|
СПЕЦИАЛЬНОСТЬ «Менеджмент организаций»
К О Н Т Р О Л Ь Н А Я Р А Б О Т А
По предмету: Экономико-математический практикум
Выполнил:
Студент 2 курса
Семестр
Рахимова Лидия Рустамовна
Ташкент,2009
Задача № 1
Условно стандартная задача линейного программирования
Необходимо выполнить в указанном порядке следующие задания.
1. Найти оптимальный план прямой задачи:
а) графическим методом;
б) симплекс-методом (для построения исходного опорного плана рекомендуется использовать метод искусственного базиса).
2. Построить двойственную задачу.
3. Найти оптимальный план двойственной задачи из графического решения прямой, используя условия дополняющей нежесткости.
4. Найти оптимальный план двойственной задачи по первой теореме двойственности, используя окончательную симплекс-таблицу, полученную при решении прямой задачи (см. п. 1б). Проверить утверждение «значения целевых функций пары двойственных задач на своих оптимальных решениях совпадают».
5. Двойственную задачу решить симплекс-методом, затем, используя окончательную симплекс-таблицу двойственной задачи найти оптимальный план прямой задачи по первой теореме двойственности. Сравнить результат с результатом, который был получен графическим методом (см. п. 1а).
6. Найти оптимальное целочисленное решение:
а) графическим методом;
б) Методом Гомори.
Сравнить значения функций целочисленного и нецелочисленного решений
4 
Решение задачи 1
1. Найдем оптимальный план решения графическим методом:
;
Построим на координатной плоскости Ох 1 х 2 граничные прямые области допустимых решений (номера прямых соответствуют их порядковому номеру в системе):
|
|
Область допустимых решений определяется многоугольником ОАВС D (см. график 1).
Для линий уровня х 1 - 3 х 2 = h (h — const) строим нормальный вектор 
. Перпендикулярно нормальному вектору построим одну из линий уровня (на рис. 1 она проходит через начало координат) Так как задача на минимум, то перемещаем линию уровня в направлении вектора 
до опорной прямой. В данном случае опорной прямой является прямая, проходящая через точку пересечения граничных прямых L 3 и L 4, т. е. через точку 
. Для определения координат точки P решаем систему уравнений
.
Получаем х 1 = 5,3, х 2 = 0,6. Это и будет оптимальным решением данной задачи, которому соответствует минимальное значение целевой функции Z min=3,5
 |
|
|
|
|
|
| ||||||
| ||||||
| ||||||
График № 1
1б) Перейдем к расширенной задаче:
Данная расширенная задача имеет начальное опорное решение 
с базисом 
. Вычисляем оценки векторов условий по базису опорного решения и значение целевой функции на опорном решении:
Расчеты проведем в таблице (Табл. 1)
Таблица 1
| 1 | -3 | 0 | 0 | 0 | 0 | M | ||||
| Б | Сб | В | А 1 | А 2 | А 3 | А 4 | А 5 | А 6 | А 7 | |
| А 3 | 0 | 9 | -2 | 3 | 1 | 0 | 0 | 0 | 0 | |
| А 4 | 0 | 53 | 5 | 2 | 0 | 1 | 0 | 0 | 0 | |
| А 5 | 0 | 17 | 4 | -7 | 0 | 0 | 1 | 0 | 0 | |
| ← | А 7 | М | 37 | 6 | 8 | 0 | 0 | 0 | 1 | 1 |
|
| 0 | –1 | 3 | 0 | 0 | 0 | 0 | 0 | ||
|
| 37 | 6 | 8 | 0 | 0 | 0 | 0 | 0 | ||
Начальное опорное решение не является оптимальным, так как в задаче на минимум имеются положительные оценки. Выбираем номер вектора А k, вводимого в базис опорного решения, и вектора А l, выводимого из базиса. Наибольшая положительная оценка соответствует А2, за разрешающий элемент выбираем коэффициент 8 и выполняем преобразование Жордана.
Вектор А2 выводимый из базиса, исключаем из рассмотрения (вычеркиваем). Получаем второе опорное решение 
с базисом 
(табл. 1.3). Целевая функция 
=-3 М -21. Это решение не является оптимальным, так как есть положительная оценка.
|
|
Таблица 1
| Б | Сб | B | А 1 | А 2 | А 3 | А 4 | А 5 | А 6 | |
| А2 | -3 | 3,0 | -0,7 | 1,0 | 0,3 | 0,0 | 0,0 | 0,0 | 0,0 |
| А 4 | 0 | 47,0 | 6,3 | 0,0 | -0,7 | 1,0 | 0,0 | 0,0 | 0,0 |
| А 5 | 0 | 38,0 | -0,7 | 0,0 | 2,3 | 0,0 | 1,0 | 0,0 | 0,0 |
| a7 | М | 13,0 | 11,3 | 0,0 | -2,7 | 0,0 | 0,0 | 1,0 | 1,0 |
| M+1 | -9,0 | 1,0 | 0,0 | -1,0 | 0,0 | 0,0 | 0,0 | 0,0 | |
| M+2 | 13,0 | 11,3 | 0,0 | -2,7 | 0,0 | 0,0 | 0,0 | 0,0 | |
| A2 | -3 | -2,4 | -0,6 | 1,0 | 0,0 | 0,0 | -0,1 | 0,0 | 0,0 |
| a4 | 0 | 57,9 | 6,1 | 0,0 | 0,0 | 1,0 | 0,3 | 0,0 | 0,0 |
| А 3 | 0 | 16,3 | -0,3 | 0,0 | 1,0 | 0,0 | 0,4 | 0,0 | 0,0 |
| A7 | М | 56,4 | 10,6 | 0,0 | 0,0 | 0,0 | 1,1 | 1,0 | 1,0 |
| M+1 | 7,3 | 0,7 | 0,0 | 0,0 | 0,0 | 0,4 | 0,0 | 0,0 | |
| M+2 | 56,4 | 10,6 | 0,0 | 0,0 | 0,0 | 1,1 | 0,0 | 0,0 | |
| A2 | -3 | 0,6 | 0,0 | 1,0 | 0,0 | 0,0 | -0,1 | 0,1 | 0,1 |
| a4 | 0 | 25,1 | 0,0 | 0,0 | 0,0 | 1,0 | -0,4 | -0,6 | -0,6 |
| А 5 | 0 | 17,8 | 0,0 | 0,0 | 1,0 | 0,0 | 0,5 | 0,0 | 0,0 |
| A1 | 1 | 5,3 | 1,0 | 0,0 | 0,0 | 0,0 | 0,1 | 0,1 | 0,1 |
|
|
| 3,5 | 0,0 | 0,0 | 0,0 | 0,0 | 0,4 | -0,1 | -0,1 |
|
|
| 0,0 | 0,0 | 0,0 | 0,0 | 0,0 | 0,0 | -1,0 | -1,0 |
Целевая функция после второй итерации равна 
= 3,5. Все оценки отрицательные, план оптимален.
Оптимальный план исходной задачи Х*=(х1*=5,3; х2*=0,6). Минимальное значение целевой функции исходной задачи =3,5.
Ответ: min Z (X *) =3,5.
Двойственная задача
Двойственная задача имеет вид.
при условиях
Задача № 2
Каноническая задача
В каждом варианте приведены таблицы, в которых записаны условия канонической задачи линейного программирования на минимум, т. е.
В первой строке помещены коэффициенты целевой функции. В остальных строках, в первых пяти столбцах, находятся векторы условий, а в последнем столбце записан вектор ограничений. В правом верхнем углу таблицы указана цель задачи.
Необходимо последовательно выполнить следующие задания.
1. Задачу решить графическим методом.
2. Применяя симплекс-метод, решить задачу, т.е. найти ее оптимальный план 
и минимальное значение целевой функции 
или установить, что задача не имеет решения. Начальный план рекомендуется искать методом искусственного базиса.
3. Построить двойственную задачу. Если вектор найден, вычислить оптимальный план 
двойственной задачи, используя первую теорему двойственности 
. Вычислить максимальное значение функции 
.
4. Провести анализ полученного решения, применяя условия дополняющей нежесткости.
Если 
, то 
.
Если 
, то 
.
| 14 | ||||||
| 1 | -5 | 6 | 8 | -2 | min | |
| 11 | 7 | 1 | 12 | 5 | 16 | |
| 14 | 10 | 0 | 3 | 8 | 17 | |
| 13 | 2 | 9 | 4 | 6 | 15 | |
Решение задачи 2
|
|
Представим исходные данные задачи в виде:
Проверяем, применим ли графический метод при решении данной задачи.
линейно независимы, так как их координаты непропорциональны. Поэтому ранг системы векторов-условий r = 3. Находим n - r =5 - 3 = 2 £ 2. Следовательно, метод применим.
1. Приведём систему уравнений-ограничений к равносильной, разрешённой методом Жордана–Гаусса. Преобразуем систему уравнений методом Жордана-Гаусса до получения общего решения (табл. 2.1).
Таблица 2.1.
| № итерац. | x1 | x2 | x3 | x4 | x5 | bi |
|
(1) | 11 | 7 | 1 | 12 | 5 | 16 |
| 14 | 10 | 0 | 3 | 8 | 17 | |
| 13 | 2 | 9 | 4 | 6 | 15 | |
|
(2) | -45,00 | -33,00 | 1,00 | 0,00 | -27,00 | -52,00 |
| 4,67 | 3,33 | 0,00 | 1,00 | 2,67 | 5,67 | |
| -5,67 | -11,33 | 9,00 | 0,00 | -4,67 | -7,67 | |
|
(3) | 2,25 | 0,75 | 1,00 | 10,13 | 0,00 | 5,38 |
| 1,75 | 1,25 | 0,00 | 0,38 | 1,00 | 2,13 | |
| 2,50 | -5,50 | 9,00 | 1,75 | 0,00 | 2,25 | |
| (4) | -12,21 | 32,57 | -51,07 | 0,00 | 0,00 | -7,64 |
| 1,21 | 2,43 | -1,93 | 0,00 | 1,00 | 1,64 | |
| 1,43 | -3,14 | 5,14 | 1,00 | 0,00 | 1,29 | |
| (5) | 0,24 | -0,64 | 1,00 | 0,00 | 0,00 | 0,15 |
| 1,68 | 1,20 | 0,00 | 0,00 | 1,00 | 1,93 | |
| 0,20 | 0,14 | 0,00 | 1,00 | 0,00 | 0,52 |
Общее решение системы уравнений имеет вид
Учитывая, что все переменные неотрицательны, перейдем от уравнений к неравенствам из общего решения системы.
откуда получим систему неравенств с двумя переменными
Целевую функцию выразим через свободные переменные
Окончательно получим стандартную задачу линейного программирования с двумя переменными
Строим область допустимых решений (график 2). Любая точка многоугольника 
удовлетворяет системе неравенств. Вершина 
является точкой входа семейства прямых 
в область решений, следовательно, в этой точке она принимает минимальное значение.
В свою очередь, 
=(1,32;0,12).
Решая систему уравнений получаем х1 =2,2, х2 =0,6. Это и будет оптимальным решением данной задачи, которому соответствует минимальное значение целевой функции Z min
.
 |
|
|
A
А 
|
 | |||
| |||
(3)
График 2
Задача № 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.
| Поставщики | Потребители | Запасы | ||||
| 
| 
| 
| 
| ||
| 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 | < | ||||||||||||||
|
|
|
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!
