---
title: "Programowanie liniowe"
source: "https://systems-analysis.info/int/Programowanie_liniowe"
wiki: "systems-analysis.info/int"
article: "Programowanie_liniowe"
language: "pl"
categories:
  - "Category:Mathematical modeling"
  - "Category:Operations research"
  - "Category:Polish"
revision_id: 5901
wiki_created_at: 2026-09-06T23:55:37Z
wiki_modified_at: 2026-09-06T23:55:37Z
downloaded_at: 2026-09-07T23:10:57Z
---

# Programowanie liniowe

**Programowanie liniowe** — to dział programowania matematycznego i szeroko stosowana metoda badań operacyjnych, poświęcona opracowaniu teorii i metod rozwiązywania zadań znajdowania ekstremum (maksimum lub minimum) funkcji liniowej przy obecności ograniczeń liniowych.

Programowanie liniowe (PL) jest jednym z najpotężniejszych i najczęściej stosowanych narzędzi do rozwiązywania zadań optymalizacyjnych w ekonomii, zarządzaniu, planowaniu, logistyce i innych dziedzinach.

## Przedmiot i przeznaczenie

**Podstawowe zadanie programowania liniowego** — znaleźć najlepszy (optymalny) sposób podziału ograniczonych zasobów w celu osiągnięcia pewnego celu, gdy zarówno cel, jak i ograniczenia dotyczące wykorzystania zasobów mogą być wyrażone zależnościami liniowymi.

- Programowanie liniowe pozwala rozwiązywać takie praktyczne zadania, jak:
- Optymalne planowanie produkcji.
- Optymalizacja przepływów transportowych (zadanie transportowe).
- Optymalna alokacja inwestycji.
- Optymalny rozkrój materiałów. Zadanie przydziału.

## Matematyczne sformułowanie zadania PL

Standardowe zadanie programowania liniowego formułuje się następująco:

Należy znaleźć wartości zmiennych decyzyjnych, które maksymalizują lub minimalizują liniową funkcję celu. Przy tym na zmienne decyzyjne nakładane są ograniczenia w postaci układu liniowych równości i/lub liniowych nierówności. Z reguły dodawany jest warunek nieujemności zmiennych decyzyjnych (ich wartości muszą być większe lub równe zero), co często wynika z fizycznego lub ekonomicznego sensu zadania.

Matematycznie oznacza to pracę z funkcjami liniowymi i układami równań/nierówności liniowych.

## Podstawowe pojęcia PL

- Zmienne decyzyjne (zmienne sterowane): Wielkości, których wartości należy wyznaczyć w trakcie rozwiązywania zadania (np. wielkości produkcji różnych wyrobów, ilości zasobów kierowanych na różne cele).
- Funkcja celu: Liniowa funkcja zmiennych decyzyjnych, której wartość należy zmaksymalizować lub zminimalizować. Wyraża ona ilościowo cel zadania (np. łączny zysk, łączne koszty).
- Ograniczenia: Układ liniowych równości i/lub nierówności, którym muszą odpowiadać zmienne decyzyjne. Ograniczenia odzwierciedlają limity zasobów, wymagania technologiczne, zadania planowe i inne warunki zadania.
- Obszar dopuszczalnych rozwiązań (ODR): Zbiór wszystkich zestawów wartości zmiennych decyzyjnych spełniających wszystkie ograniczenia zadania. Geometrycznie w przestrzeni wielowymiarowej ODR jest wypukłym wielościanem (poliedrem), możliwie nieograniczonym lub pustym.
- Rozwiązanie dopuszczalne: Dowolny zestaw wartości zmiennych należący do ODR.
- Rozwiązanie optymalne: Rozwiązanie dopuszczalne, przy którym funkcja celu osiąga swoją wartość ekstremalną (maksymalną lub minimalną). Jeśli rozwiązanie optymalne istnieje, zawsze znajduje się na granicy ODR, co najmniej w jednym z wierzchołków wypukłego wielościanu ODR (podstawowe twierdzenie PL).

## Metody rozwiązywania zadań PL

Istnieje kilka podstawowych metod rozwiązywania zadań programowania liniowego:

- Metoda graficzna: Stosowana do zadań z dwiema zmiennymi decyzyjnymi. Pozwala w sposób poglądowy przedstawić ODR i funkcję celu na płaszczyźnie oraz znaleźć rozwiązanie optymalne poprzez analizę wierzchołków ODR lub przesuwanie linii poziomu funkcji celu.
- Metoda simpleksów: Uniwersalny algorytm iteracyjny opracowany przez George'a Dantziga. Metoda kolejno przechodzi od jednego wierzchołka ODR do sąsiedniego, poprawiając wartość funkcji celu na każdym kroku, aż do znalezienia rozwiązania optymalnego. Jest to klasyczna i najbardziej znana metoda rozwiązywania zadań PL.
- Metody punktu wewnętrznego: Alternatywna klasa algorytmów, która pojawiła się później niż metoda simpleksów. Poruszają się one ku rozwiązaniu optymalnemu wewnątrz ODR, a nie po jej granicach. Metody te są szczególnie efektywne przy rozwiązywaniu zadań PL bardzo dużych rozmiarów.

## Dualność w programowaniu liniowym

Każdemu zadaniu programowania liniowego (zwanemu pierwotnym) można przyporządkować inne zadanie PL, zwane dualnym. Zadanie pierwotne i dualne są ze sobą ściśle powiązane:

Rozwiązanie jednego zadania dostarcza informacji o rozwiązaniu drugiego. Optymalne wartości funkcji celu w obu zadaniach są sobie równe (jeśli istnieją). Zmienne zadania dualnego mają ważną interpretację ekonomiczną — odpowiadają cenom cienia (lub ocenom dualnym) zasobów, wskazując, o ile zmieni się optymalna wartość funkcji celu zadania pierwotnego przy niewielkiej zmianie ograniczenia dotyczącego odpowiedniego zasobu.

## Zastosowanie PL

Programowanie liniowe znajduje szerokie zastosowanie w:

- Ekonomii i biznesie (planowanie produkcji, logistyka, finanse, marketing).
- Przemyśle (optymalizacja procesów technologicznych, zarządzanie zapasami, rozkrój materiałów).
- Transporcie (optymalizacja tras, rozkładów jazdy). Rolnictwie (optymalizacja powierzchni zasiewów, dawek paszowych).
- Energetyce (optymalizacja obciążenia mocy wytwórczych).

## Literatura

- *Dantzig G.* Programowanie liniowe, jego zastosowania i uogólnienia. — M.: Progress, 1966.
- *Judin D. B., Golsztejn E. G.* Programowanie liniowe (teoria, metody i zastosowania). — M.: Nauka, 1969.
- *Taha, Hamdy A.* Operations Research: An Introduction. — Pearson. (10th ed., 2017)
- *Hillier, Frederick S.; Lieberman, Gerald J.* Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)

## Zobacz też

- Badania operacyjne
- Optymalizacja
- Funkcja celu
- Ograniczenia
- Obszar dopuszczalnych rozwiązań
- Rozwiązanie optymalne