ДВУХИНДЕКСНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
“О НАЗНАЧЕНИЯХ”
ЦЕЛЬ РАБОТЫ
Овладение компьютерными методами обработки, моделирования и анализа экономических данных; приобретение практических навыков построения математических моделей двухиндексных задач линейного программирования на примере задачи о назначениях и поиска их оптимального решения средствами табличного процессора Microsoft Excel.
ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ
1. Согласно номеру Вашего варианта выберите условие задачи (раздел 6).
2. Постройте математическую модель задачи, включая транспортную таблицу.
3. Найдите оптимальное решение задачи с помощью табличного процессора Microsoft Excel и представьте его преподавателю.
4. Оформите отчет о лабораторной работе, который должен содержать:
· титульный лист;
· транспортную таблицу и математическую модель задачи с указанием единиц измерения величин;
· размерный результат решения задачи.
ОСОБЕННОСТИ ТЕОРЕТИЧЕСКОГО ОПИСАНИЯ
ЗАДАЧИ О НАЗНАЧЕНИЯХ
Задача о назначениях – это вид распределительной задачи, в которой для выполнения каждой работы требуется один и только один ресурс (один человек, одна автомашина и т.д.), а каждый ресурс может быть использован на одной и только одной работе. То есть ресурсы не делимы между работами, а работы не делимы между ресурсами. Таким образом, задача о назначениях является частным случаем транспортной задачи. Задача о назначениях возникает при распределении людей на должности, самолетов на авиарейсы, автомашин на маршруты, водителей на машины, студенческих групп по аудиториям, научных тем по исследовательским лабораториям и т.п.
Исходные параметры математической модели задачи о назначениях
1. 
– количество видов ресурсов;
– количество видов работ.
2. 
– единичное количество ресурса вида 
(
), например, один работник; одно транспортное средство; одна научная тема и т.д.
3. 
– единичное количество работы вида 
(
), например, одна должность; один маршрут; одна лаборатория, и т.п.
4. 
– характеристика качества выполнения работы вида с помощью ресурса . Например, компетентность 
-го работника при работе на 
-ой должности; время, за которое -е транспортное средство перевезет груз по - му маршруту; степень квалификации -ой лаборатории при работе над -ой научной темой.
Управляемые переменные математической модели задачи о назначениях
1. 
– факт назначения или неназначения ресурса вида на работу вида :
2. 
–суммарный показатель качества распределения ресурсов по работам.
Таблица 1
Общий вид “транспортной матрицы” задачи о назначениях
Ресурсы, 
| Работы, 
| Количество ресурсов | |||
| 
| … | 
| ||
| 
| 
| … | 
| |
| 
| 
| … | 
| |
| … | … | … | … | … | … |
| 
| 
| … | 
| |
| Количество работ | … | 
|
Математическая модель задачи о назначениях
 ;
| (1) |
Специфическая структура задачи о назначениях позволила разработать метод ее решения, получивший название "Венгерского метода". Поэтому, хотя в Microsoft Excel предусмотрены средства решения таких задач симплекс-методом, в данной лабораторной работе требуется построить модель задачи о назначениях вида (1). В некоторых случаях, например, когда 
имеет смысл компетентности, опыта работы, или квалификации работников, условие задачи может требовать максимизации целевой функции, в отличие от (1). Тогда целевую функцию 
заменяют на 
и решают задачу с целевой функцией 
, что равносильно решению задачи максимизации 
.