Найти наилучшее решение

1. В контейнер упакованы изделия трёх типов. Стоимость и масса одного изделия составляют 400 тыс. р. и12 кг для первого типа, 500 тыс. р. и 16 кг для второго типа,600 тыс. и 15 кг для третьего типа. Общая масса изделий равна 326 кг. Определите минимальную и максимально возможную суммарную стоимость находящихся в контейнере изделий.
2. На заводе выпускают гоночные и дорожные велосипеды. Вместо одного можно выпустить два дорожных, причем гоночный приносит в 1,5 раза больше прибыли. Завод может выпустить 700 дорожных велосипедов в день, однако склад может принять не более 500 велосипедов в день. Сколько нужно выпускать в день велосипедов каждого вида, чтобы завод получал максимальную прибыль. Это задачи дает экономфак МГУ. Не знаем, как они вообще решаются.

Как они вообще решаются, не знаю. Может кто из экономистов откликнется.
Имхо, задачки очень разные.
1)приводит к уравнению в натуральных числах 12х+16у+15z=326
И понятно, что минимальная стоимость будет тогда, когда х (к-во изделий первого типа) будет максимально........ у меня получилось (22,2,2) стоимость 11млн
А максимальная стоимость — наоборот....................... у меня (2,2,18) стоимость 12млн 600тыс

2)Создаётся ощущение, что цифра 1,5 как-то явно лишняя. Сказали бы просто больше, но, видимо, таким способом нам сообщили, что зависимость между прибылями от дорожного и гоночного велосипеда линейная))
А вообще понятно, что склад надо забивать полностью, т.е.всего велосипедов 500, если гоночных — х, то...... Да и произвести лучше всё, что можно........... Может я в ночи чего недопонимаю, но задачка класса для 5-6 :-))

Про "цифру 1,5" — это была идиома. Конечно же, 1,5 — это десятичная дробь))))
Да и не лишняя она судя по всему ;-)

Давайте по порядку. ЗАДАЧА 1 формулируется так :

a) 4x+ 5y+ 6z=max при
12x+16y+15z=326. (1) и целочисленных неотрицательных x,y,z.

Сразу отметим, что в последнем соотношении знак именно "=", а не "<=", то есть мы имеем дело с задачей целочисленного программирования. Тогда очевидно (надеюсь, что не только мне, но и Вам), что у имеет остаток 2 при делении на 3, а z — остаток 2 при делении на 4, то есть

y=3Y+2; z=4Z+2.

Перепишем задачу в новых обозначениях (после элементарных преобразований) :

S= 4x+15Y+24Z+22=max при
x+ 4Y+ 5Z =22. (2) и целочисленных неотрицательных x,Y.Z.

Теперь вычисляем "коэффициенты полезности", т.е цену ( в сотнях т.р.за 1 кг) каждого "изделия" x,Y,Z : и ранжируем их

pZ=4.8 > px=4 > pY=3.375.

Становится понятной шкала предпочтений Z-x-Y при решении уравнения (2) Тогда уравнение (2) имеет оптимальное решение (2,0,4). а уравнение (1) — (268,2,18) при Smax=126.

b) При минимизации той же функции уравнение (2) имеет оптимальное решение (2,5,0), а уравнение (1) — (2,14,2) при Smin=68.

Видимо, я должен извиниться за аморфную структуру решения и возможные ошибки в счете : время позднее. Но за основные идеи отвечаю.

перед b) читать "(2,2,18)"

Конечно, оптимум в b) — в точке (2,17,2) и Smin=105. Спасибо за правильные выкладки.

Сначала формулируем задачи математически(строим мат модели, именно за построение мат модели подобного рода задач Канторович получил премию Нобелевского комитета).
12х+16у+15z=326
4x+ 5y+ 6z=max по х,y,z-целочисленным.
Стандартная задача целочисленного программирования.
Задача вузовская и не первого курса. Но простейшая модификация.
Решение достигается в вершинах многоугольника допустимых решений. Для этого вычисляем стоимости одного кг изделия каждого вида (коэффициенты полезности -Игорь Владимирович): 400/12=33,33 ; 500/16=31,25; 600/15=40.
Теперь ясно, как надо решать целочисленное уравнение 12x+16y+15z=326. Надо по максимуму взять z, потом х, потом у. Результат подбором: z=18,х=2 у=2. Тогда максимальная стоимость-12600тыс. Минимальная: 10500.

Велосипедная задача:
2х+у<=700
x+y<=500
x>=0, y>=0
1,5x+y=ma
Стандартная формулировка задачи линейного целочисленного программирования. Решается одним из стандартных методов. Но это частный случай, когда число неизвестных и число неравенств совпадает, можно графически. Результат: х=200, у=300

Ага. Значит с велосипедной задачей и правда никаких подвохов нет. И в этом частном случае её действительно может решить пятиклассник))

А вот для первой задачки я немного недодумала. В случае максимума всё прокатило (2,2,18), а для минимума — нет.
А недодумала я как раз о том, что важна не стоимость всего изделия, а СТОИМОСТЬ одного килограмма изделия (то что, как я теперь знаю))) называется коэффициент полезности) А в этом случае оказывается, что второе изделие самое "дешёвое", а не первое. Т.е. для минимальной стоимости нужно вторых изделий брать как можно больше. Вариант (2,17,2) и стоимость действительно 10млн 500тыс. И задача сооооооовсем не такая уж сложная. Можно давать классе в 9))))
Спасибо за вопрос!!! Мне было интересно;-)

"Велосипедную" задачу может решить пятиклассник, пока все вершины симплекса целочисленные. Чтобы не было лишних иллюзий, посмотрите то же условие с коэффициентом 2.5 вместо 2 в первом уравнении. Боюсь, что Вам предварительно придется ознакомиться с симплекс-методом и методом Гомори (или, в крайнем случае, с графическим методом отсечения).

Игорь Владимирович, я умею читать то, что пишут)))
У Бориса Михайловича уже написана системка
2х+у<=700
x+y<=500
1,5x+y=ma
Но в этом частном случае, опять-таки, по счастливой случайности, эти три прямые
у=700-2х
y=500-х
y=-1,5x пересекаются в одной точке. И целочисленность, думаю здесь совсем ни при чём, просто если бы не все три линии пересеклись в одной точке, то нужно было бы понять пересечение третьей линии с какой из двух первых будет решением. По-моему так))) Хоро

Должен Вас разочаровать : все совсем не так. Давайте по порядку.

Два первых неравенства из #32, а также x,y>=0 определяют допустимую область решений задачи. В данном случае эта область (симплекс) -_четырехугольник с вершинами в (0,0), (0.500). (200,300) и (350,0).

Имеется классическая теорема, согласно которой максимум и минимум любой линейной функции достигается как минимум в одной вершине симплекса, в данном случае — в третьей и первой.

В графическом методе удобно проводить через вершины симплекса параллельные линии уровня целевой функции (в данном случае 1.5х+у=с). Чем больше с, тем дальше эта линия проходит от начала координат и тем больше значение целевой функции. В нашем случае эти значения с соответственно равны 0,500,600,525.

Точка (200,300) [как и (0.0)] примечательна тем, что в ней линия уровня касается допустимой области, а не пересекает ее. То, что в этой точке значения х и у отличаются в 1.5 раза — не более чем случайное совпадение. Никакой особенной третьей прямой там нет.

Извините за ликбез.

Вот извинятся-то Вам сейчас, Игорь Игорь Владимирович и не за что.
Спасибо, что очень доходчиво объяснили. Действительно, про третью прямую, которая пересекает... — это мне ночь навеяла и совпадение коэффициентов))))
Я по-прежнему думаю, что подобные задачки с двумя переменными можно давать 9-тиклассникам. Симплекс они построят (неравенства с двумя переменными графически решают), а линии уровня — линейная функция с параметром с, который должен быть наибольшим.

В "академическом учебнике" (tm) Дорофеева по алгебре за 9 класс есть (хоть и помечены как факультативная тема, наряду с теорией вероятностей) задачи линейного программирования и понятие о симплекс-методе, хотя сами эти слова вслух не произносятся.

+4 от меня ;-))

Неужели математики изучают не все раздела математики? У меня инженера -физика были все разделы математического программирования наряду с токарными и слесарными специальностями, а также вождение самолета и прыжки с парашютом.

Это я начала писать: хорошо всё-таки, что я с парашютом не прыгала))))))

Спасибо за в се объяснения, даже понятно почему такие задачи дают абитуриентам.
Нам дали подумать над задачей более сложной, которая однако может быть решена и школьными методами. Задача необязательная, просто попытаться.
Имеется два вида сырья S и T в количествах 800 и 1400 единиц. Из этого сырья можно изготовлять три вида продукции: P,Q,R. Затраты сырья S на изготовление одной единицы таковы: P-4,Q-2,R-5. Затраты сырья T таковы: P-2,Q-6,R-5. Цена реализации готовых изделий P-8,Q-14,R-10 ден.ед. В задаче два вопроса: 1) Рассчитать план производства, дающий максимум прибыли. 2) По каким ценам надо продавать сырье, чтобы реализовать его было выгоднее, чем производить из него продукцию.

А чего тут пытаться ? Задача как задача.

4x+3y+5z <=800
2x+6y+5z <=1400
x,y,z>=0
8x+14y+10z=max.

ВОЗМОЖНЫ ТРИ ПОДХОДА.

1.Стандартный симплекс-метод. Плюс метода — не надо думать. Минус — абитуриенты этого не знают. Сходится за две итерации. Оптимальное решение (100/3,2000/9,0). максимум целевой функции — 30400/9.

2. Решение двойственной задачи.

4u+2v >=8
2u+6v >=14
5u+5v >=10
u,v>=0.
800u+1400v =min.

Плюс метода — можно решить графически. Минус метода — надо немного подумать. Еще один метод — абитуриенты этого тем более не знают. Ответ (u,v)=(10/9,16/9). Ответ по x,y,z тот же.

3. Использование матрицы "коэффициентов полезности" :

2 7 2
4 7/3 2.

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

Плюсы метода : счета меньше, и это можно объяснять школьникам. Минус метода — надо думать чуть больше, чем в случае 2. Ответ идентичен.

Снова извиняюсь за возможные ошибки. Надеюсь на то, что утром проснется "чистильщик" Б.Кругликов, и все будет, как надо. Если ответы действительно дробные, подробности завтра.

Ну что же, будем "чистить". Вообще говоря, Игорь Владимирович объяснил все, что нужно.Оптимальное решение у меня:(100; 200; 0), значение целевой функции — 3600. И.В. допустил описку при составлении первого неравенства.
Как решать школьнику: графически, построить вектор нормали целевой функции n(8;14;10), он показывает направление ее возрастания, самой "дальней" точкой в этом направлении будет точка (100; 200; 0).
Двойственная задача может быть решена аналогично, получаем u=1,v=2
ПРОВЕРКА: из теории известно , что максимум первой задачи должен совпадать с минимумом во второй задаче. Подставляем, убеждаемся.
Для студентов — это стандартная задача в курсе линейного программирования, для школьников возможна за счет конкретных "слабостей" этих задач.
В начале Ирина Владимировна про экономистов упомянула, но ни один не откликнулся. Думаю не случайно. Мои студенты МГЛУ(почти сплошные красотки) на 90% не в состоянии это освоить. У нас экономика- общественная наука. На Западе нет экономики как науки, есть эконометрика-прикладная математика. Наши экономисты не в состоянии читать Айвазяна, Мхитаряна. В МГЛУ преподаватели-экономисты на жалобы студентов на обилие математики(4 года) успокаивают: потерпите , вся эта математика не нужна в экономике, это же искусство.
Искусство Чубайсов, Гайдаров, Ясиных и пр.

Забыл сказать, что u=1;v=2 (как правильно вычислил их коллега Б.Кругликов) — не что иное, как "теневые цены" сырья 1-го и 2-го видов соответственно, т.е. максимальные цены привлечения дефицитных ресурсов, делающие рост производства безубыточным.

Это и есть ответ на второй вопрос задачи. Единственная проблема — как "на пальцах" , без изложения теории двойственности рассказать об этом школьнику.

Вот, что мне удалось понять.
1) Система
4x+3y+5z <=800
2x+6y+5z <=1400
x,y,z>=0
решается перебором так, что одна переменная равна 0. Это несложно и недолго,если неравенства заменяются равенствами. Можно ли это делать всегда- непонятно. В этом случае это так, наверное специально для школьников.
2) Во второй задаче третье неравенство -следствие первых двух, дальше как в первой тоже наверное специально. Составление системы в первом случае ясно, во втором -???
Наверное, нам и этого достаточно. Поняли: перебор и графически решать такие задачи. Спаибо.

Вообще-то перебор осуществляется иначе. При n неравенствах с k переменными вершины симплекса располагаются в точках, где [не менее] k неравенств из (n+k), включая требования неотрицательности переменных, обращаются в равенства. Всего таких точек C(n+k,k), и они необязательно находятся внутри допустимой области. Поэтому "лобовой" перебор с последующей проверкой допустимости планов и вычислением целевой функции в каждой допустимой точке — весьма утомительная процедура. Поэтому и придуман симплекс-метод, позволяющий на каждом новом шаге, двигаясь от вершины к вершине симплекса, увеличивать значения целевой функции, оставаясь при этом в допустимой области.

На мой взгляд, ключом к понижению размерности задачи являются "коэффициенты полезности", значения которых позволяют в ряде случаев позволяют избавиться от лишних переменных. К слову сказать, аналогичные "коэффициенты затратности" (т.е отношения элементов столбца ограничений к элементам матрицы левой части) позволяют игнорировать избыточные неравенства (если строка К.З. МИНОРИРУЕТСЯ какой-либо иной строкой этой матрицы, то соответствующее неравенство исключается из анализа). Заметим, что мы рассматриваем неотрицательные значения матрицы ограничений.

Если Вы хорошо усвоили графический метод, то это будет для Вас большим подспорьем не только при поступлении в институт, но и при обучении в нем. Остальные методы Вам там изложат с предельной подробностью.

Насколько я понял, тема закрывается. В заключение хочется выразить признательность Б.Кругликову за "доведение до ума" моих "сырых" решений. Это дорогого стоит.

Две основные мысли пока: графика и перебор в сочетании с "полезностью". Этого пока достаточно. Та, что успехов, Янг.
"доведение до ума"- благодарность с благодарностью принимается. У меня в молодости был злой инструктор.

Для поступления на заочное отделение — нужно вспомнить весь курс школьной математики, есть 20 дней на подготовку (денег на репетитора нет). Все дни свободен. Нужно хоть какую-то минимальную базу иметь (а сложности есть даже с задачами 5 класса, почти нулевой уровень). По каким учебникам стоит заниматься, чтобы пройти основы?

На фотографии — аттракцион "акробат". Будем считать, что ремни растягиваются по закону Гука, длина в нерастянутом состоянии — l, высота точек крепления ремней h, расстояние между точками крепления L. На какую максимальную высоту может подняться акробат массы M без начального толчка (сопротивлением воздуха пренебречь).

Задача 2.
Предприятие выпускает велосипеды. Постоянные затраты составляют 400 тыс.руб.Определить, сколько велосипедов должно выпускать предприятие ,чтобы начать получать прибыль ,если маржинальный доход планируется в размере 15% от выручки ,а цена одного велосипеда -1800руб.

Когда делимое увеличили на 18, а делитель в 10 раз, частное осталось прежним. Каким могло быть делимое? А каким делитель?