Задача 1

Темы: «Линейное программирование»

«Двойственность в линейном программировании»

1-30. На предприятии имеется возможность выпускать n видов продукции Пj (j=1,n). При ее изготовлении используются ресурсы Р1, Р2 и Р3 соответственно. Размеры допустимых затрат ресурсов ограничены соответственно величинами b1, b2 и b3. Раcход ресурса i-го (i=1,3) вида  на единицу продукции j-го вида составляет aij единиц. Цена единицы продукции j-го вида равна сj ден. ед. Требуется:

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

2) сформулировать в экономических терминах двойственную задачу и составить ее математическую модель;

3) используя решение исходной задачи и соответствие между двойственными переменными, найти компоненты оптимального плана двойственной задачи – двойственной оценки yi* (i=1,2,3);       

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

5) с помощью двойственных оценок yi* обосновать рациональность оптимального плана, сопоставив оценку затрат φmin израсходованных ресурсов и максимальный доход fmax от реализации готовой продукции по всему оптимальному плану и по каждому виду в отдельности;

6) определить величину ∆bs  ресурса Ps , введением которого в производство можно компенсировать убыток и сохранить максимальный доход на прежнем уровне (ресурсы предполагаются взаимно заменяемыми), получаемый при исключении из производства  ∆br единиц ресурса Pr , что вызывает уменьшение максимального дохода на ∆r fmax ед. ;

7) оценить целесообразность приобретения ∆bk единиц ресурса Pk по цене сk за единицу;

8) установить, целесообразно ли выпускать новую продукцию Пl , на единицу которой ресурсы P1 , P2 и P3 расходуются в количествах a1l , a2l и a3l единиц, а цена единицы готовой продукции составляет pl ед.

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

Таблица 1.1

Задача 2

Тема: «Транспортная задача»

1- 10. В пунктах Ai (i=1,3) производится однородная продукция в количествах ai единиц. Себестоимость единицы продукции в i-ом пункте равна сi .  Готовая продукция поставляется в пункты Bj (j=1,4) потребности которых составляют bj единиц. Стоимость cij перевозки единицы продукции из пункта Ai в пункт Bj заданы матрицей [cij]3x4 .

Требуется:

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

2) вычислить суммарные затраты fmin ;

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

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

Таблица 2.1

11 – 20. На заводах № 1, 2 и 3 производится однородная продукция в количестве a1, a2 и a3   единиц. При этом затраты на производство единицы продукции на заводах составляют c1, c2 и c3 ден. ед. Четырем потребителям требуется соответственно b1, b2, b3 и b4 единиц продукции. Расходы cij по перевозке единицы продукции с i-го завода j-му потребителю известны. Для полного удовлетворения потребностей необходимо увеличить выпуск продукции. При этом возможны следующие варианты:

1) расширить мощность завода №1 с дополнительными затратами на единицу продукции, равными ∆c1 ;

2) расширить мощность завода №2 с дополнительными затратами на единицу продукции, равными ∆c2 ;

3) наладить выпуск продукции на заводе №4 с затратами на производство единицы продукции, равными с4 , и расходами по перевозке единицы продукции, равными соответственно с41, с42, с43 и с44 .

Требуется:

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

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

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

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

Таблица 3.1

21 – 30. Студенческие отряды СО-1,СО-2 и СО-3 численностью в a1, a2 и a3 человек принимают участие в сельскохозяйственных работах. Для уборки картофеля на полях П1, П2, П3 и П4 необходимо выделить соответственно b1, b2, b3 и b4  человек. Производительность труда студентов зависит от урожайности картофеля, а также от состава отряда и характеризуется для указанных отрядов и полей элементами матрицы [pij]3x4 (в центнерах на человека за рабочий день).

Требуется:

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

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

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

Таблица 4.1

Задача 3

Тема: «Программирование на сетях»

61-90. На заданной сети указаны пропускные способности ребер. Предполагается, что пропускные способности в обоих направлениях одинаковы.

Требуется:

сформировать на сети поток максимальной мощности, направленный из истока I в сток S; выписать ребра, образующие на сети разрез минимальной пропускной способности.

Задание № 4

91 – 120. Рассчитать непосредственно на сетевом графике комплекса работ ранние и поздние сроки свершения событий, резервы времени событий, минимальное время выполнения комплекса (критический срок). Выделить на сетевом графике критический путь. Для некритических работ найти полные и свободные резервы времени.