II. 1. Решение задачи графическим методом.

Министерство образования и науки Российской Федерации

Государственное образовательное учреждение

Высшего профессионального образования

«Владимирский государственный Университет

имени Александра Григорьевича и Николая Григорьевича Столетовых»

(ВлГУ)

Институт (факультет) «Малого и среднего бизнеса»

Кафедра менеджмента

Отчёт по контрольной работе

по курсу «ЭММ»

Вариант №20

На тему: «Линейное программирование»

Выполнила

ст.гр.МНб-210

Наврузова Д.В.

Принял

преподаватель

Краев В.Н.

г.Владимир

Содержание

I. Цель работы……………………………………………………………………..3

II. 1.Решение задачи графическим методом……………………………...4-10

2. Экономический анализ задачи с использованием графического метода…………………………………………………………………………11-14

3. Решение задачи симплекс-методом………………………………...15-17

4. Решение двойственной задачи………………………………………18-19

5. Расчет функции предельной эффективности ресурсов (теневых цен), поступающих на данное предприятие………………………………………20-25

6. Исследование предельной эффективности с помощью симплекс-метода…………………………………………………………………………..26

I. Цель работы

Необходимо изучить теоретически, применить на практике решения задачи линейного программирования на максимум прибыли геометрически и аналитически, проанализировать полученные результаты.

Условия задачи: предприятие осваивает выпуск 2-х новых изделий. Расходы по заработной плате, амортизационным отчислениям, материалам, лимиты, вы­деленные предприятию, и прибыль на одно изделие приведены ниже в таблицах.

Необходимо составить такой план производства, который давал бы предприятию максимальную прибыль.

II. 1. Решение задачи графическим методом.

Составим математическую модель задачи.

Целевая функция будет иметь вид: F(x) =10x₁+15x₂ à max

при ограничениях: 35x₁+70x₂≤ 2450

50x₁+40x₂≤ 2000 (1.1)

80x₁+35x₂≤ 2800

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

35x₁+70x₂=2450.

х₁=70 (х₂=0, 35х₁=2450, х₁=2450/35)

х₂=35 (х₁=0, 70х₂=2450, х₂=2450/70)

х₂

0 70 х₁

рис.1.1 ОДР по заработной плате

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

50x₁+40x₂=2000

х₁=40 (х₂=0, 50х₁=2000, х₁=2000/50)

х₂=50 (х₁=0, 40х₂=2000, х₂=2000/40)

х₂

0 40 х₁

рис.1.2 ОДР по амортизации

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

80x₁+35x₂=2800

х₁=35 (х₂=0, 80х₁=2800, х₁=2800/80)

х₂=80 (х₁=0, 35х₂=2800, х₂=2800/35)

х₂

0 35 х₁

рис.1.3 ОДР по материалам

Следующим шагом нужно выделить общую часть обозначенных штриховкой полуплоскостей или, другими словами, найти их пересечение. На рис. 1.4 заштрихованный многоугольник представляет собой все множество точек, координаты которых обращают в истинные утверждения все ограничения и граничные условия модели. Это означает, что область допустимых решений задачи ЛП построена.

х₂

35 А

В

С

Д

0 35 40 70 х₁

рис. 1.4 Нахождение общей ОДР задачи

Выделенному многоугольнику (рис. 1.4) области допустимых решений соответствуют шесть опорных решений – шесть угловых точек: О (0; 0); А(0; 35); В (20; 25); С(840/29; 400/29); Д (35; 0).

Координаты точки С(840/29; 400/29) можно найти, вычислив координаты точки пересечения прямых по материалам и амотризации, для чего нужно решить систему уравнений:

50x₁+40x₂=2000

80x₁+35x₂=2800

Откуда х₁=840/29, х₂=400/29

Далее подставляем координаты каждой угловой точки в целевую функцию и определяем максимальный доход:

F(А)=10× 0+15× 35=525

F(В)=10× 20+15× 25= 575

F(С)=10× 840/29+15× 400/29=14400/29=497

F(Д)=10× 35+15× 0=350

Максимальный доход будет в точке В, т.е. оптимальное решение состоит в выпуске 20 шт. изделия №1 и 25 шт. изделия №2, при этом заработная плата и амотризациия использованы полностью, выполняются ограничения по материалам и достигается максимальный доход в 575 тыс. руб.

х₂

35 А

В

С

0 20 35 Д х₁

Рис.1.5. Нахождение оптимального решения

Под линией уровня целевой функции понимается геометрическое место точек, для координат которых целевая функция имеет постоянное числовое значение (рис. 1.6).

Например, уравнение линии уровня 350 будет иметь вид: 10x₁+15₂=350 или уравнение линии уровня 525 - 10x₁+15x₂=525 (соответственно: прямая 1) и 2), рис.1.6) и т.д.

Под градиентом целевой функции понимается вектор с началом в текущей точки плоскости и координаты, которые соответствуют коэффициентам при неизвестных в целевой функции (х₁=10; х₂=15). (рис.1.6)

х₂

F(10; 15)

35 А

В

2) С

1)

0 35 Д х₁

Рис.1.6. Нахождение оптимального решения с помощью линий прибыли и вектора-градиента

Определим наиболее удаленную в направлении градиента линию уровня, имеющую общую точку с областью допустимых решений. Такой линии уровня соответствует прямая, проходящая через точку ОДР с координатами (20; 25).

Отсюда оптимальным решением задачи являются: X₁=20; X₂=25; F(x)=575 рублей.