Линейное программирование
Анализ расходов предприятия на производство новых изделий народного потребления. Применение графического метода и симплекс-метода для составления оптимальной производственной программы, обеспечивающей максимальную прибыль. Решение двойственной задачи.
| Рубрика | Экономико-математическое моделирование |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 17.02.2013 |
| Размер файла | 48,4 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Федеральное агентство по образованию
Государственное образовательное учреждение
Высшего профессионального образования
«Владимирский государственный университет»
Кафедра менеджмента
Контрольная работа
по курсу «ЭММ»
На тему: «Линейное программирование»
Выполнил:
ст. гр. ______
Принял: Преподаватель
Краев В.Н.
Владимир 2012
Содержание
Цель работы
1. Решение задачи графическим методом
2. Решение задачи симплекс-методом
3. Решение двойственной задачи
Цель работы
Изучить теоретически и применить на практике симплекс-метод для составления оптимальной производственной программы предприятия.
Предприятие готовит к выпуску два новых изделия народного потребления. Расходы по фонду заработной платы, амортизационным отчислениям и оборотным средствам (материалам) на единицу изделия, общий расход ресурсов и прибыль на одно изделие приведены в таблице.
|
Наименование ресурса |
Расход сырья на единицу изделия, у.е. |
Общий объем ресурсов, у.е. |
||
|
1 |
2 |
|||
|
Заработная плата |
2 |
1 |
90 |
|
|
Амортизация |
1 |
1 |
55 |
|
|
Материалы |
2 |
5 |
200 |
|
|
Прибыль |
20 |
15 |
Необходимо составить такой план производства, который давал бы предприятию максимальную прибыль.
1. Решение задачи графическим методом
графический симплекс производственный прибыль
Составим систему уравнений след. образом:
20х1 + 15х2 max
Каждое из ограничений задачи можно представить на графике в виде области, ограниченной осями х1 и х2 и прямой линией, соответствующей ограничению, представленному в виде равенства.
1) х1=0 x2=90
х2=0, 2x1=90, x1=45
|
Х2 |
|||||||||||||||
|
90 |
|||||||||||||||
|
Заработная плата |
|||||||||||||||
|
0 |
45 |
Х1 |
2) х1=0 x2=55
х2=0 x1=55
|
Х2 |
|||||||||||||||
|
Амортизация |
|||||||||||||||
|
55 |
|||||||||||||||
|
0 |
55 |
Х1 |
3) х1=0 5x2=200 x2=40
х2=0 2x1=200 x1=100
|
Х2 |
|||||||||||||||
|
40 |
Материалы |
||||||||||||||
|
0 |
100 |
Х1 |
Совмещая эти решения на графике, получим область допустимых решений, которая удовлетворяет всем ограничениям. Далее находим оптимальное решение путём обхода угловых точек и с помощью линий прибыли (уровня).
|
Х2 |
|||||||||||||||
|
А(0;40) |
|||||||||||||||
|
40 |
|||||||||||||||
|
В(25;25) |
|||||||||||||||
|
C(35;20) |
|||||||||||||||
|
ДF(20;15) |
|||||||||||||||
|
D(45;0) |
|||||||||||||||
|
0 |
45 |
Х1 |
F(A)=20*0+15*40=600
F(B)= 20*25+15*25=875
F(C)=20*35+15*20=1000 - максимальная прибыль
F(D)= 20*45+15*0=900
20х1+15х2=1000
Таким образом, оптимальное решение: х1 = 35; х2 = 20, при этом прибыль составляет 1000 у.е.
Проверка решения:
Подставим найденное решение х1 = 35; х2 = 20, получим:
Получаем, что:
Избыток ресурса составляет 30.
Таким образом, при оптимальном выпуске фонды заработной платы и амортизации расходуются полностью, а от фонда материалов должно остаться 30 условных единиц.
Далее проводим анализ изменения активных и пассивных ограничений и его влияние на оптимальное решение.
1. Рассмотрим увеличение ограничения по амортизации. Найдём координаты точки М:
|
Х2 |
|||||||||||||||
|
А(0;40) |
|||||||||||||||
|
40 |
|||||||||||||||
|
В(25;25) |
|||||||||||||||
|
М |
|||||||||||||||
|
C(35;20) |
|||||||||||||||
|
ДF(20;15) |
|||||||||||||||
|
D(45;0) |
|||||||||||||||
|
0 |
45 |
Х1 |
М(31,25;27,5)
Подставим их в ограничение по амортизации:
1*31,25+1*27,5=58,75 у.е.
Следовательно, количество дефицитного ресурса (фонда амортизации) можно увеличить на :
58,75-55=3,75 у.е.
Прибыль:
20*31,25+15*27,5=1037,5 у.е.
2. Рассмотрим увеличение ограничения по заработной плате:
|
Х2 |
|||||||||||||||
|
А(0;40) |
|||||||||||||||
|
40 |
|||||||||||||||
|
В(25;25) |
|||||||||||||||
|
C(35;20) |
|||||||||||||||
|
ДF(20;15) |
|||||||||||||||
|
D(45;0) |
N |
||||||||||||||
|
0 |
45 |
55 |
Х1 |
При перемещении ограничения параллельно самому себе вправо до точки N(55; 0), ограничение будет оставаться активным, но область допустимых решений будет ОАBCN, решение в точке N(55; 0).
Подставим координаты точки N в ограничение по зарплате:
2*55+1*0=110 у.е.
Следовательно, ресурсы по зарплате можно увеличить на:
110-90=20 у.е.
Прибыль:
20*55+15*0=1100 у.е.
3. Рассмотрим изменение пассивного ограничения:
|
Х2 |
|||||||||||||||
|
А(0;40) |
|||||||||||||||
|
40 |
|||||||||||||||
|
В(25;25) |
|||||||||||||||
|
C(35;20) |
|||||||||||||||
|
ДF(20;15) |
|||||||||||||||
|
D(45;0) |
|||||||||||||||
|
0 |
45 |
Х1 |
Материалы: 2х1+5х2?200
С (35; 20): 2*35+5*20=170
То есть материалы можно уменьшить до 170, при этом оптимальное решение не изменится.
Вывод:
Следовательно, оптимальное решение находится в точке С (35; 20). Прибыль в этой точке равна 1000 у.е.
Активное ограничение - амортизационные отчисления можно увеличить на 3,75 у.е. Прибыль при этом 1037,5 у.е.
Активное ограничение - фонд зарплаты можно увеличить на 20 у.е. Прибыль при этом 1100 у.е.
Пассивное ограничение - по материалам можно уменьшить до 170, решение при этом не изменится.
2. Решение задачи симплекс-методом
Для приведения системы к каноническому виду введем балансные неизвестные х3, х4, х5
Составим симплекс таблицу:
|
Базисные переменные |
Оценки переменных |
переменные |
Свободные члены |
Контрольный столбец |
|||||
|
x1 |
x2 |
x3 |
x4 |
x5 |
|||||
|
x3 |
0 |
2 |
1 |
1 |
0 |
0 |
90 |
0 |
|
|
x4 |
0 |
1 |
1 |
0 |
1 |
0 |
55 |
0 |
|
|
x5 |
0 |
2 |
5 |
0 |
0 |
1 |
200 |
0 |
|
|
F |
0 |
20 |
15 |
0 |
0 |
0 |
F |
0 |
Выбираем ведущий столбец : x1, т. к. он имеет наибольшую прибыль; выбираем ведущую строку: x3, т. к. поделив свободные члены на соответствующие коэффициенты ведущего столбца мы получаем, что наименьшее - 45 у строки x3.
|
Базисные переменные |
Оценки переменных |
переменные |
Свободные члены |
Контрольный столбец |
|||||
|
x1 |
x2 |
x3 |
x4 |
x5 |
|||||
|
х1 |
20 |
1 |
1/2 |
1/2 |
0 |
0 |
45 |
900 |
|
|
x4 |
0 |
0 |
1/2 |
-1/2 |
1 |
0 |
10 |
0 |
|
|
х5 |
0 |
0 |
4 |
-1 |
0 |
1 |
110 |
0 |
|
|
F |
0 |
0 |
5 |
-10 |
0 |
0 |
F-900 |
900 |
Контрольный столбец высчитывается как произведение свободных членов на соответствующую оценку переменных.
Окончательно получаем:
|
Базисные переменные |
Оценки переменных |
переменные |
Свободные члены |
Контрольный столбец |
|||||
|
x1 |
x2 |
x3 |
x4 |
x5 |
|||||
|
х1 |
20 |
1 |
0 |
1 |
-1 |
0 |
35 |
700 |
|
|
х2 |
15 |
0 |
1 |
-1 |
2 |
0 |
20 |
300 |
|
|
х5 |
0 |
0 |
0 |
3 |
-8 |
1 |
30 |
0 |
|
|
F |
0 |
0 |
0 |
-5 |
-10 |
0 |
F-1000 |
1000 |
Ответ: x1 = 35; x2 = 20; x3 =0; x4 = 0; x5 = 30; F=1000.
3. Решение двойственной задачи
Если прямая задача является задачей максимизации, то двойственная - минимизации.
Коэффициенты при неизвестных в целевой функции прямой задачи становятся свободными членами в ограничениях двойственной задачи.
Свободные члены из ограниченной прямой задачи становятся коэффициентами при неизвестных в целевой функции двойственной задачи.
В нашем случае получаем:
Здесь u1, u2, u3 - «цена» соответствующая 1 у.е. заработной платы, плановых амортизационных отчислений и материалов.
Решение двойственной задачи находится в строке целевой функции на последней операции симметричной таблице, т.е. u1=5; u2=10; u3=0. Это значит, что при изменении ресурсов «заработная плата» и «амортизация» на 1 у.е. прибыль изменится соответственно на 5 и 10 у.е. Нулевая оценка ресурса «материалы» свидетельствует о том, что этот ресурс недефицитный и находится в избытке.
Размещено на Allbest.ru
...Подобные документы
Решение задачи линейного программирования графическим и симплекс-методом. Решение задачи двойственной к исходной. Определение оптимального плана закрепления потребителей за поставщиками однородного груза при условии минимизации общего пробега автомобилей.
контрольная работа [398,2 K], добавлен 15.08.2012Линейное программирование как инструмент исследования линейных моделей. Основы симплекс-метода. Моделирование экономической ситуации в инструментальном цехе. Применение симплекс-метода для оптимизации плана производства. Применимость линейной модели.
курсовая работа [112,0 K], добавлен 09.12.2014Задача линейного программирования: определение количества продуктов для получения максимального дохода от реализации, расчет цены для минимальной общей стоимости затрат на производство с помощью графического и симплекс-метода. Решение транспортных задач.
курсовая работа [519,5 K], добавлен 06.05.2011Математическая теория оптимального принятия решений. Табличный симплекс-метод. Составление и решение двойственной задачи линейного программирования. Математическая модель транспортной задачи. Анализ целесообразности производства продукции на предприятии.
контрольная работа [467,8 K], добавлен 13.06.2012Построение математических моделей по определению плана выпуска изделий, обеспечивающего максимальную прибыль, с помощью графического и симплексного метода. Построение моделей по решению транспортных задач при применении метода минимальной стоимости.
задача [169,2 K], добавлен 06.01.2012Цель работы: изучить и научиться применять на практике симплекс - метод для решения прямой и двойственной задачи линейного программирования. Математическая постановка задачи линейного программирования. Общий вид задачи линейного программирования.
реферат [193,4 K], добавлен 28.12.2008Решение задачи линейного программирования графическим способом. Построение математической модели задачи с использованием симплекс-таблиц, её экономическая интерпретация. Поиск оптимального плана перевозки изделий, при котором расходы будут наименьшими.
задача [579,8 K], добавлен 11.07.2010Основы и методы математического программирования. Дифференциальные и разностные уравнения. Классические задачи исследования операций. Алгоритмы симплекса-метода. Допустимые решения при поиске оптимального решения. Линейное и нелинейное программирование.
курсовая работа [183,7 K], добавлен 20.01.2011Геометрический способ решения стандартных задач линейного программирования с двумя переменными. Универсальный метод решения канонической задачи. Основная идея симплекс-метода, реализация на примере. Табличная реализация простого симплекс-метода.
реферат [583,3 K], добавлен 15.06.2010Математическая формулировка задачи линейного программирования. Применение симплекс-метода решения задач. Геометрическая интерпретация задачи линейного программирования. Применение методов линейного программирования к экстремальным задачам экономики.
курсовая работа [106,0 K], добавлен 05.10.2014- Примеры использования графического и симплексного методов в решении задач линейного программирования
Экономико-математическая модель получения максимальной прибыли, её решение графическим методом. Алгоритм решения задачи линейного программирования симплекс-методом. Составление двойственной задачи и её графическое решение. Решение платёжной матрицы.
контрольная работа [367,5 K], добавлен 11.05.2014 Определение оптимальных объемов производства по видам изделий за плановый период и построение их математической модели, обеспечивающей максимальную прибыль предприятию. Решение задачи по минимизации затрат на перевозку товаров средствами модели MS Excel.
курсовая работа [3,4 M], добавлен 26.05.2013Задача оптимального планирования производства. Составление двойственной задачи, её решение по теоремам двойственности. Предельные вероятности состояний. Среднее время ожидания заявки в очереди. Принятие управленческих решений на основе теории игр.
контрольная работа [218,5 K], добавлен 15.05.2015Симплекс метод решения задач линейного программирования. Построение модели и решение задачи определения оптимального плана производства симплексным методом. Построение двойственной задачи. Решение задачи оптимизации в табличном процессоре MS Excel.
курсовая работа [458,6 K], добавлен 10.12.2013Пример решения задачи по оптимизации размещения побочного производства лесничества графическим методом; симплекс-методом; в стандартной форме - преобразованием неограниченных по знаку переменных. Оценка влияния различных параметров на оптимальное решение.
презентация [566,6 K], добавлен 30.10.2013Решение задач линейного программирования с применением алгоритма графического определения показателей и значений, с использованием симплекс-метода. Использование аппарата теории двойственности для экономико-математического анализа оптимального плана ЗЛП.
контрольная работа [94,6 K], добавлен 23.04.2013Построение и обоснование математической модели решения задачи по составлению оптимального графика ремонта инструмента. Использование табличного симплекс-метода, метода искусственных переменных и проверка достоверности результата. Алгоритм решения задачи.
курсовая работа [693,1 K], добавлен 04.05.2011Универсальный метод решения канонической задачи линейного программирования. Общая схема симплекс-метода, его простейшая реализация на примере. Группировка слагаемых при одинаковых небазисных переменных. Определение координат нового базисного плана.
контрольная работа [49,1 K], добавлен 21.10.2013Определение общего дохода от реализации продукции и общих транспортных издержек. Расчет теневых цен. Нахождение маршрута с наименьшей отрицательной теневой ценой. Составление плана производства двух видов продукции, обеспечивающего максимальную прибыль.
контрольная работа [161,9 K], добавлен 18.05.2015Характеристика и описание метода линейного программирования, основные области его применения и ограничения использования. Решение экономических задач, особенности формирования оптимизационной модели, расчет и анализ результатов оптимизации прибыли.
курсовая работа [99,0 K], добавлен 23.03.2010
