Отправляет email-рассылки с помощью сервиса Sendsay
  Все выпуски  

RFpro.ru: Дискретная математика


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный платный хостинг на базе Windows 2008

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Чемпионы рейтинга экспертов в этой рассылке

Гордиенко Андрей Владимирович
Статус: Профессор
Рейтинг: 3975
∙ повысить рейтинг »
_Ayl_
Статус: Студент
Рейтинг: 1406
∙ повысить рейтинг »
Гаряка Асмик
Статус: Практикант
Рейтинг: 1119
∙ повысить рейтинг »

/ НАУКА И ОБРАЗОВАНИЕ / Точные и естественные науки / Дискретная математика

Номер выпуска:158
Дата выхода:10.01.2010, 21:00
Администратор рассылки:Alexey G. Gladenyuk, Управляющий
Подписчиков / экспертов:113 / 45
Вопросов / ответов:5 / 6

Вопрос № 175825: Здравствуйте Уважаемые эксперты!Помогите пожалуйста решить задачку Решить задачу линейного программирования графическим методом. F(x)= -12x1+ 3x2→extr; 7x1 +3x2 &...


Вопрос № 175829: Здравствуйте Уважаемые эксперты! Требуется ваша помощь Динамическое программирование Найти оптимальное распределение средств между 5 предприятиями при условии, что прибыль f (x...
Вопрос № 175835: Здравствуйте Уважаемые эксперты! Требуется ваша помощь Симплекс-метод. Для производства продукции трех видов A, B и C можно использовать материал только трех сортов. При этом на и...
Вопрос № 175842: Здравствуйте Уважаемые эксперты! Требуется ваша помощь 6. Теория графов Найти кратчайшее расстояние от вершины B до вершин A, C, D, E, F, G. A B C D E F G A ∞...
Вопрос № 175845: Здравствуйте Уважаемые эксперты! Требуется ваша помощь 7. Теория игр Для следующих платежных матриц определить нижнюю и верхнюю цены игры, минимаксные стратегии и оптимальные ...

Вопрос № 175825:

Здравствуйте Уважаемые эксперты!Помогите пожалуйста решить задачку

Решить задачу линейного программирования графическим методом.

F(x)= -12x1+ 3x2→extr;

7x1 +3x2 ≥ 21,
7x1 + 6x2 ≤ 42,
4x1─ x2 ≥ 0,
x1 ≤ 6,
x1 ≥ 0, x2 ≥ 0.

заранее благодарен...

Отправлен: 04.01.2010, 20:46
Вопрос задал: kot31, Посетитель
Всего ответов: 2
Страница вопроса »


Отвечает Сергей Бендер, 3-й класс :
Здравствуйте, kot31.

Не знаю, что конкретно у вас имеют в виду под "графическим методом", но вот нарисовал, как понял. Неясно, который из экстремумов надо найти, -- стрелочками показано направление градиента F(x), т.е. на максимум. Ограничения подписаны. Единственно, координатные оси надо добваить, если у вас требуют.
http://files.mail.ru/C91P14

Ответ отправил: Сергей Бендер, 3-й класс
Ответ отправлен: 05.01.2010, 11:34

Оценка ответа: 5
Комментарий к оценке:
спасибо,то что нужно!

Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 258366 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:
  • Вам помогли? Пожалуйста, поблагодарите эксперта за это!
    Отвечает Гордиенко Андрей Владимирович, Профессор :
    Здравствуйте, kot31.



    С уважением.

    -----
    Пусть говорят дела

    Ответ отправил: Гордиенко Андрей Владимирович, Профессор
    Ответ отправлен: 05.01.2010, 14:14

    Оценка ответа: 5
    Комментарий к оценке:
    превосходно!

    Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 258374 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:
  • Вам помогли? Пожалуйста, поблагодарите эксперта за это!


    Вопрос № 175829:

    Здравствуйте Уважаемые эксперты! Требуется ваша помощь

    Динамическое программирование

    Найти оптимальное распределение средств между 5 предприятиями при условии, что прибыль f (x), полученная от каждого предприятия, является функцией от вложенных в него средств х. Выписать все оптимальные управления.




    Отправлен: 04.01.2010, 21:46
    Вопрос задал: kot31, Посетитель
    Всего ответов: 1
    Страница вопроса »


    Отвечает Гаряка Асмик, Практикант :
    Здравствуйте, kot31.

    Большой объем вычислений не дает возможности поместить все в форму для ответа. Решение в файле http://rfpro.ru/upload/1311.
    -----
    Я ни от чего, ни от кого не завишу.

    Ответ отправил: Гаряка Асмик, Практикант
    Ответ отправлен: 09.01.2010, 21:34

    Оценка ответа: 5

    Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 258513 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:
  • Вам помогли? Пожалуйста, поблагодарите эксперта за это!


    Вопрос № 175835:

    Здравствуйте Уважаемые эксперты! Требуется ваша помощь

    Симплекс-метод.
    Для производства продукции трех видов A, B и C можно использовать материал только трех сортов. При этом на изготовление единицы изделия вида A расходуется 1 кг материала первого сорта, 0 кг материала второго сорта, 6 кг материала третьего сорта. На изготовление единицы изделия вида B расходуется 0 кг материала первого сорта, 5 кг материала второго сорта, 8 кг материала третьего сорта. На изготовление единицы изделия вида C расходуется 5 кг материала первого сорта, 5 кг материала второго сорта, 0 кг материала третьего сорта. На складе фабрики имеется всего материалов первого, второго и третьего сортов в количествах соответственно 78 кг, 60 кг, 60 кг. От реализации единицы готовой продукции вида A фабрика имеет прибыль 18 рублей, вида B 17 рублей вида C 15 рублей. Составить план производства продукции, доставляющий максимальную прибыль .

    Задание:
    1.Составить экономическую модель задачи в табличной форме.
    2.Составить математическую модель задачи. Решить задачу симплекс-методом и сделать анализ полученных результатов.

    Отправлен: 04.01.2010, 22:46
    Вопрос задал: kot31, Посетитель
    Всего ответов: 1
    Страница вопроса »


    Отвечает Гаряка Асмик, Практикант :
    Здравствуйте, kot31.

    Необходимо найти (x1, x2, x3) - количество единиц изделия A, B, C соответственно.
    Целевая функция 18x1+17x2+15x3→max
    Мы не можем потратить сырья больше, чем имеется на складе, поэтому ограничения имеют вид неравенств. Чтобы перейти к равенствам, добавляем избыточные переменные x4,5,6
    Система ограничений Ax=b, где
    Код:

    |1 0 6 1 0 0 |
    A= |0 5 8 0 1 0 |
    |5 5 0 0 0 1 |

    b=(78,60,60)
    xi>=0
    Перейдем к векторной записи задачи линейного программирования : P0=(78,60,60), P1=(1,0,5), P2=(0,5,5), P3=(6,8,0),P4=(1,0,0),P5=(0,1,0),P 6=(0,0,1)
    В нашем случае базис выражается легко, его составляют дополнительно введенные свободные переменные x­­4­, x­5, x­6­­.

    Для получения опорного плана надо прировнять к нулю небазисные переменные, тогда получим:
    x = (0; 0; 0; 0; 15; 9; 30)
    Опорный план получен, и первый этап решения задачи завершен.

    Для проверки на оптимальность опорного плана X1 построим первую симплекс-таблицу
    Таблица 1
    Код:

    БП СЧ x1* x2 x3 x4 x5 x6
    x4 78 1 0 5 1 0 0
    x5 60 0 5 5 0 1 0
    x6* 60 6 8 0 0 0 1
    Y 0 -18 -17 -15 0 0 0

    Алгоритм:
    1) Проверяем базисные решения на оптимальность. Просматриваем знаки коэффициентов последней строки таблицы, исключая коэффициент при свободн ом члене. Наличие отрицательных коэффициентов в последней строке говорит о том, что решение не оптимально.
    2) Выбираем из небазисных переменных ту, которая способна при введении её в базис увеличить значение целевой функции, т.е. переменную, имеющую наибольший отрицательный коэффициент в последней строке и отмечаем её звездочкой «*» - разрешающий столбец.
    3) Определяем, какая из базисных переменных должна быть выведена из базиса. Для этого определяем минимальное частное от деления соответствующих свободных членов и положительных коэффициентов столбца отмеченного звездочкой. Коэффициент который находится на пересечении разрешающей строки и разрешающего столбца называется разрешающим элементом.
    4) Вводимую в базис переменную выражаем через переменную, выводимую из базиса и другие небазисные переменные. Все элементы разрешающей строки делим на разрешающий элемент. Далее выражаем все остальные переменные через новую базисную. Для этого мы должны сделать равными 0 все ос тальные элементы разрешающего столбца таблицы 1, кроме стоящего на пересечении с разрешающей строкой. Домножаем на необходимое число разрешающую строку таблицы 1 и прибавляем к другим строкам. Получаем симплекс-таблицу 2.
    Код:

    БП СЧ x1 x2 x3* x4 x5 x6
    x4 68 0 -4/3 5 1 0 -1/6
    x5* 60 0 5 5 0 1 0
    x1 10 1 4/3 0 0 0 1/6
    Y 180 0 7 -15 0 0 3

    Анализируем таблицу 2. В строке целевой функции есть отрицательные элементы, т.е. решение не является оптимальным, поэтому переходим к следующей симплекс-таблице. Выводим из базиса x5, вводим в базис x3.
    Код:

    БП СЧ x1 x2 x3 x4 x5 x6
    x4 8 -5 -19/3 0 1 -1 -1/6
    x3 12 0 1 1 0 1/5 0
    x1 10 1 4/3 0 0 0 1/6
    Y 360 0 22 0 0 3 3

    В столбце свободных членов и в строке целевой функции нет отрицательных элементов, следовательно можно сделать вывод о том, что решение оптимально. Полученные значения удовлетворяют ограничениям задачи.
    Можно выписать ответ. Значения базисных переменных и целевой функции выписываются из столбца свободных членов. Все небазисные переменные равны 0.
    x1=10
    x2=0
    x3=12
    x4=8
    Предприятие будет выпускать 10 изделий 1-го вида A и 12 изделий вида C. x4=8 - это неизрасходованный остаток сырья 1-го сорта. Прибыль при этом составить 360 рублей.
    -----
    Я ни от чего, ни от кого не завишу.

    Ответ отправил: Гаряка Асмик, Практикант
    Ответ отправлен: 10.01.2010, 03:38

    Оценка ответа: 5

    Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 258519 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:
  • Вам помогли? Пожалуйста, поблагодарите эксперта за это!


    Вопрос № 175842:

    Здравствуйте Уважаемые эксперты! Требуется ваша помощь

    6. Теория графов

    Найти кратчайшее расстояние от вершины B до вершин A, C, D, E, F, G.

    A B C D E F G
    A ∞ 46 85 23 75 81 68
    B 46 ∞ 68 15 64 57 20
    C 85 68 ∞ 19 67 51 27
    D 23 15 19 ∞ 46 51 23
    E 75 64 67 46 ∞ 24 29
    F 81 57 51 51 24 ∞ 52
    G 68 20 27 23 29 52 ∞

    Отправлен: 05.01.2010, 14:46
    Вопрос задал: kot31, Посетитель
    Всего ответов: 1
    Страница вопроса »


    Отвечает Гордиенко Андрей Владимирович, Профессор :
    Здравствуйте, kot31.

    Можно поступить следующим образом, если в Вашем распоряжении нет программы, реализующей какой-либо алгоритм решения поставленной задачи. Рассмотрим пути от вершины B до вершины A. Имеем:
    1) путь, соединяющий вершины B и A непосредственно, длиной |BA| = 46. Все остальные пути не содержат это ребро;
    2) путь, соединяющий вершины B и A через вершину D, включающий ребро |BD| = 15. Все остальные пути не содержат это ребро;
    3) путь, соединяющий вершины B и A через вершину G, включающий ребро |BG| = 20. Все остальные пути не содержат это ребро.
    Пути, проходящие от вершины B к вершине A через вершины C, E, F, не рассматриваем, поскольку их длины будут заведомо больше длины |BA|.

    Кандидатом в кратчайшие пути является путь |BA| = 46.
    Рассматриваем теперь пути, соединяющие вершины D и A. Имеем:
    1) |DA| = 23; |BA| = |BD| + |DA| = 15 + 23 = 38;
    2) |DC| = 19.

    Кандидатом в кратчайшие пути теперь является путь |BA| = |BD| + |D A| = 38.
    Рассматриваем теперь пути, соединяющие вершины C и A. Имеем
    1) |CA| = 85; |BA| = |BD| + |DC| + |CA| = 15 + 19 + 85 = 119 > 38;
    2) |CG| = 27; |BD| + |DC| + |CG| = 15 + 19 + 27 = 61, хотя вершина A еще не достигнута.

    Пути, соединяющие вершины G и A, при аналогичном рассмотрении имеют длины, большие 38.

    Следовательно, кратчайшим путем, соединяющим вершины B и A, является путь, проходящий по ребрам BD и DA. Его длина равна 38.

    Кратчайшие пути, соединяющие вершину B с другими вершинами, находятся аналогично. Здесь Вам придется потрудиться…

    С уважением.
    -----
    Пусть говорят дела

    Ответ отправил: Гордиенко Андрей Владимирович, Профессор
    Ответ отправлен: 06.01.2010, 09:52

    Оценка ответа: 5

    Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 258399 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:
  • Вам помогли? Пожалуйста, поблагодарите эксперта за это!


    Вопрос № 175845:

    Здравствуйте Уважаемые эксперты! Требуется ваша помощь

    7. Теория игр

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

    Отправлен: 05.01.2010, 15:31
    Вопрос задал: kot31, Посетитель
    Всего ответов: 1
    Страница вопроса »


    Отвечает Гаряка Асмик, Практикант :
    Здравствуйте, kot31.
    Рассмотрим игру для двух лиц с нулевой суммой. Пусть П и В – первый и второй игроки соответственно, а матрица А – платежная матрица, каждый элемент которой по абсолютной величине является выигрышем/ проигрышем, уплачиваемым игроками друг другу в соответствии с их договоренностью. Цель игроков – максимизировать выигрыш. При этом предполагается, что будет сыграно достаточно много партий, так что задача заключается в получении максимального выигрыша в среднем за партию. Каждый из игроков использует наилучшие для себя стратегии. Стратегия называется чистой, если выбор игрока неизменен от партии к партии, и смешанной, если выбор i-ой строки производится с некоторой вероятностью pi.


    -4 1 -3
    2 1 3
    -3 3 2
    3 -2 1
    -3 -4 -3

    α – нижняя цена игры
    α=max min Aij=max(-4 1 -3 -2 -4)=1
    β – верхняя цена игры
    β= min max Aij=min(3 3 3)=3

    1 ≠ 3 , значит седловой точки нет.

    Оптимальная стратегия первого игрока ищется как вероятностный вектор (pi)

    ∑pi=1 (i=1,5)
    множество смешанных стратегий второго игрока - вектор qi
    ∑qj=1 (j=1,3)

    математическое ожидание выигрыша ∑piaijqi
    2-я строка матрицы доминирует над 5 и слабо доминирует над 1. Их исключаем
    2 1 3
    -3 3 2
    3 -2 1
    v=max min ∑piaij
    Введем вспомогательную переменную u и запишем задачу нахождения максимина как ЗЛП.
    v=max u (u,p)∈B, где
    B={(u,p)|∑piaij≥u,j=1,2,3, ∑pi=1, pi≥,i=1,...5}
    Сделаем замену переменных zi=pi/u.
    Получается ЗЛП ∑zi→min
    при ограничениях ∑aijzi≥1


    0 -3 3
    2 -5 4
    -2 -1 1
    0 4 0
    -2 -4 4

    α – нижняя ц ена игры
    α=max min Aij=max(-3 -5 -2 0 -4)=0
    β – верхняя цена игры
    β= min max Aij=min(2 4 4)=2

    0 ≠ 2 , значит седловой точки нет.
    ЗЛП определяется аналогично.
    -----
    Я ни от чего, ни от кого не завишу.

    Ответ отправил: Гаряка Асмик, Практикант
    Ответ отправлен: 10.01.2010, 14:10

    Оценка ответа: 5

    Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 258529 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:
  • Вам помогли? Пожалуйста, поблагодарите эксперта за это!


    Оценить выпуск »
    Нам очень важно Ваше мнение об этом выпуске рассылки!

    Задать вопрос экспертам этой рассылки »

    Скажите "спасибо" эксперту, который помог Вам!

    Отправьте СМС-сообщение с тестом #thank НОМЕР_ОТВЕТА
    на короткий номер 1151 (Россия)

    Номер ответа и конкретный текст СМС указан внизу каждого ответа.

    Полный список номеров »

    * Стоимость одного СМС-сообщения от 7.15 руб. и зависит от оператора сотовой связи. (полный список тарифов)
    ** При ошибочном вводе номера ответа или текста #thank услуга считается оказанной, денежные средства не возвращаются.
    *** Сумма выплаты эксперту-автору ответа расчитывается из суммы перечислений на портал от биллинговой компании.


    © 2001-2010, Портал RFpro.ru, Россия
    Авторское право: ООО "Мастер-Эксперт Про"
    Автор: Калашников О.А. | Программирование: Гладенюк А.Г.
    Хостинг: Компания "Московский хостер"
    Версия системы: 2009.6.13 от 28.12.2009

    В избранное