Лабораторные работы по дисциплине "Исследование операций"

Лабораторные работы по дисциплине "Исследование операций"
Формат - Microsoft Excel.

Постановка задачи: требуется определить, в каком количестве надо
выпускать продукцию четырех типов Прод1, Прод2, Прод3, Прод4, чтобы
прибыль от производства была максимальной. Для изготовления требуются
ресурсы трех видов: трудовые, сырье, финансы. Нормы расхода, а так же
прибыль, получаемая от реализации единицы каждого типа продукции,
приведены в таблице 1.
Таблица 1 – Исходные данные к задаче
Ресурс Прод1 Прод2 Прод3 Прод4 Знак Наличие
1 Прибыль 60 70 120 130 Max —
2 Трудовые 1 1 1 1  16
3 Сырье 6 5 4 3  110
4 Финансы 4 6 10 13  100
Математическая модель задачи имеет вид:
Целевая функция: F = 60 x1 + 70 x2 + 120 x3 + 130 x4 -> max
Система ограничений
x1 + x2 + x3 + x4  16
6 x1 + 5 x2 + 4 x3 + 3 x4  110
4 x1 + 6 x2 + 10 x3 + 13 x4  100
Граничные условия : x1  0, x2  0, x3  0, x4  0
х1, х2, х3, х4 – управляемые переменные (количество продукции каждого
вида).
Ввод условий задачи состоит из следующих основных шагов:
1. Создание формы для ввода условий задачи.
2. Ввод исходных данных.
3. Ввод зависимостей из математической модели.
4. Назначение целевой функции.
5. Ввод ограничений и граничных условий.
Ввод данных для решения задачи линейного программирования:
1. Сделать форму для ввода условий задачи (рисунок 1).
Весь текст на рисунке 1 и в дальнейшем является комментарием и на
решение задачи не влияет.
Рисунок 1 – Форма для ввода условий задачи
2. Ввести исходные данные в форму (рисунок 2).
Рисунок 2 – Исходные данные на форме ввода
3. Ввести зависимости из математической модели.
Для наглядности (но не обязательно) можно перейти к режиму
представления формул. При этом ввод данных приводится на рисунке 3, а
режим представления формул - на рисунке 4.
Рисунок 3 – Форма ввода зависимости из математической модели
Рисунок 4 – Форма ввода зависимости из математической модели в режиме
представления формул
Последовательность действий для ввода зависимости для целевой
функции:
 Курсор в ячейку F6;
 Курсор на кнопку Мастер функций;
На экране диалоговое окно Мастер функций шаг 1 из 2 (рисунок 5).
 Курсор в окно Категория на категорию Математические;
 Курсор в окно Имя функции на СУММПРОИЗВ;
На экране: диалоговое окно (рисунок 6).
Рисунок 5 – Форма диалогового окна Мастер функций (шаг 1)
Рисунок 6 – Форма диалогового окна Мастер функций (шаг 2)
 В массив 1 ввести B$3:E$3;
Заметим, что во все диалоговые окна адреса ячеек удобно вводить не с
клавиатуры а, протаскивая мышь по ячейкам, чьи адреса следует ввести.
 В массив 2 ввести В6:Е6;
В ячейке F6 введены значения целевой функции (рисунок 3, 4).
Последовательность действий для ввода зависимости для левых частей
ограничений:
 Курсор в ячейку F6, копировать в буфер обмена;
 Курсор в ячейку F9, вставить из буфера обмена.
В ячейке F9 введена функция, как это показано на рисунке 4.
 Скопировать содержимое ячейки F9 в ячейки F10:F11.
На этом ввод данных в таблицы закончен.
4. Назначение целевой функции.
Последовательность действий для назначения целевой функции:
 Вызвать меню: Сервис, Поиск решения... (на экране диалоговое
окно Поиск решения, представленное на рисунке 7).
Назначить целевую функцию:
 Курсор в окно Установить целевую ячейку;
 Ввести адрес: F6;
 Ввести направление целевой функции: Максимальному значению.
Ввести адреса искомых переменных:
 Курсор в поле Изменяя ячейки;
 Ввести адреса ячеек В3: Е3;
Рисунок 7 – Диалоговое окно Поиск решения
6. Ввод ограничений и граничных условий.
В диалоговом окне Поиск решения для ввода ограничений нажать кнопку
Добавить. На экране: диалоговое окно Добавить ограничение (рисунок 8).
Рисунок 8 – Диалоговое окно Добавить ограничение
Последовательность действий для добавления граничных условий на
переменные (Прод1 - Прод4)  0, т.е. B3  B4 , C3  C4 , D3  D4 , E3  E4.
 В окне Ссылка на ячейку ввести B3;
 Курсор на стрелку (на экране отражаются знаки для ввода в
ограничения), курсор на знак >=;
 Курсор в правое окно, ввести В4, Добавить...
На экране опять диалоговое окно Добавить ограничение. Аналогично
ввести граничные условия для остальных переменных и ограничения по
ресурсам: F9  H9, F10  H10, F11  H11.
 После ввода последнего ограничения вместо Добавить... ввести ОК.
На экране: диалоговое окно Поиск решения с введенными условиями.
Если при вводе зависимостей задачи возникает необходимость в
изменении или удалении внесенных ограничений или граничных условий, то
это делается с помощью команд Изменить..., Удалить.
На этом ввод условий задачи заканчивается.
Решение задачи производится сразу же после ввода данных, когда на
экране находится диалоговое окно Параметры поиска решения (рисунок 9).
Рисунок 9 – Диалоговое окно Параметры поиска решения
С помощью команд, находящихся в этом диалоговом окне, можно
вводить условия для решения задач оптимизации всех классов.
1. Максимальное время
Служит для назначения времени в секундах, выделяемого на поиск
решения зачади. В поле можно ввести время  32767. Значение 100,
используемое по умолчанию, подходит для решения большинства задач.
2. Предельное число итераций
Служит для назначения числа итераций. Используемое по умолчанию
значение 100 подходит для решения большинства задач.
3. Линейная модель
Служит для назначения способа решения задачи: необходимо установить
флажок Линейная модель, что обеспечивает применение Симплекс - метода.
На экране: диалоговое окно Поиск решения (рисунок 7). Нажать
Выполнить.
На экране: диалоговое окно Результаты поиска решения. Решение
найдено (рисунок 10) и результат оптимального решения задачи приведен в
таблице (рисунок 11).
Рисунок 10 – Диалоговое окно Результаты поиска решения
Рисунок 11 – Результат решения задачи
На рисунке 11 видно, что в оптимальный план включена продукция в
следующем размере: Прод1 (ячейка В3) – 10, Прод2 (ячейка С3) – 0, Прод3
(ячейка D3) – 6, Прод4 (ячейка Е3) – 0.
При этом максимальная прибыль будет составлять 1320 ден.ед. (ячейка
F6), а количество использованных трудовых ресурсов равно 16 (ячейка F9),
сырья – 84 (ячейка F10) и финансов – 100 (ячейка F11).
Для наглядного представления полученного результата постройте
гистограмму, как это показано на рисунке 13. Исходными значениями для
построения гистограммы являются результаты решения задачи оптимизации
(рисунок 12).
Рисунок 12 – Исходные данные для построения гистограммы
Оптимальный план
10
0
6
0
0
2
4
6
8
10
прод1 прод2 прод3 прод4
прод1
прод2
прод3
прод4
Рисунок 13 – Графическое представление оптимального плана выпуска
продукции
Дополнительное задание.
Решить задачу линейного программирования. Решение задачи
представить графически.
Целевая функция: 43 x1 + 43 x2 + 43 x3 + 43 x4 + 43 x5 -> max
Система ограничений:
0,26 x1 + 0,25 x2 + 0,27 x3 + 0,29 x4 + 0,31 x5 ≤ 30
1,2 x1 + 1,4 x2 + 1,3 x3 + 1,6 x4 + 1,1 x5 ≤ 150
2,4 x1 + 2,5 x2 + 2,3 x3 + 2,4 x4 + 2,3 x5 ≤ 220
0,25 x1 + 0,24 x2 + 0,25 x3 + 0,26 x4 + 0,23 x5 ≤ 22
Граничные условия
xi  0, i=1,2,3,4,5.

Порядок выполнения лабораторной работы.
Постановка задачи распределения ресурсов: имеется М видов ресурсов
(i=1,2,3…M), из которых производят N (j=1,2,3…N) видов продукции.
Известны нормы расхода i – го ресурса на j-е изделие – a(i,j), запас ресурса –
b(i), затраты денежных средств на производство изделия s(j), отпускная цена
изделия – с(j). Требуется составить такой план выпуска изделий, который даст
максимум критерия эффективности.
Таблица 2 – Исходные данные к задаче
Ресурс
Изделие
1 2 … М Цена
cj
Затраты
sj
План
выпуска
1 a11 a21 …. am1 c1 s1 x1
2 a21 a22 …. am2 c2 s2 x2
…. …. ….. …. …. ….. ….. …..
N a1n a2n ….. amn cn sn xn
Запас
ресурса b(i)
b1 b2 …. bm
Математическая модель: критерий эффективности – максимум прибыли,
ограничения по запасам ресурса, граничные условия – неотрицательность
управляемых переменных.
Целевая функция: W (c s ) x max
n
j 1
j j j    

Система ограничений: a x bi i 1, ... ,m
n
j 1
j ij    

Граничные условия: xj  0, j=1,…, n
Изделия четырех типов проходят последовательную обработку на двух
станках. Время обработки одного изделия каждого типа на каждом из станков
приведено в таблице 3.
Таблица 3 – Исходные данные задачи распределения ресурсов
Станок Время обработки изделий, ч
Тип 1 Тип 2 Тип 3 Тип 4
1 2 3 4 2
2 3 2 1 2
Стоимость машино-часа составляет 10$ для станка 1 и 8$ для станка 2.
Допустимое время использования станков для обработки изделий всех типов
ограничено следующими значениями: 500 машино-часов – для станка 1 и 380
машино-часов для станка 2. Цены изделий типов 1, 2, 3 и 4 равны 65$, 70$, 55$
и 45$ соответственно. Сформулируйте для приведенных условий задачу
максимизации чистой прибыли и решите ее.
Таблица 4 – Преобразование исходных данных
Ресурс
Изделие
Станок1 Станок 2 Цена
cj
Затраты
sj
План
выпуска
1 2 3 65 10·2+8·3=44 x1
2 3 2 70 10·3+8·2=46 x2
3 4 1 55 10·4+8·1=48 x3
4 2 2 45 10·2+8·2=36 x4
Запас
ресурса b(i)
500 380
Математическая модель задачи имеет следующий вид:
Целевая функция:
W 21 x 24 x 7 x 9 x max
W (65 44) x (70 46) x (55 48) x (45 36) x max
1 2 3 4
1 2 3 4
        
            

Система ограничений:
  
       
       
3 x 2 x 1 x 2 x 380
2 x 3 x 4 x 2 x 500
1 2 3 4
1 2 3 4
Граничные условия:
xj  0, j=1,2,3,4
Предприятие выпускает «неделимую» продукцию, поэтому необходимо
ввести дополнительные ограничения:
xjцелое , j=1,2,3,4
Задачи оптимизации, в результате решения которых искомые переменные
должны быть целыми числами, называются задачами целочисленного
программирования. Задачи целочисленного программирования решаются
аналогично задачам линейного программирования. Основное отличие
заключается в требовании целочисленности.
Решение задач распределения ресурсов средствами Excel проводится
аналогично задачи, рассмотренной в предыдущей лабораторной работе.
1. Разработать форму для ввода условий задачи и ввести исходные
данные.
2. Вызвать меню Сервис, Поиск решения... На экране: диалоговое
окно Поиск решения (рисунок 6).
3. Ввести:
 условия, которые были введены для задачи линейного
программирования;
 требования целочисленности с использованием диалогового окна
Добавить ограничение:
a) Курсор в окно Ссылка на ячейку, ввести адрес ячейки
В3;
b) Курсор на стрелку, ввести целое;
c) Повторить ввод требований целочисленности для всех
целочисленных переменных
На рисунке 14 представлена форма для решения задачи с введенными в
нее исходными данными.
Рисунок 14 – Форма исходных данных
Результаты поиска решения приведены на рисунке 15:
x1= 28 ед.
x2= 148 ед.
x3= 0 ед.
x4= 0 ед.
Целевая функция:
W= 4140 $
Рисунок 15 – Результаты решения задачи распределения ресурсов
Вывод: для получения максимальной прибыли, равной 4140 $,
предприятию необходимо выпустить изделий типа 1- 28 шт., изделий типа 2 –
148 шт., изделия типа 3 и 4 в оптимальный план не входят. При этом
фактическое время использования 1 и 2 станка для обработки изделий всех
типов 500 машино-часов и 380 машино-часов соответственно.
Дополнительное задание.
1. Решить задачу распределения ресурсов.
Завод выпускает два вида деталей (А и Б), обработка которых
осуществляется на токарных и фрезерных станках. На месяц заводу выделено N
тонн металла. Его расход на изготовление детали А - a1 тонн, Б - a2 тонн. На
изготовление детали А требуется t11 ч работы токарного и t21 ч работы
фрезерного станков, а детали Б - t12 и t22 ч соответственно. Всего на заводе r1
токарных станков и r2 фрезерных станка, работающих в две смены (т.е.
месячный календарный фонд рабочего времени каждого станка составляет 300
ч). При реализации единицы каждого вида деталей прибыль составляет с1 и с2
соответственно. Необходимо составить план выпуска продукции, который бы
обеспечивал получение максимальной прибыли при реализации всей
выпущенной продукции.
Варианты заданий и числовые значения параметров задачи для каждого
варианта приведены в таблице 5.

Вариант N a1 a2 t11 t21 t12 t22 r1 r2 c1 c2
1 30 0,10 0,13 3 4 3,7 3,8 3 4 6,0 8,0

2. Составить и решить задачу распределения ресурсов (количество
изделий – не менее 3, количество видов используемых ресурсов не менее 4).

Подготовительные работы:
 cоставить на бумаге таблицу вариантов;
Вариант 1 2 3 4 5
Финансы 50 100 150 200 250
 вызвать на экран таблицу с результатом решения задачи
 удалите результат решения, находящийся в ячейках B3:E3.
Решение задачи для 1-го варианта:
 ввести в ячейку H11 значение 50;
 вызвать меню Сервис, Поиск решения..., Выполнить;
На экране: диалоговое окно Результаты поиска решения.
 выполнить команду Сохранить сценарий... Ввести имя сценария
финансы = 50 (рисунок 16);
Рисунок 16 – Окно сохранения сценария
На экране: результат решения для данного варианта (рисунок 17).
Рисунок 17 – Результат решения для первого варианта
Решение задачи для последующих вариантов:
 ввести в ячейку H11 значение финансов для следующего варианта.
 выполнить описанные ранее действия, при этом при сохранении
сценария вводить имя сценария, соответствующее значению финансов.
Представление результатов решения:
 вызвать меню Сервис, Сценарии. На экране: диалоговое окно
Диспетчер сценариев;
 сформировать Отчет. На экране: диалоговое окно Отчет по
сценарию;
 определить вид отчета Структура. На экране: отчет Структура
сценария.
Примечание:
Сравните данные из структуры сценария со значениями, приведенными на рисунке 16. Если числовые
значения не совпадают, выполните следующие действия:
- удалите лист Структура сценария
- перейдите на лист с решением задачи
- вызовите меню Сервис, Сценарии…
- курсор на сценарий Финансы=50, Изменить…
На экране: диалоговое окно Изменение сценария и далее диалоговое окно Значения ячеек сценария
- для каждой ячейки установите разделитель между целой и дробной частью числа «,». (Например,
исправьте 12.5 на 12,5)
- сделайте исправления в каждом сценарии и попробуйте снова создать отчет по сценарию.
Для удобства дальнейшей работы выполните редактирование Итогового
сценария (рисунок 18).
Рисунок 18 – Итоговый сценарий
Для наглядного представления результатов параметрического анализа
на основании отредактированной таблицы используйте их графическое
представление.
1. Для построения первой гистограммы используйте диапазон ячеек
С3:I8 (результат представлен на рисунке 19).
Номенклуатура выпуска
12,5
10
1,67
0 0 0 0 0 0 0 0
6
14,33
2,67
0 0 0 0
13,33
16
0
2
4
6
8
10
12
14
16
18
Финансы = 50 Финансы = 100 Финансы = 150 Финансы = 200 Финансы = 250
Прод1
Прод2
Прод3
Прод4
Рисунок 19 – Зависимость номенклатуры выпускаемых изделий от
финансирования
Вывод:
 При различном финансировании в план входит продукция
различных видов, однако, ни в один вариант не входит выпуск Прод2. Это
объясняется тем, что при высоком потреблении ресурсов, прибыль от
производства Прод2 ниже, чем от производства других видов продукции.
 Для значений финансов 50, 150, 200 величина выпускаемой
продукции является дробной. Такое положение допустимо при планировании
выпуска ткани, добычи нефти и т.д.
2. Для построения второй нестандартной диаграммы (тип: график
(гистограмма 2)) используйте диапазон ячеек С3:I3, С9:I9, С11:I11 (результат
представлен на рисунке 20).
750
1320
1820
2053,33 2080
75
84
67,33
50,67
48
0
500
1000
1500
2000
2500
Финансы = 50 Финансы = 100 Финансы = 150 Финансы = 200 Финансы = 250
0
10
20
30
40
50
60
70
80
90
Прибыль
Сырье
Рисунок 20 – Зависимость между показателями прибыли, использования сырья
и финансированием
Вывод:
 Увеличение финансирования дает увеличение прибыли.
 При увеличении финансирования, начиная со 150, происходит
уменьшение потребляемого сырья, т.к. выпуск Прод3, Прод4, обеспечивающих
увеличение прибыли, требует меньшего потребления сырья.
Выполнение сравнительного вариантного анализа.
1 постановка задачи.
Критерий эффективности – максимум прибыли.
Целевая функция:
F = 60·x1+70·x2+120·x3+130·x4 -> max
Система ограничений:
x1 + x2 + x3 + x4  16
6·x1 + 5·x2 + 4·x3 + 3·x4  110
4·x1 + 6·x2 + 10·x3 + 13·x4  100
Решение задачи:
 ввести условие задачи и целевую функцию в таблицу для ввода
условий;
 назначить целевую функцию, ввести ограничения и граничные
условия;
 решить задачу (результат представлен на рисунке 21);
 сохранить сценарий. Ввести имя сценария МАКС ПРИБ.
Рисунок 21 – Результат решения первой постановки задачи
2 постановка задачи.
Критерий эффективности – максимум продукции в натуральном
выражении.
Целевая функция:
F = x1 + x2+ x3 + x4 -> max
Система ограничений:
x1 + x2 + x3 + x4  16
6·x1 + 5·x2 + 4·x3 + 3·x4  110
4·x1 + 6·x2 + 10·x3 + 13·x4  100
Решение задачи:
 ввести условие задачи и целевую функцию в таблицу для ввода
условий;
 назначить целевую функцию, ввести ограничения и граничные
условия;
 решить задачу (результат представлен на рисунке 22);
 сохранить сценарий. Ввести имя МАКС ПРОД.
Рисунок 22 – Результат решения второй постановки задачи
3 постановка задачи.
Критерий эффективности – максимальное использование имеющихся
ресурсов
Целевая функция:
F = x1 + x2 + x3 + x4 + 6·x1 + 5·x2 + 4·x3 + 3·x4 + 4·x1 + 6·x2 + 10·x3 + 13·x4 -> max
Система ограничений:
x1 + x2 + x3 + x4  16
6·x1 + 5·x2 + 4·x3 + 3·x4  110
4·x1 + 6·x2 + 10·x3 + 13·x4  100
Решение задачи:
 ввести условие задачи в таблицу для ввода условий;
 ввести зависимости для целевой функции: курсор в ячейку F6,
ввести =F9+F10+F11
 назначить целевую функцию, ввести ограничения и граничные
условия;
 решить задачу (результат представлен на рисунке 23);
 сохранить сценарий. Ввести имя МАКС РЕСУРС.
Рисунок 23 – Результат решения третьей постановки задачи
Представление результатов решения:
 вызвать меню Сервис, Сценарии. На экране: диалоговое окно
Диспетчер сценариев;
 сформировать Отчет. На экране: диалоговое окно Отчет по
сценарию;
 определить вид отчета Структура. На экране: отчет Структура
сценария. Выполните редактирование структуры сценария (результат - рисунок
24).
Рисунок 24 – Структура сценария
Выполнение анализа внутренней структуры.
Порядок выполнения анализа:
1. Откройте файл, созданный при выполнении лабораторной работы
«Решение задач линейного программирования средствами ЭТ Excel»
2. Перейдите на лист с решением задачи 1. Установите начальные
значения в ячейки исходных данных.
3. Вызовите меню Сервис, Поиск решения…, Выполнить.
4. Создайте отчет по результатам, отчет по устойчивости, отчет по
пределам.

Дополнительное задание.
Выполните экономико-математический анализ оптимального решения
задачи распределения ресурсов, составленной вами (анализ вариантный и
анализ внутренней структуры).

Постановка задачи оптимальной загрузки оборудования.
Вариант 1: имеется М (i=1,M) групп взаимозаменяемого оборудования, на
которых выполняется N (j=1,N) видов работ. Известна производительность
оборудования a(i,j) (ед/час), ресурс времени работы оборудования b(i), затраты
денежных средств на выполнение работ по группам оборудования s(i,j),
стоимость произведенных работ c(j). Предприятию задан план по каждому виду
работ P(j). Требуется составить такой план производства работ (т.е. так
распределить выполнение работ между оборудованием), при котором прибыль
будет максимальной.
Представим исходные данные в табличной форме.
Таблица 6 – Табличная форма представления исходных данных
Виды работ 1 2 … N Ресурс
времени
Оборудование
1 a(1,1)
x(1,1)
s(1,1)
a(1,2)
x(1,2)
s(1,2)
a(1,j)
x(1,j)
s(1,j)
a(1,N)
x(1,N)
s(1,N)
b(1)
2 a(2,1)
x(2,1)
s(2,1)
a(2,2)
x(2,2)
s(2,2)
a(2,j)
x(2,j)
s(2,j)
a(2,N)
x(2,N)
s(2,N)
b(2)
Продолжение таблицы 6
… a(i,1)
x(i,1)
s(i,1)
a(i,2)
x(i,2)
s(i,2)
a(i,j)
x(i,j)
s(i,j)
a(i,N)
x(i,N)
s(i,N)
b(i)
М a(M,1)
x(M,1)
s(M,1)
a(M,2)
x(M,2)
s(M,2)
a(M,j)
x(M,j)
s(M,j)
a(M,N)
x(M,N)
s(M,N)
b(M)
План P(1) P(2) P(j) P(N)
Стоимость
работ
с(1) с(2) с(j) с(N)
Обозначим x(i,j) – время, в течение которого i-ое оборудование
выполняет j-ый вид работ.
Математическая модель задачи оптимальной загрузки оборудования:
Целевая функция: W (c( j) s(i, j))x(i, j) max
N
j 1
M
i 1
   
 
при ограничениях по запасам ресурса:
x(1,1) + x(1,2)+ …. + x(1,N)  b(1)
x(2,1) + x(2,2)+ …. + x(2,N)  b(2)
………………………………………
x(M,1) + x(M,2)+ …. + x(M,N)  b(M)
при ограничениях по плану:
a(1,1) ·x(1,1) + a(2,1) ·x(2,1)+ …. + a(M,1) ·x(M,1) = P(1)
a(1,2) ·x(1,2) + a(2,2) ·x(2,2)+ …. + a(M,2) ·x(M,2) = P(2)
……………………………………………………………
a(1,N) ·x(1,N) + a(2,N) ·x(2,N)+ …. + a(M,N) ·x(M,N) = P(N)
Граничные условия: x(i,j)  0
Вариант 2: имеется М (i=1,M) групп взаимозаменяемого оборудования, на
которых выполняется N (j=1,N) видов работ. Известен расход времени на
производство j – го вида работ i – м оборудованием a(i,j), ресурс времени
работы оборудования b(i), затраты денежных средств на выполнение работ по
группам оборудования s(i,j). Предприятию задан план по каждому виду работ
P(j). Требуется составить такой план производства работ (т.е. так распределить
выполнение работ между оборудованием), при котором суммарные затраты на
выполнение работ будут минимальными.
Обозначим x(i,j)  количество работ j – го вида выполненного на i
оборудовании.
Математическая модель задачи оптимальной загрузки оборудования:
Целевая функция: W s(i, j)x(i, j) min
N
j 1
M
i 1


при ограничениях по плану:
x(1,1) + x(2,1)+ …. + x(M,1) = P(1)
x(1,2) + x(2,2)+ …. + x(M,2) = P(2)
………………………………………
x(1,N) + x(2,N)+ …. + x(M,N) = P(N)
при ограничениях по запасу ресурса (времени):
a(1,1) ·x(1,1) + a(1,2) ·x(1,2)+ …. + a(1,N) ·x(1,N)  b(1)
a(2,1) ·x(2,1) + a(2,2) ·x(2,2)+ …. + a(2,N) ·x(2,N)  b(2)
………………………………………………………
a(M,1) ·x(M,1) + a(M,2) ·x(M,2)+ …. + a(M,N) ·x(M,N) =  b(M)
Граничные условия: x(i,j)  0
Числовой пример.
Постановка задачи: на двух станках I и II производится два вида
продукции А1 и А2. Для изготовления единицы продукции А1 станок I должен
работать 2 ч, станок II - 1 ч. Для изготовления единицы продукции А2 станок I
должен работать 1 ч, станок II - 2 ч. В течение суток станок I может работать по
выпуску продукции А1 и А2 не более 10 ч, станок II не более 8 ч. Требуется
спланировать работу станков по выпуску продукции А1 и А2, так чтобы
обеспечить наибольшую прибыль, если от реализации единицы продукции А1
получают 5 д.е., а от реализации единицы продукции А2 - 2 д.е., но за каждый
час простоя станка I предприятие несет 2 д.е. убытка, а станка II - 1 д.е.
Таблица 7 – Исходные данные к задаче
Продукция А1 А2 Убыток Ресурс
времени
Станки
I a(1,1)=2 x(1,1)
a(1,2)=1 x(1,2)
2 10
II a(2,1)=1 x(2,1)
a(2,2)=2 x(2,2)
1 8
Прибыль 5 2
Математическая модель задачи оптимальной загрузки взаимозаменяемого
оборудования:
X(i,j) – управляемые переменные, количество j-ой продукции,
изготовленной на i-ом станке.
Целевая функция:
W = [Прибыль] – [Убыток]  max
W = [5·x(1,1) + 5·x(2,1)+ 2·x(1,2) + 2·x(2,2)] – [2· ( 10 – x(1,1) - x(1,2)) + (8 –
x(2,1) - x(2,2))]  max
W= 7·x(1,1) + 4·x(1,2) + 6·x(2,1) + 3·x(2,2) – 28  max
Ограничение по запасу ресурса
2·x(1,1) + 1·x(1,2)  10
1·x(2,1) + 2·x(2,2)  8
Граничные условия: x(i,j)  0
Решение задачи загрузки оборудования проводится в соответствии с
алгоритмом, рассмотренном в первой лабораторной работе.
Замечание: если в ходе решения задачи появляется сообщение «Поиск не
может найти подходящего решения», следует заменить ограничения по плану
на менее жесткие (вместо знака «=» поставить «») или увеличить запасы
ресурса.
На рисунке 25 представлена форма для решения задачи с введенными в
нее исходными данными.
Рисунок 25 – Форма исходных данных
Результаты поиска решения приведены на рисунке 26.
Рисунок 26 – Результаты решения задачи
Ответ: значения управляемых переменных x(1,1)=0, x(1,2)=10, x(2,1)=8,
x(2,2)=0. При этом значение целевой функции W = 60.
Вывод: чтобы получить наибольшую прибыль, необходимо производить:
 на станке I продукцию А2  10 единиц;
 на станке II продукцию А1  8 единиц.
Прибыль составит 60 д.е. Ресурсы (суточное время работы станков)
израсходуются полностью.
Дополнительное задание.
Составить и решить задачу оптимальной загрузки взаимозаменяемого
оборудования (количество изделий – не менее 4, количество видов
оборудования – не менее 3).

Постановка транспортной задачи: некоторый однородный продукт,
сосредоточенный у М поставщиков в количестве ai (i = 1,…,M) единиц
соответственно, необходимо доставить N потребителям в количестве bj
(j=1,…,N). Известна стоимость Сij перевозки единицы груза от i–го поставщика
к j–ому потребителю. Необходимо составить план перевозок, позволяющий
вывезти все грузы, полностью удовлетворить потребности и имеющий
минимальную стоимость.
Математическая модель:
Xij – управляемые переменные, количество единиц груза.
Целевая функция:  
 
  
N
i 1
M
j 1
W Cij Xij min
Система ограничений:
 все грузы вывезены X ai i 1,N
M
j 1
ij   

 все потребности удовлетворены 

 
N
i 1
Xij b j j 1,M.
Граничные условия Xij  0.
Прежде чем решать транспортную задачу, необходимо сначала
определить, к какому типу она принадлежит.
Типы моделей:
1. Модель закрытая:  
 

M
j 1
j
N
i 1
ai b
2. Модель открытая:
 суммарные запасы превышают суммарные потребности:  
 

M
j 1
j
N
i 1
a i b .
Для преобразования открытой модели данного вида к закрытой
необходимо ввести фиктивного потребителя, потребности которого равны:
 
 
 
M
j 1
j
N
i 1
i
b* a b
 суммарные потребности превышают суммарные запасы:  
 

M
j 1
j
N
i 1
a i b .
Для преобразования открытой модели данного вида к закрытой
необходимо ввести фиктивного поставщика, объем производства которого
равен:  
 
 
N
i 1
i
M
j 1
j
a* b a
3. При решении транспортной задачи можно встретить случаи, когда
необходимо применить метод блокирования клеток. Обычно вместо стоимости
перевозки в блокируемой клетке таблицы исходных данных ставят знак , и
переменную, соответствующую данной клетке не включают в ограничения.
Рассмотрим несколько примеров.
Пример 1: суммарный объем потребностей больше суммарного объема
производства. Потребности некоторых потребителей обязательно должны быть
удовлетворены полностью.
Решение:
 ввести фиктивного поставщика;
 стоимость перевозки от фиктивного поставщика к потребителям,
потребности которых следует удовлетворить, установить значительно
большими любой из стоимости перевозок решаемой задачи или заблокировать
эти клетки.
Пример 2: суммарный объем производства больше суммарного объема
потребностей. От некоторых поставщиков нужно вывести всю продукцию.
Решение:
 ввести фиктивного потребителя;
 стоимость перевозки от поставщика к фиктивному потребителю,
установить значительно большими любой из стоимости перевозок решаемой
задачи или заблокировать эти клетки.
Пример 3: груз от поставщика, по каким – то причинам не может быть
направлен одному из потребителей.
Решение: заблокировать клетки.
Частным случаем транспортной задачи является задача оптимального
назначения.
Постановка задачи: пусть, имеются М лиц ai (i=1,…,M), которые могут
выполнять bj (j=1,…,M) видов различных работ. Известна производительность
i–го лица при выполнении j–ой работы Сij. Необходимо определить, кого и на
какую работу следует назначить, что бы добиться максимальной суммарной
производительности при условии, что каждое лицо может быть назначено
только на одну работу.
Математическая модель:
Xij – управляемые переменные, назначение i–го лица на j-ую работу.
Xij принимает значение “0” или “1”. (“0” – не назначен; “1” – назначен).
Целевая функция:  
 
  
M
j 1
M
i 1
W Cij Xij MAX .
Система ограничений:
 
 







M
j 1
M
i 1
Xij 1
Xij 1
Граничные условия Xij 0
Составить план перевозки песка из пунктов отправления: песчаный
карьер №1, железнодорожная товарная станция, речной грузовой порт,
песчаный карьер №2, в пункты назначения ЖБИ №1, ЖБИ №2, ДСК, при
котором затраты на перевозку будут минимальными. Затраты на перевозку 1 т
песка между пунктами отправления и назначения указаны в таблице исходных
данных в км. Потребности ДСК должны быть удовлетворены полностью.
Таблица 8 – Таблица исходных данных
Поставщик Потребитель Запас
ЖБИ №1 ЖБИ №2 ДСК
Песчаный карьер №1 11 x11 15 x12 7 x13 120
Ж/д станция 12 x21 16 x22 14 x23 200
Речной порт 13 x31 10 x32 9 x33 80
Песчаный карьер №1 14 x41 9 x42 11 x43 100
Фиктивный поставщик 0 x51 0 x52 50
Заявки 160 170 220
Определим тип модели: 500, 550
3
1
4
1
   
 j
j
i
i a b
Следовательно, модель открытого типа. Для решения задачи необходимо
ввести фиктивного поставщика, а также учесть, что потребности ДСК должны
быть удовлетворены полностью, запретив перевозку Фиктивный поставщик –
ДСК.
Целевая функция:
W = 11·X11+15·X12+ 17·X13+ 12·X21+ 16·X22+ 14·X23+ 13·X31 +10·X32 +
+9·X33+ 14·X41+ 9·X42 + 11·X43 + 0·X51 + 0·X52  max
Система ограничений:
 все потребности удовлетворены
x11+x21+x31+x41+x51=160
x12+x22+x32+x42+x52=170
x13+x23+x33+x43 =220
 все запасы вывезены
x11+x12+x13=120
x21+x22+x23=200
x31+x32+x33=80
x41+x42+x43=100
x51+x52 =50
Граничные условия Xij 0
Решение транспортной задачи и задачи о назначении проводится по
алгоритму, описанному в лабораторной работе «Решение задач линейного
программирования средствами ЭТ Excel».
На рисунке 27 представлена форма для решения задачи с введенными в
нее исходными данными. Результаты поиска решения приведены на рисунке
28.
Рисунок 27 – Форма исходных данных
Рисунок 28 – Результаты решения задачи
Ответ:
x11= 110 x12=0 x13=0
x21= 40 x22=0 x23=160
x31= 0 x32=20 x33=60
x41= 0 x42=100 x43=0
x51= 0 x52=50
Целевая функция: W=5680
Вывод:
Затраты на перевозку будут минимальными и составят 5680 тг, если
перевезти по маршруту:
Песчаный карьера №1 - ЖБИ №1 110 т песка
Ж/д станция - ЖБИ №1 40 т песка
Ж/д станция - ДСК 160 т песка
Речной порт - ЖБИ №2 20 т песка
Речной порт - ДСК 60 т песка
Песчаный карьер №2 - ЖБИ №2 100 т песка
Потребности ДСК и ЖБИ №1 удовлетворены полностью, для ЖБИ №2
недопоставка составит 50 т песка.
Дополнительное задание.
1. Составить и решить транспортную задачу открытой модели.
Условие сформулировать так, чтобы при решении задачи использовать метод
запрещения перевозок.
2. Составить и решить задачу о назначении.