Линейное программирование или матан

Думаю над 4-ыми номерами вот этих вариантов контрольной работы (вуз, честно говоря, не помню)

Есть еще пара вариантов. В общем, с совместностью понятно, а вот с минимумом функции не совсем. По сути задача на условный экстремум, но вряд ли тут функция Лагранжа или типа того (во-первых, для этого уровня слишком сложно, во-вторых, это все-таки линейное программирование или линейная алгебра, а не матан). Думаю, из какой логики исходить...

Пусть тройка неизвестных являются координатами вектора в трёхмерном пространстве, тогда решением системы является что за множество точек? а какую характеристику этого вектора надо минимизировать? Ну и решайте задачу методами аналитической геометрии.

Спасибо!

Но, мне кажется, это все еще слишком сложно для этого уровня. Я подозреваю, что есть какой-то способ найти минимум длины вектора-решения СЛАУ и без непосредственно решения СЛАУ :)

Решение неоднородной СЛАУ — это линейное многообразие. Нас интересует нормальный вектор линейного многообразия, а точнее его длина... Если найти решение, направляющее подпространство, то там найти его уже не проблема. Но возможно ли это как-то сделать, не решая СЛАУ? Что-то не могу сообразить.

"Найти решение системы", не решая её? Это возможно лишь в том случае, если ранее кто-то решил её в общем виде и опубликовал готовую формулу.
Координаты вектора нормали простым способом связаны с коэффициентами линейного уравнения. Вычисляем их и сводим задачу к стереометрической, которая не сложнее заданий 14 ЕГЭ.

Не "найти решение, не решая системы", а "найти длину кратчайшего решения, не решая системы".

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

"Координаты вектора нормали простым способом связаны с коэффициентами линейного уравнения" — нормали к чему? Нормального вектора линейного многообразия?

И если да, то если не секрет, как связаны? :) Я же это и пытаюсь понять.

Хорошо, буду трактовать вопрос как "найти требуемое частное решение, не выписывая в явном виде общее решение системы".

Меня пугает термин "линейное многообразие" (я или забыл, или не знал, что под ним понимается), поэтому я более простыми словами буду выражаться.
1. Множество точек в трёхмерном пространстве, декартовы координаты которых удовлетворяют линейному уравнению, является плоскостью, если не все коэффициенты уравнения нулевые. В вышеприведённых вариантах это условие выполняется.
2. Я не владею техникой набора формул в стиле TeX, поэтому вместо выдачи готового результата отошлю вас в поиск. Если у вас нет под рукой справочника по аналитической геометрии, то наберите "нормальный вектор плоскости" и, я уверен, получите десятки ссылок. Как математику вам легко будет выбрать нужную и проверить, соответствует ли найденная формула действительности.

Сергей Иванович, спасибо вам за помощь и главное за желание помочь.

Правда, меня все-таки смущает вот эта "нормаль к плоскости", о которой вы говорите. У нас все-таки не плоскость, а прямая (пересечение двух плоскостей в случае, если система совместна), и нам нужна в таком случае нормаль к прямой, притом соединяющая прямую и начало координат. Это если говорить языком ангема.

Про нормальный вектор линейного многообразия я не буду опять говорить, потому что его найти, найдя решение системы уравнений, относительно несложно. И вот его длина-то нам и нужна.

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

Да, нам нужен вектор нормали к прямой, исходящий из начала координат. Или ваш студент не в состоянии зазубрить формулу для его расчёта, а выполнять умеет только арифметические действия с числами? А как он задачу номер 2 решает, исключительно методом Гаусса? На мой взгляд, формулы Крамера более громоздкие, чем для расстояния от точки до прямой в пространстве.

Есть ещё метод наименьших квадратов ...

В первом нужно найти точки пересечения прямых и просто подставить их в функцию (несмотря на некрасивые коэффициенты, точки пересечения получаются простые).

Во втором нужен ТОЛЬКО метод Гаусса, и результат получается после пары действий (корни там, где я проверял, 1, -1, 0 — других нет).

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

Понимаете? Поэтому я и размышляю над необычной "сложностью" четвертого задания и ищу элементарный "метод".

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

Ну так тупым подбором-то во всех вариантах задачу 4 можно устно решить.
Полминуты медитации — и видно, что переменные в системах во всех вариантах разделяются, причём минимум суммы квадратов достигается, когла две из них равны нулю.

Ну-ка, что-то интересное :) Потому что я пока этого не вижу.

В каком смысле разделяются? и почему такой вывод можно сделать про сумму квадратов?

Я излишне поспешил с выводом. На самом деле нули не всегда дают минимум.
Перебирая миноры расширенной матрицы коэффициентов, можно увидеть, что во всех вариантах наличествует прямая пропорциональность между вектором коэффициентов при одном неизвестном и вектором свободных слагаемых. Следовательно, оставшаяся пара неизвестных должна быть связана прямой пропорциональностью.
Систему всё равно придётся решить, но решается она легко, тем же методом Гаусса. Из этой пары выбирают принимающую любые значения неизвестную, через неё выражают две остальных и эти выражения подставляют в минимизируемую функцию, а точку минимума умеют находить по шаблону даже те школьники, кто не обладает глубокими знаниями.

Ну да, это, наверное, самый простой метод, какой можно представить. Других экстремумов у функции не будет, поэтому достаточно просто найти ноль производной (либо даже вершину параболы по известной формуле). Главное, потом еще подставить в функцию и найти ее значения...

Все эти нетривиальные вещи для нас очень простые, а вот для гуманитариев, блин, китайская грамота по большому счету. Ну, попытаюсь объяснить.

Спасибо за помощь!

Если СЛУ [m]Ax=b[/m] с коэффициентами над полем [m]\mathbb{R}[/m] имеет больше одного решения, то решение с минимальной евклидовой нормой может быть выражено как [m]x=A^{+}b[/m], где [m]A^{+}[/m] есть псевдообратная матрица Мура-Пенроуза (анг.: Moore-Penrose pseudoinverse).

Я так понимаю, это и есть метод наименьших квадратов.

Спасибо, Андрей Михайлович, но это way too круто для этого уровня :) Если можете, прокомментируйте, пожалуйста, https://ask.profi.ru/q/teorver-mnogomernoe-normalnoe-raspredelenie-37052/

это называется задача квадратичного программирования. для нее, как и для линейного программирования разработано много методов, в том числе и модифицирован симплекс-метод. надо спросить клиента — что именно им давали, но скорее всего именно его.

Ого, спасибо!

Клиент не в курсе, т.к. не ходил на занятия и не ведет записей. Попробую разобрать модифицированный симплекс-метод.

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

Акулич. математическое программирование в примерах и задачах.

У Ермакова только линейное программирование. Посмотрите ещё Хемди А Таха «Исследование операций».

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

Существуют ли методы решения задач линейного программирования на множестве натуральных чисел

Условие отсутствия решений в задаче линейного программирования