Методы оптимальных решений, вариант 12

Вариант 12
1) Составить экономико-математическую модель задачи и решить её графически и симплекс-методом.
Завод изготавливает 2 вида изделий на экспорт с помощью машин и . Максимальное время работы машин - 8 ч., а машин - 12 ч. В сутки. Расход времени машин в сутки представлен в таблице. Валютная прибыль 1 изделия составляет 3 долл., а 2 – 4 долл. Рассчитать производственный план на сутки при максимальной валютной прибыли.
Изделие Машины
1 1 2,5
2 4 2
8 12

2) В трёх пунктах отправления А1, А2, А3 сосредоточен груз в количествах а1, а2, а3. Этот груз следует доставить в каждый из четырёх пунктов назначения В1, В2, В3 в количестве b1, b2, b3. Стоимость перевозок единицы груза из i-го пункта отправления в j-й пункт назначения равна сij. Определить такой план перевозок методом минимал ...

Вариант 12
1) Составить экономико-математическую модель задачи и решить её графически и симплекс-методом.
Завод изготавливает 2 вида изделий на экспорт с помощью машин и . Максимальное время работы машин - 8 ч., а машин - 12 ч. В сутки. Расход времени машин в сутки представлен в таблице. Валютная прибыль 1 изделия составляет 3 долл., а 2 – 4 долл. Рассчитать производственный план на сутки при максимальной валютной прибыли.
Изделие Машины
1 1 2,5
2 4 2
8 12

2) В трёх пунктах отправления А1, А2, А3 сосредоточен груз в количествах а1, а2, а3. Этот груз следует доставить в каждый из четырёх пунктов назначения В1, В2, В3 в количестве b1, b2, b3. Стоимость перевозок единицы груза из i-го пункта отправления в j-й пункт назначения равна сij. Определить такой план перевозок методом минимального элемента, чтобы стоимость перевозок была наименьшей. Улучшить оптимальный план методом потенциалов.
Поставщик Потребитель Запасы груза
В1 В2 В3
А1 2 5 3 60
А2 9 4 7 40
А3 6 5 8 75
Потребность 80 40 5

Вариант 12
1) Составить экономико-математическую модель задачи и решить её графически и симплекс-методом.
Завод изготавливает 2 вида изделий на экспорт с помощью машин и . Максимальное время работы машин - 8 ч., а машин - 12 ч. В сутки. Расход времени машин в сутки представлен в таблице. Валютная прибыль 1 изделия составляет 3 долл., а 2 – 4 долл. Рассчитать производственный план на сутки при максимальной валютной прибыли.
Изделие Машины
1 1 2,5
2 4 2
8 12

2) В трёх пунктах отправления А1, А2, А3 сосредоточен груз в количествах а1, а2, а3. Этот груз следует доставить в каждый из четырёх пунктов назначения В1, В2, В3 в количестве b1, b2, b3. Стоимость перевозок единицы груза из i-го пункта отправления в j-й пункт назначения равна сij. Определить такой план перевозок методом минимал ьного элемента, чтобы стоимость перевозок была наименьшей. Улучшить оптимальный план методом потенциалов.
Поставщик Потребитель Запасы груза
В1 В2 В3
А1 2 5 3 60
А2 9 4 7 40
А3 6 5 8 75
Потребность 80 40 5

16
0,5
1
Условия оптимальности выполняются – все .
Оптимальным решением является вектор при этом .
В условиях исходной задачи, для получения максимальной прибыли в 16 долл. необходимо производить 4 единицы изделий 1 вида и 1 единицу изделия 2 вида.
Ответ: необходимо производить 4 единицы изделий 1 вида и 1 единицу изделия 2 вида для получения максимальной прибыли 16 долл.
В трёх пунктах отправления А1, А2, А3 сосредоточен груз в количествах а1, а2, а3. Этот груз следует доставить в каждый из четырёх пунктов назначения В1, В2, В3 в количестве b1, b2, b3. Стоимость перевозок единицы груза из i-го пункта отправления в j-й пункт назначения равна сij. Определить такой план перевозок методом минимального элемента, чтобы стоимость перевозок была наименьшей. Улучшить оптимальный план методом потенциалов.
Поставщик
Потребитель
Запасы груза
В1
В2
В3
А1
2
5
3
60
А2
9
4
7
40
А3
6
5
8
75
Потребность
80
40
55
Решение:
Имеем закрытую транспортную задачу: суммарный запас груза 60 + 40 + 75 = 175 равен суммарной потребности 80 + 40 + 55 = 175.
Построим начальный план методом минимального элемента.
Минимальная стоимость перевозки 2. Разместим в клетку А1В1 наибольшее количество груза - 60 единиц (строка А1 выходит из рассмотрения). Следующая минимальная стоимость 4 – в клетку А2В2 разместим наибольшее количество груза – 40 единиц (строка А2 и столбец В2 выходят из рассмотрения). Следующая минимальная стоимость 6 – в клетку А3В1 разместим наибольшее количество груза – 20 (столбец В1 выходит из рассмотрения).
В оставшейся клетке А3В3 размещаем 55 единиц груза.
Получаем следующий план перевозок:
 
80
40
55
60
 
2
 
5
 
3
60
 
 
40
 
9
 
4
 
7
 
40
 
75
 
6
 
5
 
8
20
 
55
Стоимость перевозки при данном плане равна:
60*2 + 40*4 + 20*6 + 55*8 = 840
Проверим полученный план на оптимальность и при необходимости, улучшим его методом потенциалов. Расчеты будем производить в таблице.
потенциал
стоимость перевозки
количество груза
Число занятых клеток 4, число уравнений связи в задаче 3 + 3 – 1 = 5, следовательно, опорный план является вырожденным. Для получения невырожденного плана перевозок разместим в клетку А3В2 нулевую перевозку.
Найдем потенциалы uі и vі по занятым клеткам таблицы, решая систему уравнений, полагая, что uі + vі = сij и u1 = 0.
Занесем рассчитанные потенциалы в таблицу и подсчитаем оценки свободных клеток :
 
80
40
55
ui
60
2
-4
5
1
3
60
40
-4
9
4
7
3
40
75
6
5
8
4
20
55
vi
2
1
4
840
Условием оптимальности плана перевозок является .
Первый опорный план не является оптимальным, так как существуют , поэтому переходим к его улучшению. Выберем положительную оценку свободной клетки . Для клетки А1В3 построим цикл перераспределения груза:
Перераспределение произведем на min(55, 60) = 55 единиц груза.
Получим следующий план перевозок:
 
80
40
55
60
 
2