Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Задача линейного программирования (вопрос по условию)  (Прочитано 20003 раз)
0 Пользователей и 7 Гостей смотрят эту тему.
MilanAC
Гость
« : 19-08-2009 09:06 » 

Задача 1. Для приготовления смолы необходимо составить смесь, пользуясь набором из трех компонентов: A, B, C, ресурсы которых огра-ничены соответственно 20, 25 и 10 кг в расчете на одну загрузку. При этом требуется, чтобы смесь содержала необходимое количество хими-ческих добавок D (не менее 20 г), E (не менее 2000 г), F (не менее 100 г) и при этом оказалась наиболее выгодной по себестоимости.
Следующая таблица характеризует содержание химических добавок D, E и F в одном килограмме каждого компонента и себестоимость ком-понентов A, B и C.



2. Рассмотрите модуль «Поиск решения» (Сервис  Поиск ре-шения). (При отсутствии модуля его необходимо подключить при помо-щи меню «Сервис  Надстройки».)
В окно «Установить целевую ячейку» вводится адрес целевой функции, которая стремится к какому-либо значению (в нашем случае – к минимальному). В окно «Изменяя ячейки» вводятся адреса ячеек, которые отведены под искомые значения переменных. В окно «Ограни-чения» добавляются все необходимые условия.
Обратите внимание на возможность изменения параметров поиска решений   в указанном модуле.
3. Решите в Excel при помощи модуля «Поиск решения» пред-ставленную выше задачу:


* img.jpg (63.74 Кб - загружено 5401 раз.)
* img2.jpg (84.75 Кб - загружено 6241 раз.)
« Последнее редактирование: 02-04-2010 11:33 от Sla » Записан
MilanAC
Гость
« Ответ #1 : 19-08-2009 09:08 » 

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

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #2 : 19-08-2009 09:16 » 

я называю это "от стели"
Стеля по-украински обозначает потолок или крыша
Так вот цифры взяты с потолка, для примера
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
MilanAC
Гость
« Ответ #3 : 19-08-2009 10:13 » 

Спасибо, вроде получилось ))
Можете помочь составить таблицу по аналогии, чтобы я мог дальше решить. Если конечно не трудно

Для производства двух видов изделий X и Y предприятие использует три вида сырья. Известен расход сырья каждого вида на изготовление единицы продукции вида X: 1,1; 2,3; 4,9 кг соответственно, и продукции вида Y: 0,8; 5,3; 2 кг. Общий запас сырья составляет соответственно 15; 6; 8 тонн. Прибыль от реализации продукции вида X – 180 рублей, вида Y – 110 рублей. Составить оптимальный план производства изделий, обеспечивающий максимальную прибыль.
Записан
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #4 : 20-08-2009 13:46 » 

1) Что надо максимизировать? Прибыль получается от производства x штук изделия типа X, и y штук изделия типа Y. Даны удельные прибыль для 1 штуки типа X и 1 штуки типа Y. Какое уравнение описывает общую прибыль?

2) Есть 3 вида материалов A, B, C. Даны удельные расходы материалов каждого вида на производство 1 штуки изделия каждого вида. С учётом того, что производится x штук вида X и y штук вида Y, какие 3 уравнения описывают полный расход материала каждого вида?

3) Даны лимиты по запасам материалов. Которые означают, что производство возможно при расходе материалов от 0 до указанного лимита - по каждому виду материала. Как уравнения 2) преобразовать в неравенства, описывающие возможности производства? Должен получиться многоугольник на плоскости x,y, внутри которого каждая точка пространства - это решение. И каждое решение можно оценить при помощи уравнения 1).

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

Для сокращения поиска лучше определить то направление (градиент) изменения x и y, вдоль которого прибыль (целевая функция, описываемая уравнением 1)) растёт наиболее быстро. И двигаться по пространству возможных решений в этом направлении.

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
MilanAC
Гость
« Ответ #5 : 20-08-2009 17:32 » 

Спасибо, задача решена Ага
Записан
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #6 : 21-08-2009 12:59 » 

На плоскости проводим линии, соответствующие неравенствам ограничений по ресурсам. Разрешённая зона ниже и левее линий, запрещённая зона выше и правее линий. Синий цвет - 1-й ресурс, зелёный цвет - 2-й ресурс, красный цвет - 3-й ресурс. При этом мы не должны уходить в отрицательные значения для x и y.



Как видно из рисунка, 1-й ресурс можно считать неограниченным, так как он никак не влияет на решение. Поэтому изменим масштаб и сосредоточимся на выделенной пунктиром области.



На этой плоскости нужно построить функцию цены, т.е. 3-хмерную поверхность. Будем считать, что смотрим на неё сверху. Она представляет собой плоскость с некоторым наклоном, поэтому пунктиром обозначим линии уровня (как на географической карте высоты). Высота увеличивается от нуля по направлению, перпендикулярному линиям уровня.

Становится совершенно очевидным, что в допустимой области наивысшая точка находится на пересечении ограничений 2-го и 3-го ресурсов. Если решить систему уравнений, описывающую расход ресурсов, получим точку x=1422,555; y=514,74. Поскольку решение не целое, можно взять ближайшую целую точку влево-вниз по диагонали от решения (1422; 514). Но неплохо бы проверить на допустимость точки справа и сверху от решения:  (1423; 514), (1422; 515) - в указанном порядке, поскольку прибавление единицы x выгоднее прибавления единицы y. По диагонали вправо-вверх смотреть бессмысленно - она заведомо недопустима. Дополнительные точки не удовлетворяют уравнениям. Значит решение x=1422, y=514.

* lpt1.png (4.76 Кб - загружено 4749 раз.)
* lpt2.png (6.06 Кб - загружено 4668 раз.)
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #7 : 02-04-2010 08:45 » 

Жаль Димкиных трудов, но быстрее пропадёт ссылка с "радикала" из первого поста и тему придётся удалять
Записан

Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #8 : 02-04-2010 11:00 » 

Алексей1153++, а?

так сохрани картинку и вставь в тему.
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #9 : 02-04-2010 11:34 » new

+
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #10 : 02-04-2010 15:31 » 

на работе лень было Улыбаюсь Слава опередил
Записан

Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines