Question

Как решить задачу целочисленного программирования в Excel?

Помогите пожалуйста решить задачу целочисленного программирования в Excel

В контейнер упакованы изделия трех типов. Стоимость и вес одного изделия составляет 400 руб. и 12 кг. для первого типа, 500 руб. и 16 кг. для второго типа, 600 руб. и 15 кг. для третьего типа. Общий вес комплектующих равен 326 кг. Определить максимальную и минимальную возможную суммарную стоимость изделий, находящихся в контейнере. Лучше со скриншотами.

Answer 1

Я решала бы такую задачу так, не знаю, может быть будет что то не так, но у меня такое вот решение:

Допустим в контейнер упакованы приблизительно х изделий первого типа, у - это изделия второго типа и z изделий третьего типа. Тогда общая масса изделий составит (12х + 16у + 15z) кг, вот такое уравнение очень подходит для данной задачи.

Идем дальше, по условию задачи значение составленного выражения составляет 326. Составим и решим данное уравнение:

12х + 16у + 15z = 326 (*), где х, у, z – натуральные числа.

Здесь заметим, что 15z = 326 – 12х – 16у; 15z = 2(163 – 6х – 8у). Значит, 15z –четное число. Отсюда следует, что z – четно.

Введем новое обозначение: t = 2z. Тогда будем иметь: 30t = 2(163-6x – 8y), т.е. 15t = 163 – 2(3x + 4y).

Число 2(3х +4у) – четное число, значит, 163 – 2(3x + 4y) – нечетно, следовательно, число 15t – также нечетное число, что возможно лишь при нечетных значениях t.

Заметим, что t может принимать значения, лишь равные 1; 3; 5; 7; 9, так как 15 или 15 . (Наименьшим значением х и у в данном контексте может быть только число 1).

Если значение t – натуральное число, то отсюда выходит - 15

Получим соответствующие значения z: 2; 6; 10; 14; 18.

Приведем уравнение (*) к двучленным уравнениям для каждого полученного значения z.

Рассмотрим несколько случаев:

Случай 1.

Для z = 2 имеем: 12х + 16у = 326 – 30, т.е. 12х + 16у = 296, 3х + 4у = 74. Поскольку число (74 – 3х) кратно 4, то оно четное. Но оно четно лишь при четных значениях х.

Вычислим значение у для наименьшего четного натурального числа х = 2. Оно окажется равным 17.

Одно из искомых решений уравнения (*) есть тройка данных чисел (2; 17; 2).

Поскольку результат деления (74 -3х) на 4 обязано быть натуральным числом, то последующими значениями х могут быть только числа: 6; 10; 14; 18 и 22.

Простые вычисления приведут к результатам:

у = 14, если х = 6; у = 11, если х = 10; у = 8, если х = 14; у = 5, если х = 18; у = 2, если х = 22.

Значит, следующими тройками чисел решения уравнения (*) будут: (6; 14; 2), (10; 11; 2), (14; 8; 2), (18; 5; 2), (22; 2; 2).

Теперь решаем Случай 2.

Вот здесь, пусть приблизительно наш z = 6. Тогда 12х + 16у = 326 – 90, 12х + 16у = 236, 3х + 4у = 59, (59 – 3х) – число четное, следовательно, число 3х – нечетно.

При х = 1 имеем: у = 14. Очевидно, что последующими значениями х могут быть только числа: 5; 9; 13 и 17.

Легко получим: у = 11, если х = 5; у = 8, если х = 9; у = 5, если х = 13 и у = 2, если х = 17.

Натуральными решениями уравнения (*) в данном случае будут тройки чисел: (1; 14; 6), (5; 11; 6), (9; 8; 6), (13; 5; 6), (17; 2; 6).

Случай 3.

При z = 10 12х + 16у = 326 – 150, 12х + 16у = 176, 3х + 4у = 44, . 44 кратно 4. Значит, 3х также кратно 4. А это возможно только при значениях х, кратных 4. Нетрудно понять, что значениями х могут быть только лишь числа: 4; 8; 12.

Очевидно, что у = 8 при х = 4, у = 5 при х = 8, у = 2 при х = 12.

Тройки чисел: (4; 8; 10), (8; 5; 10), (12; 2; 10) являются решениями уравнения (*).

Случай 4.

Пусть z = 14. Тогда 12х + 16у = 326 – 210, 12х + 16у = 116, 3х + 4у = 29, .

Поскольку (29 – 3х) кратно 4, то 3х – число нечетное, что возможно лишь при нечетных значениях х. При х = 1 число (29 – 3х) не кратно 4. При х = 3 значение выражения равно 5.

А следующим рассматриваемым значением х может быть только число 7.

При х = 7 у= 2.

В данном случае искомыми решениями уравнения (*) будут тройки чисел: (3; 5; 14) и (7; 2; 14).

Случай 5.

Пусть z = 18. Тогда 12х + 16у = 326 – 270, 12х + 16у = 56, 3х + 4у = 14, .

Очевидно, что х – четное число. Для х = 2 имеем: у = 2. Другие значения, кратные 4 и большие 2 уже не подойдут.

Таким образом, мы нашли последнюю тройку чисел (2; 2; 18) удовлетворяющую уравнению (*).

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

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

И конечный итог данной задачи

Ответ: 10500 тыс.р., 12600 тыс. р.