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

[Zelenoglazka-Blr]

Помогите, пожалуйста, разобраться с задачей. Просто безвыходное положение и очень срочная ситуация.
Условие задачи и исходные данные
Студенческие отряды СО-1, СО-2 и СО-3 численностью в а1, а2 и а3 человек принимают участие в сельскохозяйственных работах. Для уборки картофеля на полях П1, П2, П3 и П4 необходимо выделить соответственно b1, b2, b3 и b4 человек. Производительность труда студентов зависит от урожайности картофеля, а также от состава отряда и характеризуется для указанных отрядов и полей элементами матрицы [pn]3x4 (в центнерах на человека за рабочий день).
Требуется:
1) распределить студентов по полям так, чтобы за рабочий день было убрано максимально возможное количество картофеля;
2) определить, сколько центнеров картофеля будет убрано с четырех полей при оптимальном распределении студентов.
Все необходимые числовые данные приведены в таблице:
а1=25 b1=30
а2=35 b2=18
а3=50 b3=40
b4=22

p11=6, p12=9, p13=6,p14=8
p21=5, p22=9, p23=8, p24=7
p31=5, p32=4, p33=6, p34=8

Не могу определиться с тем, как правильно записать уравнения. И сомнения каким методом решать.

Заранее очень Вам всем благодарна.

-- Пт фев 12, 2010 13:39:50 --

Сначала хотела решать как транспортную задачу, методом потенциалов. Но ведь транспортная - это задача о перевозках, и на минимум.
Значит нужно решать симплекс-методом.Вот возникают сомнения по этому поводу. Функцию составила, но боюсь, что неправильно :(:(:(

[gris]

И что такого? Количество студентов равно количеству рабочих мест.
Распределение бездельников студентов по полям опишем матрицей $s_{ij}$ = сколько студентов из $i$- того отряда трудится на $j$-том поле.
Суммы по строкам и столбцам дадут 7 ограничений в виде равенств.
Целевая функция $\sum\limits_{i,j} p_{ij}\cdot s_{ij}$
Обычная задача линейного программирования. Решается в Excel солвером.

[Zelenoglazka-Blr]

в том то и дело, что нужно показать так сказать ручное решение задачи, и составить ограничения
в этом случае формулы ограничений будут со знаком = или со знаком >=?

-- Пт фев 12, 2010 14:28:29 --

Сори, не увидела про ограничения - туплю :(:(

-- Пт фев 12, 2010 14:28:50 --

И все таки решать нужно получает симплекс-методом, насколько я понимаю?

-- Пт фев 12, 2010 14:40:50 --

Функция будет выглядеть таким образом: Z=6x11+9x12+6x13+8x14+5x21+9x22+8x23+7x24+5x31+4x32+6x33+8x34 ->max

-- Пт фев 12, 2010 14:49:39 --

А ограничения:

x11/6+x12/9+x13/6+ x14/8+a1=25
x21/5+x22/9+x23/8+x24/7+a2=35
x31/5+x32/4+x33/6+x34/8+a3=50
x11/6+ x21/5+ x31/5+a4=30
x12/9+ x22/9+ x32/4+a5=18
x13/6+ x23/8+ x33/6+a6=40
x14/8+ x24/7+ x34/8+a7=22

Скажите, все ли правильно я поняла?
Заранее огромное спасибо!!!!

[gris]

формулы записывайте латиницей в окружении знаков $. x с коэффициентами записывается так: x_{23}. А то не понятно ничего.

Функция будет выглядеть таким образом:
$Z=6x_{11}+9x_{12}+6x_{13}+8x_{14}+5x_{21}+9x_{22}+8x_{23}+7x_{24}+5x_{31}+4x_{32}+6x_{33}+8x_{34} \to max$


А ограничения:

$x_{11}+x_{12}+x_{13}+ x_{14}=25$ икс это количество студентов же? Зачем его делить. Вот эта строка показывает, сколько студентов в 1 отряде.
А эта - сколько работает на 1 поле:
$x_{11}+x_{21}+x_{31}=30$
Ну и так для трёх групп и четырёх полей.
Тут не надо дополнительные переменные вводить.

Ну ещё все $x_{ij}\geqslant 0$
Я бы пользуясь ограничениями убрал 7 переменных.

[Zelenoglazka-Blr]

Спасибо Вам огромное-преогромное!!!!!!
Вы просто спасли сомневающуюся душу!!!

-- Пт фев 12, 2010 15:26:56 --

Что значит - Я бы пользуясь ограничениями убрал 7 переменных.
??????

[Zelenoglazka-Blr]

И подскажите, все-таки каким методом лучше решать - методом потенциалов или симплекс-методом?

[gris]

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

[Shtirlic]

Zelenoglazka-Blr
Я бы посоветовал методом потенциалов. Домножим все на -1, вот вам и обычная транспортная задача. Правда не помню точно, могут быть отрицательные значения в таблице. Но в любом случае можно добиваться обратной ситуации. Посмотрите в литературе, она сводится к транспортной.