2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 задача линейного программирования.
Сообщение21.09.2016, 12:01 
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$, а остальные иксы - нули.
но я не уверен, что такая сумма не может быть меньше единицы..

 
 
 
 Re: задача линейного программирования.
Сообщение21.09.2016, 12:23 
Аватара пользователя
Экстремум линейной функции достигается в вершинах же.

 
 
 
 Re: задача линейного программирования.
Сообщение21.09.2016, 12:37 
пианист в сообщении #1153233 писал(а):
Экстремум линейной функции достигается в вершинах же.

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

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

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

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


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

 
 
 
 Re: задача линейного программирования.
Сообщение21.09.2016, 14:46 
Аватара пользователя
Для вывода, что нужно вершины смотреть, никакой теории не требуется, все элементарно.

 
 
 
 Re: задача линейного программирования.
Сообщение21.09.2016, 16:52 
пианист в сообщении #1153268 писал(а):
никакой теории не требуется
Ну вы ещё скажите, что для таблицы умножения никакой теории не требуется. «Элементарно» отнюдь не означает отсутствия теории.
falazure123 в сообщении #1153267 писал(а):
хотелось бы разобраться как дойти до решения
Ну дык центральная идея в том и состоит: вот у нас отрезок; где на нём линейная функция принимает минимальное/максимальное значение?
Остаётся доказать, кажется, что если мы стоим на какой-то вершине, то можем перейти к искомой вершине монотонно — и вот, в сущности, симплекс-метод готов.

 
 
 
 Re: задача линейного программирования.
Сообщение21.09.2016, 20:55 
Аватара пользователя

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

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

 
 
 
 Re: задача линейного программирования.
Сообщение21.09.2016, 23:49 

(Оффтоп)

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

 
 
 
 Re: задача линейного программирования.
Сообщение21.09.2016, 23:52 

(Оффтоп)

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

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group