Раздел I. Тема 1. Решить задачу линейного программирования графическим методом

1. при следующих ограничениях:	2. при следующих ограничениях:
3. при следующих ограничениях:	4. при следующих ограничениях:
5. при следующих ограничениях:	6. при следующих ограничениях:
7. при следующих ограничениях:	8. при следующих ограничениях:
9. при следующих ограничениях:	10. при следующих ограничениях:

Раздел I. Тема 2. Решить задачу целочисленного линейного программирования методом ветвей и границ, учитывая целочисленность переменных.

 

Вариант 1.	Вариант 2.
max (2x1+3x2) 4x1+5x2 < = 20 x1+6x2 < = 12 0 < = x1 < = 5 0 < = x2 < = 4	max (x1+2x2) 3x1+7x2 < = 21 x1+x2 < = 4 0 < = x1 < = 4 0 < = x2 < = 3
Вариант 3.	Вариант 4.
max (x1+3x2) 3x1+4x2 < = 12 3x1+2x2 < = 6 0 < = x1 < = 4 0 < = x2 < = 2	max (4x1+x2) 2x1-3x2 < = 6 4x1+9x2 < = 18 0 < = x1 < = 2 0 < = x2 < = 3
Вариант 5.	Вариант 6.
max (3x1+x2) 4x1+3x2 < = 18 x1+2x2 < = 6 0 < = x1 < = 5 0 < = x2 < = 3	max (x1+2x2) x1+x2 < = 5 3x1+8x2 < = 24 0 < = x1 < = 5 0 < = x2 < = 3
Вариант 7.	Вариант 8.
max (2x1+x2) 5x1+2x2 < = 30 3x1+8x2 < = 48 0 < = x1 < = 6 0 < = x2 < = 6	max (3x1-2x2) 2x1+3x2 < = 6 x1-2x2 < = 2 0 < = x1 < = 3 0 < = x2 < = 3
Вариант 9.	Вариант 10.
min (3x1+2x2) 2x1+x2 > =6 4x1+3x2 > =6 0 < = x1 < = 3 1 < = x2 < = 2	max (x1+2x2) 5x1+9x2 < = 45 x1+3x2 < = 12 0 < = x1 < = 9 0 < = x2 < = 4

Раздел II. Тема 3. Решить методом ветвей и границ следующую задачу коммивояжера:

 

Вариант 1.	Вариант 2.
Вариант 3.	Вариант 4.
Вариант 5.	Вариант 6.
Вариант 7.	Вариант 8.
Вариант 9.	Вариант 10.

Раздел II. Тема 3. Решить транспортную задачу.

 

1. 6 5 4 - 500 2. 5 1 2 4 92

8 8 2 6 300 2 5 - 3 45

9 - 7 6 100 - 2 2 5 63

 

400 200 150 250 60 40 36 14

 

3. - 5 4 2 30 4. 5 6 1 4 80

2 5 - 3 50 8 - 6 5 320

3 2 - 5 120 5 4 3 - 100

 

40 30 20 10 250 100 150 50

 

5. 3 - - 6 140 6. 4 7 1 1 100

5 2 3 1 160 5 - 3 4 50

1 1 2 4 150 3 - 2 8 70

 

50 70 130 150 10 80 90 20

 

7. 3 - 2 1 200 8. 4 3 2 - 400

2 3 - 4 70 10 10 4 7 200

5 8 7 3 80 12 - 11 5 100

 

20 40 80 60 300 150 100 200

 

9. 4 1 2 3 100 10. 2 7 4 3 40

3 6 - 4 200 5 - 12 7 30

- 2 3 5 150 8 1 - 13 50

 

40 60 100 50 10 20 40 60

Раздел III. Задача линейного программирования

Тема 5. Формулировка задачи линейного программирования (ЛП).

1. 2.

 

3. 4.

 

5. 6.

 

7. 8.

 

9. 10.

Раздел IV. Тема 6. Симплексный метод решения задачи линейного программирования

11. 12.

13. 14.

 

15. 16.

 

17. 18.

 

19. 20.

 

Раздел IV. Тема 7. Теория двойственности. Двойственная задача к задаче планирования торговли. Решение задачи линейного программирования двойственным симплексным методом

 

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

21. 22.

23. 24.

25. 26.

 

27. 28.

 

29. 30. .

 

Раздел V. Тема 8. Целочисленное программирование

Найти максимум или минимум целевой функции при заданной системе ограничений. Во всех задачах x_j ≥ 0 и x_j -целые ( j =1, 2 или j= )

31.

L(x) = 2x₁– x₂ –3x₃ → min

 

32.

L(x) = x₁+ x₂ → max

 

33.

L(x) = x₁+4 x₂ → max

 

34.

L(x) = 3x₁+4 x₂ → max

 

35.

L(x) = x₁+ x₂ → max

 

36.

L(x) = x₁– 4x₂ + 2x₃ → min

 

37.

L(x) = 2x₁→ max

 

38.

L(x) = 5x₁– 3x₂ → max

 

39.

L(x) = 7x₁– x₂ → max

 

40.

L(x) = 2x₁→ max

 

 

Раздел V. Тема 9. Транспортная задача. Нахождение оптимального плана методом потенциалов

 

 

Решить транспортные задачи:

 

41.

 

42.

 

43.

 

 

44.

 

45.

 

46.

 

 

47.

 

48.

 

49.

Решение типовых задач

ГРАФИЧЕСКИЙ СПОСОБ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

ТИПОВОЙ ПРИМЕР 1

Ζ =-2х₁+х₂→ min

2х₁+х₂≤ 8,

х₁+3х₂≥ 6,

3х₁+х₂≥ 3,

х₁, х₂≥ 0.

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

Областью решений неравенства 2х₁+х₂≤ 8 является полуплоскость, лежащая по одну сторону от прямой 2х₁+х₂=8. Построим эту прямую. Для построения этой прямой достаточно знать ее любые две точки. Для определения координат точки на прямой одна из ее координат полагается равной произвольному числу, а другая находится из уравнения прямой после подстановки туда зафиксированного значения координаты.

Положим х₁=0. Подставив это значение в уравнение прямой

2х₁+х₂=8,

найдем х₂: х₂=8-2•0=8

Следовательно, точка (0; 8) лежит на нашей прямой.

Положим х₂=0.

Подставив это значение в уравнение прямой находим:

х₁=(8-0): 2=4

Точка (4; 0) также лежит на прямой.

Построим в системе координат (х₁; х₂) точки с координатами (0; 8) и (4; 0).

Областью решений неравенства 2х₁+х₂≤ 8 является полуплоскость, лежащая по одну сторону от построенной прямой.

Для определения, какая из двух полуплоскостей является областью решений данного неравенства, достаточно взять любую точку плоскости не лежащую на этой прямой и проверить, удовлетворяет она неравенству или нет. Если взятая точка удовлетворяет неравенству, то полуплоскость, в которой она лежит, является областью решений неравенства, если же не удовлетворяет, то областью решений является другая полуплоскость. Обычно в качестве такой точки берут начало координат (0; 0). Эта точка удовлетворяет неравенству 2х₁+х₂≤ 8, значит областью решений неравенства является полуплоскость, в которой лежит точка (0; 0).

Аналогично можно построить области решений неравенств: х₁+3х₂≥ 6, 3х₁+х₂≥ 3.

Взяв пересечение всех областей решений неравенств, получим пространство решений – четырехугольник АВСД.

В каждой точке, принадлежащей внутренней области или границам четырехугольника решений АВСД, все ограничения выполняются, поэтому решения, соответствующие этим точкам, являются допустимыми. Пространство решений содержит бесконечное число таких точек, но, несмотря на это, можно найти оптимальное решение, если выяснить в каком направлении возрастает (в нашем случае убывает) целевая функция модели Ζ =-2х₁+х₂. На график наносят ряд параллельных линий, соответствующих уравнению целевой функции при нескольких произвольно выбранных и последовательно возрастающих значениях Ζ, что позволяет определить наклон целевой функции и направление, в котором происходит ее увеличение, т.е. возрастание общего дохода (в нашем случае, ее уменьшение). На рис.1 использованы следующие значения целевой функции: Ζ =0 и Ζ =6. Чтобы найти оптимальное решение, следует перемещать прямую, характеризующую доход, в направлении возрастания (в нашем случае, в направлении убывания) целевой функции до тех пор, пока она не сместиться в область недопустимых решений.

 

(1)

8 В

(3) 6

 

(2)

А 3

2 Д

С

0 1 4 6

-3

Ζ =6

Ζ =0

 

 

Рис 1

 

 

На рис.1 видно, что оптимальному решению соответствует точка С. Так как точка С является точкой пересечения прямых (1) и (2), значения х₁и х₂ в этой точке определяются решением следующей системы двух уравнений:

2х₁+х₂=8

х₁=х₂ + 3х₂ = 6

 

Решение указанной системы уравнений дает следующий результат: х₁=3, 6; х₂=0, 8.

Значит точка С (3, 6; 0, 8) является точкой минимума. Значение целевой функции в этой точке равно Ζ =-2х₁+х₂=-2•3, 6+0, 8=-6, 4.

 

ТИПОВОЙ ПРИМЕР 2

Задача.

Решить симплекс-методом следующую задачу линейного программирования:

Z = 0, 16 х₁ + 0, 2 х₂ → max, при ограничениях:

 

х₁ + х₂ ≤ 300

2х₁ + 3х₂ ≤ 780

60х₁ + 30х₂ ≤ 14400

х₁, х₂ ≥ 0

 

Вначале перейдем от системы неравенств к системе уравнений, для этого введем переменные х₃, х₄, х₅ такие, что:

 

х₁+ х₂ + х₃ = 300, х₃ > 0

2х₁ + 3х₂ + х₄ = 780, х₄> 0

60х₁ + 30х₂ + х₅ = 14400, х₅> 0

 

Переменные, имеющие нулевое значение называются небазисными переменными, остальные – базисными переменными.

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

Исключаемая переменная – это та базисная переменная, которая на следующей итерации полежит исключению из множества базисных переменных.

Столбец симплекс-таблицы ассоциированный с включаемой (вводимой) переменной называют ведущим столбцом.

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

Элемент таблицы находящийся на пересечении ведущего столбца и строки называют ведущим элементом.

Если все коэффициенты при небазисных переменных в Z – уравнении неотрицательны (неположительные, при задаче на минимум), полученное решение оптимально.

Если все коэффициенты при базисных переменных неотрицательны, то решение называется допустимым.

Предположим, что х₁= 0, х₂ = 0, т.е.х₁ и х₂ – небазисные переменные, тогда при таких условиях х₃ = 300, х₄ = 780, х₅ = 14400. Переменные х₃, х₄, х₅ – отличны от нуля, составляют базис.

Составим симплекс-таблицу.

В строки Х₃, Х₄, Х₅ выписываем коэффициенты при соответствующих переменных х₁.х₂, х₃.х₄, х₅ из уравнений ограничений. В столбец Решение выписываем правые части из ограничений. Строка Z формируется из коэффициентов в целевой функции (с противоположными знаками).

Таблица 1

 

Переменные Базис	х1	х2	х3	х4	х5	Решение	Ѳ
Х3
Х4		3	0				260←
Х5		30
Z	-0, 16	-0, 2 ↑

 

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

 

Переход к новой таблице осуществляется следующим способом.

Условие оптимальности. В строке Z находим наибольшее по модулю отрицательное (при задачи на минимум – наибольшее положительное) число. В нашем примере этим числом будет -0, 2, расположенное во втором столбце (ведущий столбец) при переменной х₂, которая будет являться вводимой в базис переменной. Если в таблице имеется два одинаковых коэффициента, то выбирается любой.

Условие допустимости. Делим столбец Решение на положительные элементы ведущего столбца и выбираем из полученных отношений наименьшее. Наименьшее отношение определяет ведущую строку. В данном случае имеем:

 

300 780 14400 780

Min=; ; = = 260

1 3 30 3

Таким образом, ведущей строкой будет строка Х₄(переменная х₄- исключаемая). Коэффициент 3 – ведущий. В случаи равенства нескольких отношений выбор делается произвольно.

Составляем вторую симплекс - таблицу.

Вместо х₄ вводим в базис переменную х₂. Переход к новому базису эквивалентен преобразованию матрицы, элементами которой служат числа таблицы 1. А именно: в новой таблице элементы ведущей строки равны элементам прежней таблице разделенным на ведущий элемент, те. Новая ведущая строка =

Предыдущая ведущая строка (2⁄ 3; 3⁄ 3 и т.д.)

Ведущий элемент

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

Для примера найдем элемент на пересечении строки Х₅ и столбца Х₁:

3 ∙ 60 – 2 ∙ 30 =40

Таким образом, мы переходим ко второй таблице.

 

Таблица 2

Переменные Базис	х1	х2	х3	х4	х5	Решение	Ѳ
х3	1/3	0		-1⁄ 3			120←
х2	2⁄ 3			1⁄ 3
х5
Z	-2⁄ 75 ↑			1⁄ 15

 

Т.к. строка Z имеет отрицательное число (-2⁄ 75), то оптимальное решение не достигнуто и надо строить следующую таблицу.

Столбец Х₁ – ведущий. Определяем ведущую строку:

40 260 6600 40

Min = 1⁄ 3; 2⁄ 3; 40 = 1⁄ 3 = 120.

т.е. Х₃- ведущая. Следовательно, 1⁄ 3 – ведущий элемент.

Вместо х₃ вводим в базис переменную х₁ и составляем симплекс- таблицу.

 

Таблица 3

Переменные Базис	Х1	Х2	Х3	Х4	Х5	Решение
Х1				-1
Х2			-2
Х5			-120
Z			2⁄ 25	1⁄ 25		55, 2

 

В строке Z нет отрицательных элементов. Следовательно, мы получили оптимальное решение:

х₁ =120, х₂ = 180, х₃ = 0, х₄ = 0, х₅ =1800

Z=0, 16 ∙ 120 + 0, 2 ∙ 180 = 55, 2

⇐ Предыдущая1234567Следующая ⇒

Поделиться:

Популярное:

1. I. ПОЧЕМУ СИСТЕМА МАКАРЕНКО НЕ РЕАЛИЗУЕТСЯ
2. I. Теоретические основы использования палочек Кюизенера как средство математического развития дошкольников.
3. II. Решить следующие ниже финансовые задачи на листе “Задачи”.
4. II. Система обязательств позднейшего права
5. II. Соотношение — вначале самопроизвольное, затем систематическое — между положительным мышлением и всеобщим здравым смыслом
6. II.2.6. Методы математической статистики
7. IV. Решить следующую задачу.
8. IV. Тематика и перечень курсовых работ и рефератов.
9. MS Word. Работа с математическими формулами
10. VI. ОБСЛЕДОВАНИЕ БОЛЬНОГО ПО ОРГАНАМ И СИСТЕМАМ
11. VII. Перечень вопросов для проведения проверки знаний кандидатов на получение свидетельства линейного пилота с внесением квалификационной отметки о виде воздушного судна - вертолет
12. VIII. Общение и система взаимоотношений