Решение задачи линейного программирования симплексным методом
Составление плана выпуска продукции с целью получения максимальной прибыли при ее реализации. Вид и запас сырья, прибыль от единицы продукции и общее количество. Приведение системы ограничений к каноническому виду. Составление симплексной таблицы.
| Рубрика | Математика |
| Вид | практическая работа |
| Язык | русский |
| Дата добавления | 24.05.2009 |
| Размер файла | 12,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
3
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
Государственное образовательное учреждение
Высшего профессионального образования
«Волгоградский государственный технический университет»
Камышинский технологический институт (филиал)
Волгоградского государственного технического университета
Кафедра «Высшей математики»
Типовой расчет
Часть II
по дисциплине: «Экономико-математические методы»
на тему: «Решение задачи линейного программирования
симплексным методом»
Выполнила:
студентка гр. КБА-081(вво)
Титова Мария Дмитриевна
Проверила:
Старший преподаватель каф. ВМ
Мягкова Светлана Васильевна
Камышин - 2009 г.
Задача II
Для изготовления двух видов продукции P1 и P2 используют три вида сырья S1, S2, S3. На изготовление единицы продукции P1 используют сырье S1 = 4ед., S2 = 5ед., S3 = 4ед. На изготовление единицы продукции P2 используют сырье S1 = 3ед., S2 = 4ед., S3 = 3ед. Запасы сырья S1 составляют не более чем 320 ед., S2 не более чем 318 ед., S3 не более чем 415 ед. Прибыль от единицы продукции P1 составляет 4 рубля, от P2 составляет 5 рублей.
Необходимо составить такой план выпуска продукции, чтобы при ее реализации получить максимальную прибыль.
Решение:
Таблица данных:
|
Вид сырья |
Запас сырья, ед. |
Количество единиц продукции |
||
|
P1 |
P2 |
|||
|
S1 |
320 |
4 |
3 |
|
|
S2 |
318 |
5 |
4 |
|
|
S3 |
415 |
4 |
3 |
|
|
Прибыль от единицы продукции, руб. |
4 |
5 |
Пусть х1 - количество единиц продукции P1, а х2 - количество единиц продукции P2, тогда целевая функция: max Z=4х1+5х2
Ограничения:
4х1 + 3х2 ? 320;
5х1 + 4х2 ? 318;
4х1 + 3х2 ? 415;
х1, х2 ? 0.
Приведем систему ограничений к каноническому виду:
4х1 + 3х2 + х3 = 320;
5х1 + 4х2 + х4 = 318;
4х1 + 3х2 + х5 = 415;
хj ? 0 (j = 1,…,5)
Тогда целевая функция: max Z=4х1+5х2+0х3+0х4+0х5
Составим симплексную таблицу:
|
№ |
БП |
СБ |
В |
х1 |
х2 |
х3 |
х4 |
х5 |
И |
min И |
|
|
4 |
5 |
0 |
0 |
0 |
|||||||
|
0 |
х3 |
0 |
320 |
4 |
3 |
1 |
0 |
0 |
320/3 |
||
|
х4 |
0 |
318 |
5 |
4 |
0 |
1 |
0 |
318/4 |
318/4^ |
||
|
х5 |
0 |
415 |
4 |
3 |
0 |
0 |
1 |
415/3 |
|||
|
Zj-cj |
0 |
-4 |
-5^ |
0 |
0 |
0 |
Д0 = 320Ч0 + 318Ч0 + 415Ч0 = 0; Д1 = 4Ч0 + 5Ч0 + 4Ч0 - 4 = -4;
Д2 = 3Ч0 + 4Ч0 + 3Ч0 - 5 = -5; Д3 = Д4 = Д5 = 0.
Начальный опорный план Х = {0; 0; 320; 318; 415} не оптимальный.
Так как ¦-5¦>¦-4¦, то второй столбец - разрешающий. Минимальное симплексное отношение min И = 318/4, значит вторая строка разрешающая и а22 = 4 - разрешающий элемент.
1-ая итерация: переменная х2 записывается в столбец базисных переменных вместо х4. Элементы 2-ой строки делятся на а22 = 4, а второй столбец заполняется нулями, все другие элементы пересчитываются по правилу прямоугольника.
|
№ |
БП |
СБ |
В |
х1 |
х2 |
х3 |
х4 |
х5 |
|
|
4 |
5 |
0 |
0 |
0 |
|||||
|
1 |
х3 |
326/4 |
1/4 |
0 |
1 |
-3/4 |
0 |
||
|
х2 |
318/4 |
5/4 |
1 |
0 |
1/4 |
0 |
|||
|
х5 |
706/4 |
1/4 |
0 |
0 |
-3/4 |
1 |
|||
|
Zj-cj |
1590/4 |
9/4 |
0 |
0 |
5/4 |
0 |
После заполнения таблицы видим, что все Дj ? 0, поэтому опорный план Х* = {0; 318/4} = {0; 79,5} является оптимальным, а максимальное значение целевой функции равно max Z = 4Ч0 + 5Ч79,5 = 397,5
Из симплексной таблицы max Z = 1590/4 = 397,5, значит решение верное.
Ответ: max Z = 1590/4 = 397,5, при х1 = 0; х2 = 318/4 = 79,5
Вывод: Таким образом, чтобы получить максимальную прибыль, в размере 397,5 рублей, необходимо запланировать производство 79,5 единиц продукции P2, а производство продукции P1 экономически не целесообразно.
Подобные документы
Методы определения объемов выпуска изделий каждой модели, при которых прибыль будет максимальна Составление математической модели задачи целочисленного программирования. Решение задачи симплекс-методом. Поиск целочисленного решения методом отсечения.
контрольная работа [156,9 K], добавлен 30.01.2011Поиск базисного решения для системы уравнений, составление уравнения линии, приведение его к каноническому виду и построение кривой. Собственные значения и векторы линейного преобразования. Вычисление объема тела и вероятности наступления события.
контрольная работа [221,1 K], добавлен 12.11.2012Составление математической модели задачи. Приведение ее к стандартной транспортной задаче с балансом запасов и потребностей. Построение начального опорного плана задачи методом минимального элемента, решение методом потенциалов. Анализ результатов.
задача [58,6 K], добавлен 16.02.2016Симплекс как геометрическая фигура, являющаяся мерным обобщением треугольника. Математика и её место в жизни человека. Алгоритм решения задачи "нахождение наименьшего значения линейной функции симплексным методом". Составление начальной симплекс таблицы.
контрольная работа [484,7 K], добавлен 29.07.2013Решение системы методом Гаусса. Составление расширенной матрицу системы. Вычисление производной сложной функции, определенного и неопределенного интегралов. Область определения функции. Приведение системы линейных уравнений к треугольному виду.
контрольная работа [68,9 K], добавлен 27.04.2014Сущность понятия "симплекс-метод". Математические модели пары двойственных задач линейного программирования. Решение задачи симплексным методом: определение минимального значения целевой функции, построение первого опорного плана, матрица коэффициентов.
курсовая работа [219,4 K], добавлен 17.04.2013Численные методы поиска безусловного экстремума. Задачи безусловной минимизации. Расчет минимума функции методом покоординатного спуска. Решение задач линейного программирования графическим и симплексным методом. Работа с программой MathCAD.
курсовая работа [517,9 K], добавлен 30.04.2011Система линейных уравнений. Общее и частные решения системы линейных уравнений. Нахождение векторного произведения. Приведение уравнения кривой второго порядка к каноническому виду. Исследование функции на непрерывность. Тригонометрическая форма числа.
контрольная работа [128,9 K], добавлен 26.02.2012Графическое решение задачи линейного программирования. Общая постановка и решение двойственной задачи (как вспомогательной) М-методом, правила ее формирования из условий прямой задачи. Прямая задача в стандартной форме. Построение симплекс таблицы.
задача [165,3 K], добавлен 21.08.2010Решение систем уравнений по правилу Крамера, матричным способом, с использованием метода Гаусса. Графическое решение задачи линейного программирования. Составление математической модели закрытой транспортной задачи, решение задачи средствами Excel.
контрольная работа [551,9 K], добавлен 27.08.2009
