задача линейного программирования.

[falazure123]

1)решить
$\sum\limits_{1}^{n} c_j x_j \to \inf$
при ограничении
$x_j \geqslant 0 , j \in 1:n$

как я думаю о решении:
если все $c_j$ неотрицательны, то в качестве $x_j$ беру нули.

А вот если есть отрицательные коэффициенты, то получается, что иксы можно брать сколь угодно большими. и получается, что целевая функция не ограничена снизу на множестве планов. Значит и решения нет. Верно ?

2) $\sum\limits_{1}^{n} c_j x_j \to \inf$
при ограничениях
$\sum\limits_{1}^{n}x_j = 1$
$x_j \geqslant 0 , j \in 1:n$

вот тут я уже не могу придумать алгоритм решения..
пробовал рассмотреть сначала неотрицательные коэффициенты, например:
$x_1 + 2 x_2 + 3x_3 \to \inf$
хотелось бы взять $x_1 = 1$, а остальные иксы - нули.
но я не уверен, что такая сумма не может быть меньше единицы..

[пианист]

Экстремум линейной функции достигается в вершинах же.

[falazure123]

пианист в сообщении #1153233 писал(а):

Экстремум линейной функции достигается в вершинах же.

это вы имеете в виду 2 задачу? ну я нарисовал двумерную картинку. действительно в вершинах.
то есть ответ будет что-то вроде $(1,0,..,0)$ или $(0,1,0,..,0)$ и тд. вот только какой из этих векторов выбрать?

в первой задаче точно нет решений?

[iifat]

А кто такой есть $\dots\rightarrow\inf$? В задачах линейного программирования либо $\dots\rightarrow\text{max}$, либо $\dots\rightarrow\text{min}$.
Первая-то задача решается легко. Не нужна даже неотрицательность всех коэффициентов. Достаточно одного, чтобы максимум не достигался.
Касательно второй — лучше почитать теорию, если вы не хотите непременно разработать её самостоятельно. Вкратце: линейная функция на выпуклом многограннике достигает минимума/максимума в вершине оного. Симплекс-метод состоит в том, что мы выбираем любую из них, смотрим на значения функций в соседних и при необходимости переходим к одной из них. Повторять до полного удовлетворения либо установления факта неограниченности.

[falazure123]

iifat в сообщении #1153266 писал(а):

А кто такой есть $\dots\rightarrow\inf$? В задачах линейного программирования либо $\dots\rightarrow\text{max}$, либо $\dots\rightarrow\text{min}$.
Первая-то задача решается легко. Не нужна даже неотрицательность всех коэффициентов. Достаточно одного, чтобы максимум не достигался.
Касательно второй — лучше почитать теорию, если вы не хотите непременно разработать её самостоятельно. Вкратце: линейная функция на выпуклом многограннике достигает минимума/максимума в вершине оного. Симплекс-метод состоит в том, что мы выбираем любую из них, смотрим на значения функций в соседних и при необходимости переходим к одной из них. Повторять до полного удовлетворения либо установления факта неограниченности.

дело в том, что эта задачка давалась ещё в самом начале курса. когда было введено только определение задачи ЛП и задачи ЛП в канонической форме. И понятие эквивалентных экстремальных задач.
То есть не предполагалось знание какой-то теории.. Поэтому и хотелось бы разобраться как дойти до решения

[пианист]

Для вывода, что нужно вершины смотреть, никакой теории не требуется, все элементарно.

[iifat]

пианист в сообщении #1153268 писал(а):

никакой теории не требуется

Ну вы ещё скажите, что для таблицы умножения никакой теории не требуется. «Элементарно» отнюдь не означает отсутствия теории.

falazure123 в сообщении #1153267 писал(а):

хотелось бы разобраться как дойти до решения

Ну дык центральная идея в том и состоит: вот у нас отрезок; где на нём линейная функция принимает минимальное/максимальное значение?
Остаётся доказать, кажется, что если мы стоим на какой-то вершине, то можем перейти к искомой вершине монотонно — и вот, в сущности, симплекс-метод готов.

[пианист]

(Таблица умножения другое дело)

Таблица умножения совсем другое дело! :)
Тут без теории никак:

[iifat]

(Оффтоп)

Во-во. Человек, небось, решил без теории обойтись — и так всё помню.

[arseniiv]

(Оффтоп)

Аааа! Некоммутативное умножение! $3\times7=21$ там выше.