Задача на оптимизацию

[PeanoJr]

Здравствуйте!
Необходимо составить оптимальную производственную программу по критерию минимума суммарных затрат при обработке четырех видов изделий (1,2,3,4) с плановым заданием, соответственно, 200,100,150,180 штук на трех взаимозаменяемых станках по следующим исходным данным.



Правильно ли я понимаю, что придется ввести двенадцать переменных, обозначающих количество времени, в течение которых каждый из трех станков будет делать одну из четырех деталей.
Пусть $x_1,x_2,x_3,x_4$ - количество времени на первую, вторую, третью и четвертую деталь, соответственно, для первого станка.
$x_1+x_2+x_3+x_4\leqslant63$

$x_5,x_6,x_7,x_8$ - время на каждую из деталей для второго станка, $x_9,x_{10},x_{11},x_{12}$ - для третьего станка, получается:
$x_5+x_6+x_7+x_8\leqslant84$
$x_9+x_{10}+x_{11}+x_{12}\leqslant126$

Из ограничений на выпуск:
$25x_1+64x_5+18x_9\geqslant200$
$43x_2+102x_6+32x_{10}\geqslant100$
$32x_3+64x_7+19x_{11}\geqslant150$
$26x_4+45x_8+15x_{12}\geqslant180$

Теперь целевая функция:
$Z=21\cdot25x_1+145\cdot43x_2+...+22\cdot15x_{12}$

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

[iifat]

Похоже на правду. Кроме последнего абзаца: не думаю, что можно обойтись без двенадцати переменных. Не считая дополнительных семи.

[PeanoJr]

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

Похоже на правду. Кроме последнего абзаца: не думаю, что можно обойтись без двенадцати переменных. Не считая дополнительных семи.

Спасибо! Дополнительных семь - Вы имеете ввиду те, которые придется добавить для решения симплекс-методом?

[PeanoJr]

Ещё один вопрос. Может ли в симплекс-методе быть так, что некоторая из переменных дважды будет определена в качестве основной?
У меня получилось так, что одна из переменных через одну итерацию снова оказалась в числе основных. Возможно ли это?

[Shtorm]

PeanoJr, да такое может быть. Ведь в симплекс-методе поиск оптимального решения производится по сути перебором различных комбинаций базисных переменных. Это как на плоскости с двумя переменными оптимальное решение может быть либо в каком-то угле многоугольника решений, либо на одной из сторон целиком многоугольника решений. Так и со многими переменными - в многомерном пространстве поиск оптимального решения ищется в вершине многомерного многогранника.

[iifat]

PeanoJr в сообщении #925338 писал(а):

которые придется добавить для решения симплекс-методом?

Именно.