Дискретная математика(задача про память).

[Jesse]

Помогите разобраться, как можно формализовать данную задачу.

В оперативной памяти ЭВМ должна одновременно храниться информация по N программам для организации мультипрограммной работы. Размер выделяемой зоны для каждой из программ может быть выбран любым из имеющихся К вариантов.
Пусть N = К = 4. Соответствие программ и вариантов выделяемых зон задается матрицей А. Столбцы матрицы А соответствуют программам, строки – вариантам выбора зон. При каждом варианте распределения возможно недоиспользование зоны памяти. Каждый вариант характеризуется средним размером недоиспользования памяти, который зависит как от объема программы, так и от варианта и задан таблицей В.
Найти такой вариант статического размещения программ в оперативной памяти ЭВМ, чтобы общий объем недоиспользования памяти был минимальным при условии, что не будет превышен общий объем памяти S .

Исходные данные в таблице
1 2 3 4
1 30 20 10 40
2 35 25 12 45
3 42 28 15 47
4 45 35 17 50
S =115

Добавлено спустя 2 минуты 40 секунд:

Не знаю почему, но вверху там чуть сбилось

1 2 3 и 4 должны стоять над соответственно 30 20 10 40

Добавлено спустя 6 минут 2 секунды:

http://www.sendspace.com/file/2fhnnw - это линк на текстовый вариант задачи. Она идет там под номером 9(таблица 5.30). Это если вдруг не понял то, что я написал выше. Как я понимаю, это задача на минимизацию. Но проблема тут в формализации. И что делать с матрицей A(и как ее выписать правильно ?)

Добавлено спустя 42 минуты 24 секунды:

ой какой я тупой Таблица это по сути и есть матрица А (исходные данные), а начинка таблица(30, 20 и т.д.) - это то, что они назвали В.


Теперь проблема в том, чтобы это минимизировать. Есть ли какой короткий путь ? (я чувствую, что задача оч примитивная, но плз помогите). Получаю сейчас второе высшее по менеджменту, а тут дискретку требуют. После работы голова уже не варит совсем (

[maxal]

Сначала формализуйте задачу, то есть сформулируйте ее чисто в математических терминах - типа: даны матрицы $A,B$ такого-то размера, нужно найти такой вектор $x$, что ...

[Архипов]

Как я понял, задача из дискретной математики. А в дискретной математике оперируют не формулами, а алгоритмами, но значения величин, в первом приближении, рассматривают как непрерывные функции.
Предлагаю такой алгоритм:
1. Упорядочить числа в строках в порядке убывания.
2. Посчитать суммы чисел в столбиках (182 152 108 54).
3. Вычитая из этих сумм число 115, найдем оптимальный столбик (третий (108))
Теперь нужно заменить некоторые числа в третьем столбике, числами из ближайших столбиков (из 2 и 4), чтобы приблизить сумму третьего столбика к числу 115.
Получим ответ: (20 +35 +15 +45 = 115).
Но ответ мы получили интуитивно, просмотрев глазами соседние столбики. А нужно получить рациональным способом, как это делала бы компьютерная программа оптимизации.
4. Образуем временно вторую табличку из трех столбиков, вставив в первый положительные разности между числами 2 и 3 столбиков в порядке возрастания (сверху вниз). Во втором столбике - отрицательные разности между числами 3 и 4 столбика в порядке возрастания ( по абсолютному значению они будут убывать).
5. Просуммируем числа в наших двух столбиках - получится третий столбик разностей в порядке убывания.
6. Нам нужно прибавить к числу 108 разность не больше 7, чтобы получить ближайшее к 115 число. Мы легко его найдем такую разность в нашем третьем столбике.
Еще нужно перебрать несколько вариантов соседних строк нашего третьего столбика, чтобы в третьем приближении найти ближайшую к 7 разность. Это будет шагом номер 7 в алгоритме. Да еще нужно восстановить номера строк и столбцов откуда берутся числа для замены.

[TOTAL]

Архипов писал(а):

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

Зачем Вы это сказали?

[Архипов]

TOTAL писал(а):

Зачем Вы это сказали?

А затем, чтобы Вы это спросили: "Зачем Вы это сказали?". Я бы вот так ответил.

[нг]

Архипов, не занимайтесь флудом.

Ваше высказывание о том, что такое дискретная математика, как минимум, не имеет отношения к теме, а уж по существу — неверно.