Назначение механизмов на работы

Задача о ранце

В грузовую автомашину надо поместить четыре вида предметов, причем могут потребоваться несколько одинаковых предметов. Имеется три вида ограничений такого типа, как вес, объем и т.д. В приведенной ниже таблице даны a_ij- i-я характеристика предмета j-го наименования, c_j- полезность одного предмета j-го наименования (i=, j=). Требуется загрузить машину так, чтобы суммарная полезность груза была максимальной.

Ограничения	Предмет1	Предмет2	Предмет3	Предмет4	Значения ограничений
I
II
III
Полезность

Математическая модель задачи выглядит следующим образом.

Целевая функция имеет вид:

3× x₁+4× x₂+3× x₃+3× x_4® max,

Ограничения имеют вид:

3× x₁+3× x₂+5× x₃+2× x_4£ 1000,

4× x₁+2× x₂+4× x₃+4× x_4£ 600,

3× x₁+5× x₂+4× x₃+3× x_4£ 600,

x_j³ 0, целые, j=.

Вид электронной таблицы Excel, созданной для решения задачи, представлен на рис. 34. Значения переменных x_ij располагаются в блоке ячеек B3:E3 (см. рис. 34). Коэффициенты целевой функции, отражающие полезности предметов находятся по адресам B6:E6. Данные о характеристиках предметов имеются в блоке B9:E11. Заданы значения ограничений- соответственно блок H9:H11.

Рис. 34

Формулы целевой функции и ограничений находятся соответственно в ячейке F6 и ячейках F9:E11 (ограничения по свойствам) (см. рис. 34 и 35). Вид электронной таблицы в режиме отображения формул представлен на рис. 35.

Запись условий задачи в окне "Поиск решения" можно увидеть на рис. 36.

Результаты поиска решения приведены на рис. 34.

Рис. 35

Рис. 36

Имеются три механизма М₁, М₂, М₃, каждый из которых может быть использован на трех видах работ Р₁, Р₂, Р₃ с производительностью (в условных единицах), заданной в виде таблицы:

Механизмы	Работы
	Р1	Р2	Р3
М1
М2
М3

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

Математическая модель задачи выглядит следующим образом.

Целевая функция имеет вид:

x₁₁+2× x₁₂+3× x₁₃+2× x₂₁+4× x₂₂+x₂₃+3× x₃₁+x₃₂+5× x_33® max,

Ограничения имеют вид:

x₁₁+x₁₂+x₁₃=1,

x₂₁+x₂₂+x₂₃=1,

x₃₁+x₃₂+x₃₃=1,

x₁₁+x₂₁+x₃₁=1,

x₁₂+x₂₂+x₃₂=1,

x₁₃+x₂₃+x₃₃=1.

Вид электронной таблицы Excel, созданной для решения задачи, представлен на рис. 37. Значения переменных x_ij располагаются в блоке ячеек B4:D6 (см. рис. 37). Коэффициенты целевой функции, отражающие производительность механизмов, находятся по адресам B11:D13.

Рис. 37

Формулы целевой функции и ограничений находятся соответственно в ячейке E8 и ячейках E4:E6 (каждый механизм может быть назначен только на одну работу), B8:D8 (каждая работа выполняется только на одном механизме) (см. рис. 37 и 38). Вид электронной таблицы в режиме отображения формул представлен на рис. 38.

Рис. 38

Рис. 39

Данная задача является задачей линейного булева программирования и в ней переменные x_ij должны принимать значения либо 0 либо 1. В поиске решения такое ограничение задается тремя ограничениями, по которым изменяемые ячейки в блоке (x_ij) одновременно больше либо равны 0, меньше либо равны 1 и являются целыми. Первые три записи в группе Ограничения (см. рис. 39) отражают этот факт.

Результаты поиска решения приведены на рис. 37.

Дата добавления: 2014-01-11