Відмінності між версіями «Задача про рюкзак.»
(→Задача про рюкзак.) |
(→Література) |
||
| (не показано 8 проміжних версій цього учасника) | |||
| Рядок 8: | Рядок 8: | ||
<center> <math> \sum_{j=1}^n m_j x_j \le M </math> ; </center> | <center> <math> \sum_{j=1}^n m_j x_j \le M </math> ; </center> | ||
| − | <center> <math> x_j \ge 0 , x_j </math> — цілі числа, <math>(j=\overline{1,n})</math> </center> | + | <center> <math> x_j \ge 0 , x_j </math> — цілі числа, <math>(j=\overline{1,n})</math> . </center> |
| + | |||
| + | =='''Приклад'''== | ||
| + | Фермеру для удобрення земельної ділянки необхідно придбати 107 кг добрив. Він може купити добрива в упаковках по 35 кг вартістю 14 ум. од. або по 24 кг вартістю 12 ум. од. Метою фермера є закупівля не менше, ніж 107 кг добрив з мінімальними витратами. Причому потрібно купувати або цілу упаковку, або не купувати її зовсім, бо частину упаковки придбати неможливо. <br> | ||
| + | |||
| + | ''Розв’язання.''Позначимо кількість упаковок вагою 35 кг та вагою 24 кг відповідно змінними <math>x_1</math> та <math>x_2</math> . Маємо модель цієї задачі: | ||
| + | |||
| + | <center> <math>\min F= 14 x_1 + 12 x_2</math> </center> | ||
| + | |||
| + | <center> <math>35 x_1 + 24 x_2 \ge 107</math> ; </center> | ||
| + | |||
| + | <center> <math>x_1 \ge 0 , x_2 \ge 0 , x_1,x_2 </math> — цілі числа. </center> | ||
| + | |||
| + | У результаті розв’язування задачі будь-яким з вищена-ведених методів отримаємо оптимальний план: <math>X^{*}(x_1=1,x_2=3), F_\min =50</math>.Отже, за оптимальним планом найменші витрати, що дорівнюють 50 ум. од., можливі у разі закупівлі однієї упаковки добрив вагою 35 кг та трьох вагою по 24 кг. | ||
| + | |||
| + | == '''Література''' == | ||
Поточна версія на 16:20, 9 травня 2012
Задача про рюкзак.
Найпростішою задачею цілочислового програмування, а саме задачею лише з одним обмеженням, є задача про рю-кзак (або ранець). Така задача має багато прикладів прак-тичного застосування. Назва «задача про рюкзак» пов’язана з інтерпретацією задачі вибору найкращого складу предметів, що задовольняють певні умови гіпотетичної проблеми туриста щодо вибору для походу оптимальної кількості речей.
Турист може вибирати потрібні речі із списку з Неможливо розібрати вираз (невідома помилка): n
предметів. Відома вага кожного Неможливо розібрати вираз (невідома помилка): j
-го предмета Неможливо розібрати вираз (невідома помилка): m_j(j=\overline{1,n})
.Визначена також цінність кожного виду предметів Неможливо розібрати вираз (невідома помилка): w_j
.Максимальна вага всього вантажу в рюкзаку не може перевищувати зазначеного обсягу М. Необхідно визначити, скільки предметів кожного виду турист має покласти в рюкзак, щоб загальна цінність спорядження була максимальною за умови виконання обмеження на вагу рюкзака.
Позначимо через Неможливо розібрати вираз (невідома помилка): x_j
– кількість предметів Неможливо розібрати вираз (невідома помилка): j
-го виду в рюкзаку. Тоді математична модель задачі матиме вигляд:
— цілі числа, Неможливо розібрати вираз (невідома помилка): (j=\overline{1,n})
. Приклад
Фермеру для удобрення земельної ділянки необхідно придбати 107 кг добрив. Він може купити добрива в упаковках по 35 кг вартістю 14 ум. од. або по 24 кг вартістю 12 ум. од. Метою фермера є закупівля не менше, ніж 107 кг добрив з мінімальними витратами. Причому потрібно купувати або цілу упаковку, або не купувати її зовсім, бо частину упаковки придбати неможливо.
Розв’язання.Позначимо кількість упаковок вагою 35 кг та вагою 24 кг відповідно змінними Неможливо розібрати вираз (невідома помилка): x_1
та Неможливо розібрати вираз (невідома помилка): x_2 . Маємо модель цієї задачі:
У результаті розв’язування задачі будь-яким з вищена-ведених методів отримаємо оптимальний план: Неможливо розібрати вираз (невідома помилка): X^{*}(x_1=1,x_2=3), F_\min =50 .Отже, за оптимальним планом найменші витрати, що дорівнюють 50 ум. од., можливі у разі закупівлі однієї упаковки добрив вагою 35 кг та трьох вагою по 24 кг.
