ЗАДАНИЕ 1 Тема «Линейное программирование»

Задача 1.1

На предприятии имеется возможность выпускать n видов продукции П_i (i = 1, n). При ее изготовлении используются ресурсы Р₁, Р₂ и Р₃. Размеры прямых затрат ресурсов ограничены соответственно величинами b₁, b₂ и b₃. Расход j-го ресурса (i = 1, 3) на единицу продукции i-го вида составляет a_ij ед. Цена единицы продукции i-го вида равна с_j ден. ед. Требуется:

1. Сформулировать в экономических терминах прямую задачу и составить математическую модель прямой и двойственной задач. Раскрыть экономический смысл всех переменных, участвующих в решении задачи.

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

3. используя решение исходной задачи и соответствие между прямыми и  двойственными переменными, найти параметры оптимального плана двойственной задачи;

4. указать наиболее дефицитный и недефицитный (избыточный) ресурс, если он имеется;

5. с помощью двойственных оценок у_i* обосновать эффективность оптимального плана, сопоставив оценку израсходованных ресурсов j_min и максимальный доход Z_max от реализации готовой продукции по всему оптимальному плану и по каждому виду продукции отдельно;

6. установить, целесообразно ли выпускать новую продукцию П_l, на единицу которой ресурсы Р₁, Р₂ и Р₃ расходуются в количестве а_1l, а_2l и а_3l, а цена единицы готовой продукции составляет р_l.

7. установить, выгодно ли покупать Dbk единиц k ресурса по цене ck.

Необходимые числовые данные приведены в табл. 1.1.

Задача 1.2

Составить диету, включающую белки, жиры и углеводы в количестве не менее b_i (i = 1, 3). Для составления смеси можно использовать три вида продуктов М_j (j = 1, 3), содержащих белки, жиры и углеводы в количестве a_ij. Цена продуктов c_j. Необходимо определить такой набор продуктов, который обеспечил бы необходимое содержание питательных веществ, и полная стоимость его при этом была бы наименьшей. Требуется:

1. составить математическую модель прямой и двойственной задачи;

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

Необходимые числовые данные приведены в табл. 1.2.

ЗАДАНИЕ 2 Тема «Транспортная задача»

Задача 2.1

В пунктах D_i (i = 1, 3) производится однородная продукция в количестве а_i ед. Себестоимость единицы продукции в i-м пункте равна s_i. Готовая продукция поставляется в пункты В_j, (j = 1, 4), потребности которых составляют b_j ед. Стоимость перевозки единицы продукции из пункта D_i в пункт В_j, задана матрицей c_ij (i = 1, 3; j = 1,4). Требуется:

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

2. построить план перевозки продукции, при котором минимизируются суммарные затраты по ее изготовлению и доставке потребителям;

3. вычислить суммарные затраты Z_min;

4. указать в какие пункты развозится продукция от поставщиков.

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

Необходимые числовые данные приведены в табл. 2.1.

Задача 2.2

На заводах № 1, 2 и 3 производится однородная продукция в количестве а₁ а₂ и а₃. При этом затраты на производство единицы продукции на заводах составляют s₁ s₂ и s₃  ден. ед. Четырем потребителям требуется соответственно b₁, b₂, b₃ и b₄ единиц продукции. Расходы с_ij по перевозке единицы продукции с i-го завода j-му потребителю известны. Для полного удовлетворения потребностей потребителей необходимо увеличить выпуск продукции. При этом возможны следующие варианты:

1) увеличить производство продукции на заводе № 1 с дополнительными затратами на единицу продукции, равными Dc₁;

2) увеличить производство продукции на заводе № 2 с дополнительными затратами на единицу продукции, равными Dc₂,

3) наладить выпуск продукции на заводе № 4 с затратами на производство единицы продукции, равными c₄, и расходами по перевозке единицы продукции, равными соответственно c₄₁, c₄₂ , c₄₃ и c₄₄. Требуется:

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

2. определить минимальные совокупные затраты на производство продукции и доставку ее потребителям по оптимальному плану расширения выпуска продукции.

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

Необходимые числовые данные приведены в табл. 2.2.

Задача 2.3

Студенческие отряды СО-1, СО-2 и СО-3 численностью а₁, а₂, и а₃ человек принимают участие в сельскохозяйственных работах. Для уборки картофеля на полях П₁, П₂, П₃ и П₄ необходимо выделить соответственно b₁, b₂, b₃ и b₄ человек. Производительность труда студентов зависит от урожайности картофеля, а также от численности отряда и характеризуется для указанных отрядов и полей элементами матрицы p_ij (в центнерах на человека за рабочий день). Требуется:

1) распределить студентов по полям так, чтобы за рабочий день было убрано максимально возможное количество картофеля;

2) определить, сколько центнеров картофеля будет убрано с четырех полей при оптимальном распределении студентов.

Необходимые числовые данные приведены в табл. 2.3.

ЗАДАНИЕ 3 Тема "Элементы теории игр"

Задача 3.1

Предприятие имеет возможность самостоятельно планировать объемы выпуска сезонной продукции А₁, А₂, А₃. Не проданная в течение сезона продукция позже реализуется по сниженной цене. Данные о себестоимости продукции, отпускных ценах и объемах реализации в зависимости от уровня спроса приведены в таблице:

Требуется:

1) придать описанной ситуации игровую схему, указать допустимые стратегии сторон, составить платежную матрицу.

2) дать рекомендации об объемах выпуска продукции по видам, обеспечивающих предприятию наивысшую прибыль.

(a)  При условии, что вероятности известны.

(b) При условии, что вероятности того или иного спроса одинаковы.

(c)  При условии, что про вероятности неопределенны.

Указание1. Для уменьшения размерности платежной матрицы считать, что одновременно на все три вида продукции уровень спроса одинаков: повышенный, средний или пониженный.

Указание2. Использовать критерии Байеса( вероятности равны 0,25, 0,4, 0,35 соответственно), Лапласа, Вальда, Сэвиджа, Гурвица (значение параметра g в критерии Гурвица равно 0,6).

Числовые данные приведены в табл. 3.1.

ЗАДАНИЕ 4 Тема "Динамическое программирование"

Задача 4.1

Выделены денежные средства S₀=100 для вложения в инвестиционные проекты. По каждому проекту известен возможный прирост f_i(x) (i = 1, 4) выпуска продукции в зависимости от выделенной суммы. Требуется:

1) распределить средства S₀ между проектами так, чтобы суммарный прирост прибыли на всех четырех проектах достиг максимальной величины;

Необходимые числовые данные приведены в табл. 4.1.

Задача 4.2

Выделены денежные средства S₀. для вложения в инвестиционные проекты на 2 года. По каждому проекту известны прирост денежных средств f_i(x) (i = 1, 2) и отдача денежных средств g_i(x). Требуется

1) распределить средства S₀ между проектами так, чтобы суммарная прибыль достигла  максимальной величины;

Необходимые числовые данные приведены в табл. 4.2.

ЗАДАНИЕ 5 Тема Управление производством"

Задача 5.1

В начале планового периода продолжительностью 6 лет имеется оборудование, возраст которого t. Оборудование не должно быть старше 6 лет. Известны: стоимость r(t) продукции, произведенной в течение года с помощью этого оборудования; ежегодные расходы u(t), связанные с эксплуатацией оборудования; его остаточная стоимость s; стоимость p нового оборудования, включающая расходы, связанные с установкой, наладкой и запуском оборудования. Требуется:

1) составить матрицу максимальных прибылей за 6 лет;

2) сформировать по матрице максимальных прибылей оптимальные стратегии замены оборудования возрастов t и t₁ лет в плановом периоде продолжительностью 6 и N лет.

Необходимые данные приведены в табл. 5.3.

ЗАДАНИЕ 7 Тема «целочисленное программирование»

Задача 7.1

Имеется необходимость посетить n городов в ходе деловой поездки. Спланировать поездку нужно так, чтобы, переезжая из города в город, побывать в каждом не более одного раза и вернуться в исходный город. Задана матрица расстояний между городами c_ij.

Сформулированная задача - задача ЦП. Пусть х_ij = 1 , если путешественник переезжает из i -ого города в j-ый и х_ij = 0, если это не так.

Формально введем (n+1) город, расположенный там же, где и первый город, т.е. расстояния от (n+1) города до любого другого, отличного от первого, равны расстояниям от первого города. При этом, если из первого города можно лишь выйти, то в (n+1) город можно лишь придти.

Введем дополнительные целые переменные, равные номеру посещения этого города на пути. u₁ = 0, u_n+1 = n . Для того, чтобы избежать замкнутых путель, выйти из первого города и вернуться в (n+1) введем дополнительные ограничения, связывающие переменные x_ij и переменные u_i. ( u_i целые неотрицательные числа).

2. Математическая модель

Необходимые данные приведены ниже.

Задача 7.2

Решить задачу методом ветвей и границ.

Данные, необходимы для решения, приведены в приложении 7.2. 

Условия задачи 7.1

Вариант 1

Вариант 2

Вариант 3

Вариант 4

Вариант 5

Вариант 6

Вариант 7

Вариант 8

Вариант 9

Вариант 10

Вариант 11

Вариант 12

Вариант 13

Вариант 14

Вариант 15

Вариант 16

Вариант 17

Вариант 18

Вариант 19

Вариант 20

Вариант 21

Вариант 22

Вариант 23

Вариант 24

Вариант 25

Вариант 26

Вариант 27

Вариант 28

Вариант 29

Вариант 30

Данные для решения задачи 7.2

Вариант 1

Решить методом ветвей и границ 4*x+3*y≤15,   2*x+5*y≤17 при условии, что Z = 6*x+ 7*y→max.

Вариант 2

Решить методом ветвей и границ 4*x+5*y≤24,  5*x+4*y≤27 при условии, что Z = 2*x+ 3*y→max.

Вариант 3

Решить методом ветвей и границ 3*x+2*y≤16,  2*x+3*y≤18 при условии, что Z = 4*x+ 3*y→max.

Вариант 4

Решить методом ветвей и границ 2*x+3*y≤10,   4*x+3*y≤13 при условии, что Z = 3*x+ 5*y→max.

Вариант 5

Решить методом ветвей и границ 3*x+5*y≤15,    6*x+3*y≤19 при условии, что Z = 6*x+ 7*y→max.

Вариант 6

Решить методом ветвей и границ 2*x+7*y≤20,    5*x+4*y≤15 при условии, что Z = 2*x+ 3*y→max.

Вариант 7

Решить методом ветвей и границ 3*x+2*y≤16,   2*x+3*y≤18  при условии, что Z = 4*x+ 3*y→max.

Вариант 8

Решить методом ветвей и границ 5*x+2*y≤14, 2*x+5*y≤16  при условии, что Z = 3*x+ 5*y→max.

Вариант 9

Решить методом ветвей и границ 9*x+4*y≤31, 8*x+6*y≤39 при условии, что Z = 5*x+4*y→max.

Вариант 10

Решить методом ветвей и границ 8*x+5*y≤24, 7*x+3*y≤18 при условии, что Z = 2*x+ 3*y→max.

Вариант 11

Решить методом ветвей и границ 4*x+7*y≤16, 9*x+4*y≤21 при условии, что Z = 4*x+ 2*y→max.

Вариант 12

Решить методом ветвей и границ 8*x+3*y≤10, 3*x+8*y≤12 при условии, что Z = 3*x+ 5*y→max.

Вариант 13

Решить методом ветвей и границ 4*x+5*y≤19, 6*x+2*y≤25 при условии, что Z = 4*x+ 3*y→max.

Вариант 14

Решить методом ветвей и границ 5*x+6*y≤24, 7*x+5*y≤30 при условии, что Z = 2*x+ 3*y→max.

Вариант 15

Решить методом ветвей и границ 2*x+5*y≤20, 2*x+7*y≤23  при условии, что Z = 4*x+ 3*y→max.

Вариант 16

Решить методом ветвей и границ 1*x+3*y≤20, 4*x+5*y≤37  при условии, что Z = 3*x+ 5*y→max.

Вариант 17

Решить методом ветвей и границ 5*x+2*y≤14, 2*x+5*y≤16  при условии, что Z = 3*x+ 5*y→max.

Вариант 18

Решить методом ветвей и границ 9*x+4*y≤31, 8*x+6*y≤39 при условии, что Z = 5*x+4*y→max.

Вариант 19

Решить методом ветвей и границ 8*x+5*y≤24, 7*x+3*y≤18 при условии, что Z = 2*x+ 3*y→max.

Вариант 20

Решить методом ветвей и границ 4*x+7*y≤16, 9*x+4*y≤21 при условии, что Z = 4*x+ 2*y→max.

Вариант 21

Решить методом ветвей и границ 8*x+3*y≤10, 3*x+8*y≤12 при условии, что Z = 3*x+ 5*y→max.

Вариант 22

Решить методом ветвей и границ 4*x+5*y≤19, 6*x+2*y≤25 при условии, что Z = 4*x+ 3*y→max.

Вариант 23

Решить методом ветвей и границ 5*x+6*y≤24, 7*x+5*y≤30 при условии, что Z = 2*x+ 3*y→max.

Вариант 24

Решить методом ветвей и границ 2*x+5*y≤20, 2*x+7*y≤23  при условии, что Z = 4*x+ 3*y→max.

Вариант 25

Решить методом ветвей и границ 1*x+3*y≤20, 4*x+5*y≤37  при условии, что Z = 3*x+ 5*y→max.

Вариант 26

Решить методом ветвей и границ 2*x+3*y≤10,   4*x+3*y≤13 при условии, что Z = 3*x+ 5*y→max.

Вариант 27

Решить методом ветвей и границ 3*x+5*y≤15,    6*x+3*y≤19 при условии, что Z = 6*x+ 7*y→max.

Вариант 28

Решить методом ветвей и границ 2*x+7*y≤20,    5*x+4*y≤15 при условии, что Z = 2*x+ 3*y→max.

Вариант 29

Решить методом ветвей и границ 4*x+7*y≤16, 9*x+4*y≤21 при условии, что Z = 4*x+ 2*y→max.

Вариант 30

Решить методом ветвей и границ 8*x+3*y≤10, 3*x+8*y≤12 при условии, что Z = 3*x+ 5*y→max

РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА

1.     Бонди Б. Основы линейного программирования. - М.: Радио и связь, 1989. - 174 с.