ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 1 Построить математическую модель задачи согласно вашему варианту

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
1. Построить математическую модель задачи согласно вашему варианту.
2. Решить задачу графическим методом.
3. Решить задачу симплекс методом.
4. Решить задачу с помощью средства MS Excel Поиск решения.
5. Сделать соответствующие выводы.
Условия задачи.
Для производства двух видов изделий А и В используется токарное, фрезерное и шлифовальное оборудование. Нормы затрат времени для каждого из типов оборудования на одно изделие данного вида приведены в табл. 1. В ней же указан общий фонд рабочего времени каждого из типов оборудования, а также прибыль от реализации одного изделия.
Таблица 1.
Тип оборудования Затраты времени (станко-часов) на обработку одного изделия Общий фонд полезного рабочего времени

А В
Фрезерное
Токарное
Шлифовальное 10
5
6 8
10
12 168
180
144
Прибыль от реализации одного изделия (руб.) 14 18

Определить план выпуска изделий вида А и В, обеспечивающий максимальную прибыль от их реализации.

Решение:
1.Строим математическую модель задачи.
Необходимо спланировать объем производства изделий вида А и В, чтобы максимизировать прибыль. Поэтому переменными являются: х1 – количество изделий А, х2 – количество изделий В.
Суммарная прибыль от производства равна
z=14*x1+18*x2.
Целью является определение среди всех допустимых значений х1 и х2 таких, которые максимизируют суммарную прибыль, т.е. целевую функцию z.
Ограничения, которые налагаются на х1 и х2:
1. объем производства изделий не могут быть отрицательным, следовательно
х1, х2 ≥0.
2. нормы затрат времени производства изделий А и В не могут превосходить максимально возможную производственную мощность, следовательно
10×1+8×2≤168,
5×1+10×2≤180,
6×1+12×2≤144.
Таким образом, математическая модель данной задачи имеет следующий вид:
максимизировать функцию

при следующих ограничениях:

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

2. Решим задачу графическим методом.
Построим область допустимых решений (она будет расположена в 1-й четверти, так как х1 и х2 ≥ 0).
Область допустимых значений – выпуклый пятиугольник ОABCD (см рис. 2.1.)
490220181610×2
00×2

51349023241000019881854403725l
00l
37973030022800018218151984375N
00N
68199020955000024091904112260С
00С
24917404055110002320290397510000206311538385750017868903676650001539240359092500124396534861500099631534671000010198103484245ОДР
00ОДР
20618453333115В
00В
21564603561080007296153336925007010403239770007105653162300006365223013111006343652939415005048252683510А
00А
4044954055745О
00О
46964603841750×1
00×1

Рис. 2.1.

Найдем оптимальное решение в допустимой области.
Построим градиент целевой функции от начала координат. Это вектор N = gradz с координатами (14, 18) (рис. 2.1.). Целью является максимума целевой функции, поэтому будем перемещать прямую, перпендикулярную вектору-градиенту, по направлению вектора – градиента от 0, до тех пор, пока она не станет опорной прямой для многоугольника ограничений.
Согласно графическому построению опорная прямая l* проходит через точку В.
212217057975500Точка В – это точка пересечения прямых 1 и 3, Поэтому ее координаты найдем из системы линейных уравнений:
10х1 + 8х2 = 168
6х1 + 12х2 = 144
х1= 12; х2= 64
Получим В (12, 6).
Найдем значение целевой функции в точке В:
ZВ = 14*12+18*6 = 276 руб.

3. Решить задачу симплекс методом
Канонический вид задачи:

10×1 + 8×2 + 1×3 + 0x4 + 0x5 = 168
5×1 + 10×2 + 0x3 + 1×4 + 0x5 = 180
6×1 + 12×2 + 0x3 + 0x4 + 1×5 = 144

Используем симплекс таблицу:
Базисные переменные Свободные члены x1 x2 x3 x4 x5 Отношение
x3 168 10 8 1 0 0 21
x4 180 5 10 0 1 0 18
x5 144 6 12 0 0 1 12
F(X1) 0 -14 -18 0 0 0 0
x3 72 6 0 1 0 -2/3 12
x4 60 0 0 0 1 -5/6 —
x2 12 1/2 1 0 0 1/12 24
F(X2) 216 -5 0 0 0 11/2 0
x1 12 1 0 1/6 0 -1/9
x4 60 0 0 0 1 -5/6
x2 6 0 1 -1/12 0 5/36
F(X3) 276 0 0 5/6 0 17/18

х1= 12х2= 6
Найдем значение целевой функции:
Z* = 276 руб.

4. Решим задачу с помощью средства MS Excel Поиск решения.
Решение задачи с помощью MS Excel
1. Отвести ячейки A3 и ВЗ под значения переменных х1 и х2 (рис. 2.2).

Рис. 2.2. Диапазоны, отведенные под переменные, целевую функцию и ограничения

2. В ячейку С4 ввести функцию цели: =14*АЗ+18*ВЗ, в ячейки А7:А9 ввести левые части ограничений:
=10*А3+8*ВЗ
=5*A3+10*B3
=6*A3+12*B3
а в ячейки В7:В9 – правые части ограничений (рис. 2.2).
3. Выбрать команду Сервис/Поиск решения (Tools/Solver) и заполнить открывшееся диалоговое окно Поиск решения (Solver) так, как показано на рис. 1.2. Средство поиска решений является одной из надстроек Excel. Если в меню Сервис (Тоо1s) отсутствует команда Поиск решения (Solver), то для ее установки необходимо выполнить команду Сервис/ Надстройки/ Поиск решения (Tools/Add-ins/Solver). Для ввода ограничений нажмите кнопку Добавить.

Рис. 2.3. Диалоговое окно Поиск решения задачи о максимизации прибыли на фабрике

4. После нажатия кнопки Выполнить (Solve) открывается окно Результаты поиска решения (Solver Results), которое сообщает, что решение найдено (рис. 2.4).

Рис. 2.4. Диалоговое окно Результаты поиска решения

5. Результаты расчета задачи представлены на рис. 2.5.

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

Вывод:
Оптимальным является производство 12 изделий вида А и 6 изделий вида В. Этот объем производства принесет 276 руб. прибыли.
1.3 ТРАНСПОРТНАЯ ЗАДАЧА
1. Построить математическую модель задачи согласно вашему варианту.
2. Решить задачу методом северо-западного угла
2. Решить задачу с помощью средства MS Exscel Поиск решения.
3. Сделать соответствующие выводы.
Условия задачи:
Решить транспортную задачу со следующими условиями (табл. 3.1):
Таблица 3.1
Пункты отправления Пункты назначения Запасы

В1
В2
В3 В4

А1
3 4 6 1 460
А2
5 1 2 3 340
A3 4 5 8 1 300
Потребности 350 200 450 100

Решение:
1. Построить математическую модель задачи согласно вашему варианту
Математическая модель транспортной задачи:
F = ∑∑cijxij, (1)
при условиях:
∑xij = ai, i = 1,2,…, m, (2)
∑xij = bj, j = 1,2,…, n, (3)
xij ≥ 0
Запишем экономико-математическую модель для нашей задачи.
Целевая функция:
F(X)= 3×11 + 4×12 + 6×13 + 1×14 +
+5×21 + 1×22 + 2×23 + 3×24 +
+4×31 + 5×32 + 8×33 + 1×34 → min
Ограничения по запасам:
x11 + x12 + x13 + x14 ≤ 460
x21 + x22 + x23 + x24 ≤ 340
x31 + x32 + x33 + x34 ≤ 300
Ограничения по потребностям:
x11 + x21 + x31 ≥ 350
x12 + x22 + x32 ≥ 200
x13 + x23 + x33 ≥ 450
x14 + x24 + x34 ≥ 100
xij ≥ 0

2. Решить задачу методом северо-западного угла

Рейтинг
( Пока оценок нет )
Понравилась статья? Поделиться с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!:

четыре × четыре =

Этот сайт использует Akismet для борьбы со спамом. Узнайте как обрабатываются ваши данные комментариев.

Adblock detector