Экономико-математический практикум
Оптимальный план прямой задачи. Значения функций целочисленного и нецелочисленного решений. Оптимальное решение двойственной задачи и условия дополняющей нежесткости. Условия канонической задачи линейного программирования. Метод Жордана–Гаусса.
| Рубрика | Экономико-математическое моделирование |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 20.01.2011 |
| Размер файла | 323,0 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
|
D= |
+ |
+ |
+ |
+ |
+ |
+ |
+ |
|||
|
7 |
29 |
30 |
1 |
27 |
22 |
0* |
17 |
|||
|
3 |
22 |
15 |
34 |
20 |
25 |
0' |
6 |
|||
|
33 |
12 |
10 |
0* |
6 |
24 |
35 |
36 |
|||
|
17 |
28 |
0* |
6 |
0' |
17 |
19 |
37 |
+ |
||
|
8 |
27 |
9 |
3 |
18 |
26 |
1 |
0* |
|||
|
23 |
0* |
29 |
47 |
24 |
16 |
0' |
30 |
|||
|
0* |
22 |
43 |
28 |
14 |
25 |
11 |
23 |
|||
|
2 |
16 |
28 |
20 |
41 |
0* |
12 |
25 |
е=2
П.2. Помечаем знаком «+» сверху столбцы: 1, 2, 3, 4,6, 7,8 и считаем эти столбцы занятыми. Незанятый нуль находится в четвертой строке пятого столбца 04,5 , во второй строке и шестой строках седьмого столбца. Помечаем их штрихом 0'4,5 , 0'2,7 , 0'6,7. Переходим к пункту 3.
П.3. Столбец 3 считаем незанятым и знак «+» сверху снимаем (обводим в рамку), а четвертую строку объявляем занятой и помечаем знаком «+» справа. Возвращаемся к третьему абзацу п.2.
П.2. Незанятых нулей нет, переходим к п.5.
П.5. Среди незанятых элементов находим минимальный, который обозначим через , е=d3,5=6. Преобразуем матрицу : незанятые элементы уменьшим на 6; дважды занятые увеличим на 6; остальные элементы оставим без изменения. Получим матрицу , в которой имеется один незанятый нуль, переходим к четвертому абзацу п.2.
|
+ |
+ |
+ |
+ |
+ |
+ |
+ |
||||
|
D1= |
7 |
29 |
24 |
1 |
21 |
22 |
0* |
17 |
||
|
3 |
22 |
9 |
34 |
14 |
25 |
0' |
6 |
+ |
||
|
33 |
12 |
4 |
0* |
0' |
24 |
35 |
36 |
|||
|
23 |
34 |
0* |
12 |
0' |
23 |
25 |
43 |
+ |
||
|
8 |
27 |
3 |
3 |
12 |
26 |
1 |
0* |
|||
|
23 |
0* |
23 |
47 |
18 |
16 |
0' |
30 |
|||
|
0* |
22 |
37 |
28 |
8 |
25 |
11 |
23 |
|||
|
2 |
16 |
22 |
20 |
35 |
0* |
12 |
25 |
П.2. Незанятый нуль находится в третьей строке пятого столбца 03,5 . Помечаем штрихом 0'3,5. Во второй строке седьмого столбца находится нуль со штрихом. Помечаем штрихом 0'2,7 и считаем седьмой столбец незанятым, знак «+» сверху снимаем, а вторую строку объявляем занятой и помечаем знаком «+» справа.
|
+ |
+ |
+ |
+ |
+ |
+ |
+ |
||||
|
D2= |
7 |
29 |
24 |
1 |
21 |
22 |
0* |
17 |
||
|
3 |
22 |
9 |
34 |
14 |
25 |
0' |
6 |
+ |
||
|
33 |
12 |
4 |
0* |
0' |
24 |
35 |
36 |
|||
|
23 |
34 |
0* |
12 |
0' |
23 |
25 |
43 |
+ |
||
|
8 |
27 |
3 |
3 |
12 |
26 |
1 |
0* |
|||
|
23 |
0* |
23 |
47 |
18 |
16 |
0' |
30 |
|||
|
0* |
22 |
37 |
28 |
8 |
25 |
11 |
23 |
|||
|
2 |
16 |
22 |
20 |
35 |
0* |
12 |
25 |
П.5. Переходим к пункту 2. Помечаем звездочкой 0*6,5, штрихом 0'8,3, 0'2,7. В третьей нет , следовательно, переходим к пункту 4, е=d6,4=7 после преобразований, получим матрицу D3
|
+ |
+ |
+ |
+ |
+ |
+ |
+ |
||||
|
D3= |
7 |
29 |
24 |
1 |
21 |
22 |
0* |
17 |
||
|
3 |
22 |
9 |
34 |
14 |
25 |
0' |
6 |
+ |
||
|
33 |
12 |
4 |
0* |
0' |
24 |
35 |
36 |
|||
|
23 |
34 |
0* |
12 |
0' |
23 |
25 |
43 |
+ |
||
|
8 |
27 |
3 |
3 |
12 |
26 |
1 |
0* |
|||
|
23 |
0* |
23 |
47 |
18 |
16 |
0' |
30 |
|||
|
0* |
22 |
37 |
28 |
8 |
25 |
11 |
23 |
|||
|
2 |
16 |
22 |
20 |
35 |
0* |
12 |
25 |
П.4. Строим цепочку из нулей. Начиная от только что отмеченного штрихом нуля (0'2,7), идем по строке до 5,2 цепочка состоит из двух элементов Ц: 07,2, 0'5,2. В матрице такие цепочки обозначают так . После преобразования получим новый набор нулей со звездочкой (), который содержит на одну звездочку больше, чем предыдущий набор.
Проводим следующие пересчеты.
|
+ |
+ |
+ |
+ |
+ |
+ |
|||||
|
D3= |
25 |
0 |
0* |
27 |
19 |
16 |
20 |
32 |
+ |
|
|
3 |
43 |
2 |
7 |
23 |
14 |
5 |
0* |
+ |
||
|
6 |
32 |
0 |
23 |
20 |
5 |
18 |
7 |
+ |
||
|
0* |
36 |
10 |
0 |
0 |
5 |
2 |
17 |
|||
|
0 |
0' |
9 |
19 |
5 |
45 |
19 |
12 |
+ |
||
|
15 |
24 |
10 |
7 |
0' |
0* |
5 |
5 |
|||
|
22 |
0* |
13 |
8 |
9 |
15 |
22 |
9 |
|||
|
6 |
32 |
0 |
20 |
7 |
34 |
0* |
8 |
+ |
Процесс окончен, так как число нулей со звездочкой равно размерности матрицы эффективности.
Оптимальный вариант выбора (1,2)(2,7)(3,8)(4,1)(5,4),(6,6),(7,5),(8,3). Это значит, что первая невеста выберет второго жениха, вторая невеста седьмого жениха, третья -восьмого, четвертая первого, пятая четвертого, шестая - шестого, седьмая невеста пятого жениха, а восьмая невеста выберет третьего жениха.
При этом максимальная суммарная эффективность (суммарная продолжительность жизни всех семей) равна: (единиц эффективности)
Подобные документы
Цель работы: изучить и научиться применять на практике симплекс - метод для решения прямой и двойственной задачи линейного программирования. Математическая постановка задачи линейного программирования. Общий вид задачи линейного программирования.
реферат [193,4 K], добавлен 28.12.2008- Примеры использования графического и симплексного методов в решении задач линейного программирования
Экономико-математическая модель получения максимальной прибыли, её решение графическим методом. Алгоритм решения задачи линейного программирования симплекс-методом. Составление двойственной задачи и её графическое решение. Решение платёжной матрицы.
контрольная работа [367,5 K], добавлен 11.05.2014 Исследование методом Жордана-Гаусса системы линейных уравнений. Решение графическим и симплексным методом задач линейного программирования. Экономико-математическая модель задачи на максимум прибыли и нахождение оптимального плана выпуска продукции.
контрольная работа [177,8 K], добавлен 02.02.2010Математическая теория оптимального принятия решений. Табличный симплекс-метод. Составление и решение двойственной задачи линейного программирования. Математическая модель транспортной задачи. Анализ целесообразности производства продукции на предприятии.
контрольная работа [467,8 K], добавлен 13.06.2012Теоретические основы экономико-математических методов. Этапы принятия решений. Классификация задач оптимизации. Задачи линейного, нелинейного, выпуклого, квадратичного, целочисленного, параметрического, динамического и стохастического программирования.
курсовая работа [2,3 M], добавлен 07.05.2013Математическая формулировка экономико-математической задачи. Вербальная постановка и разработка задачи о составлении графика персонала. Решение задачи о составлении графика персонала с помощью программы Microsoft Excel. Выработка управленческого решения.
курсовая работа [1,2 M], добавлен 12.01.2018Решение задачи линейного программирования графическим и симплекс-методом. Решение задачи двойственной к исходной. Определение оптимального плана закрепления потребителей за поставщиками однородного груза при условии минимизации общего пробега автомобилей.
контрольная работа [398,2 K], добавлен 15.08.2012Симплекс метод решения задач линейного программирования. Построение модели и решение задачи определения оптимального плана производства симплексным методом. Построение двойственной задачи. Решение задачи оптимизации в табличном процессоре MS Excel.
курсовая работа [458,6 K], добавлен 10.12.2013Понятие "транспортная задача", ее типы. Отыскание оптимального плана перевозок однородного груза, при котором запросы цехов будут удовлетворены при минимальной суммарной стоимости перевозок. Решения прямой и двойственной задачи линейного программирования.
контрольная работа [81,9 K], добавлен 14.09.2010Решение задач линейного программирования на примере ПО "Гомсельмаш". Алгоритм и экономико-математические методы решения транспортной задачи. Разработка наиболее рациональных путей, способов транспортирования товаров, оптимальное планирование грузопотоков.
курсовая работа [52,3 K], добавлен 01.06.2014
