Решить задачу без применения ПЭВМ, используя методы аппроксимации и потенциалов.
Опорное решение найти: для студентов с четным номером N – методом аппроксимации;
для студентов с нечетным номером N –методом минимального элемента.
Записать полный ответ решения задачи и проверить значение целевой функции.
Решение задачи
Запись задачи в структурном виде.
Целевая функция:
Z=
Zконтр=
Ограничения.
а) по строкам:
б) по столбцам:
Балансовое условие:
Условие неотрицательности переменных:
Таблица 2
Табличное представление исходных данных задачи
| Бригада | Стоимость обследования одного м2, тыс.руб. | Максимальная площадь, которую может обследовать бригада, м2 | |||||||||||
| 1-й гараж. коопер. | 2-й гараж. коопер. | 3-й гараж. коопер. | 4-й гараж. коопер. | ||||||||||
| №1 | |||||||||||||
| №2 | |||||||||||||
| №3 | |||||||||||||
| №4 | |||||||||||||
| Площадь, подлежащая обследованию, м2 | |||||||||||||
Таблица 3
Приведение задачи к сбалансированному виду с помощью фиктивных объектов (строки, столбца)
| № п/п | Бригада | Стоимость обследования одного м2, тыс.руб. | Фиктивный столбец | Максимальная площадь, которую может обследовать бригада, м2 | |||
| 1-й гараж. коопер. | 2-й гараж. коопер. | 3-й гараж. коопер. | 4-й гараж. коопер. | ||||
| №1 | |||||||
| №2 | |||||||
| №3 | |||||||
| №4 | |||||||
| Фиктивная строка | |||||||
| Площадь, подлежащая обследованию, м2 |
Запись ЭММ в расширенном виде с конкретными технолого-экономическими показателями
Граничные условия
а) по строкам: б) по столбцам:
1. 1.
2. 2.
3. 3.
4. 4.
5. 5.
в) балансовое условие:
г) условие неотрицательности переменных:
Целевая функция задачи Z=
Таблица 4
Определение опорного решения методом аппроксимации
| i j | Ai |  1 | 2 | 3 | 4 | 5 | 6 | ||||||||
| Bj | |||||||||||||||
| 1 | |||||||||||||||
| 2 | |||||||||||||||
| 3 | |||||||||||||||
| 4 | |||||||||||||||
| 5 | |||||||||||||||
| 6 | |||||||||||||||
Проверка опорного решения на выполнение граничных условий:
а) по строкам: б) по столбцам:
1. 1.
2. 2.
3. 3.
4. 4.
5. 5.
Проверка на число занятых клеток:
Значение целевой функции
Z1=
Таблица 5
Потенциалы 
для опорного решения задачи
№ | |||||||||
  | |||||||||
Проверка опорного решения на оптимальность и, при необходимости, его улучшение. Вычисление 
для свободных клеток по формуле:
Улучшающий многоугольник строим для клетки с максимальной по модулю оценкой =
Таблица 6
Потенциалы для улучшенного решения задачи
| № | ||||||
| | ||||||
Проверка улучшенного решения на выполнение граничных условий.
а) по строкам: б) по столбцам:
1. 1.
2. 2.
3. 3.
4. 4.
5. 5.
Значение целевой функции.
Z2=
Таблица 7
Оптимальное решение задачи
| № п/п | Бригада | Стоимость обследования одного м2, тыс.руб. | Максимальная площадь, которую может обследовать бригада, м2 | |||
| 1-й гараж. коопер. | 2-й гараж. коопер. | 3-й гараж. коопер. | 4-й гараж. коопер. | |||
| №1 | ||||||
| №2 | ||||||
| №3 | ||||||
| №4 | ||||||
| Площадь, подлежащая обследованию, м2 |
Zопт=
Ответ задачи: